jueves, 25 de julio de 2013

1184 - Dados especiales

En la página de IBM, aparece todos los meses un problema, el siguiente apareció este mes:
Si usted tira tres dados con ocho caras numeradas de la siguiente forma 1,4,15,64,256,1024,4096 y 16384,  puede lograr 120 sumas diferentes. En este caso la cara mas grande tiene un valor de 16384.

Encuentre 8 valores positivos que puedan colocarse en las caras de dichos dados, para lograr 120 sumas posibles diferentes al tirar tres dados, de forma tal que el valor de la cara que tiene el mayor valor sea mínimo.

Pongamos por ejemplo un dado de tres caras: Si los valores que tiene este dado fueran 1,2,3, se pueden lograr solo siete sumas diferentes de las diez posibles : 3,4,5(2),6(2),7(2),8 y 9
En cambio si los dados tuvieran estos valores: 1, 2 y 5 se pueden lograr diez sumas diferentes

111 = 3
112 = 4
115 = 7
122 = 5
125 = 8
155 = 11
222 = 6
225 = 9
255 = 12
555 = 15

La idea es encontrar los dados de n lados, con la cara que tiene el valor mas alto mínimo y con los cuales se obtenga  la mayor cantidad de sumas diferentes al arrojar tres de ellos. 
Yo tengo una solución que ví en Internet

Si lo quieres compartir o guardar
Share/Bookmark

12 comentarios:

  1. Si mis cálculos no fallan:
    NºCaras
    3 (1,2,5) suma 10
    4 (1,2,5,14) suma 20
    5 (1,2,5,14,33) suma 35
    6 (1,2,5,14,33,72) suma 56
    7 (1,2,5,14,33,72,125) suma 84
    8 (1,2,5,14,33,72,125,219) suma 120

    La secuencia que indica los valores de las caras se puede consultar en http://oeis.org/A096772

    Vicente iq.

    ResponderEliminar
    Respuestas
    1. Vicente : se puede lograr que los valores de las caras con el máximo valor sean menores a los que tu pones, Saludos

      Eliminar
    2. Me hubiera gustado que se cumpliera la norma.
      Vicente iq.

      Eliminar
  2. Segundo intento.
    NºCaras
    3 (1,2,5) suma 10
    4 (1,2,8,12) suma 20
    5 (1,2,16,19,24) suma 35
    6 (1,3,12,27,43,46) suma 56
    7 (1,2,8,51,60,79,83) suma 84

    Vicente iq.

    ResponderEliminar
  3. Aparentemente no encuentro ningún patrón para formar estos números. Cuando encuentre el de 8 lo pondré.

    Vicente iq.

    ResponderEliminar
    Respuestas
    1. Los valores que he puesto los he encontrado por fuerza bruta porque llevan un tiempo relativamente pequeño.
      El de 8 caras lleva mucho tiempo por el mismo procedimiento.
      Llamemos a cada cara a1,b1,c1,d1,e1,f1,g1 y h1.
      He calculado las distintas sumas que se pueden dar con 8 caras, son 120 como máximo. Las pongo por si alguien está interesado:
      3 a1, 2 a1 + b1, 2 a1 + c1, 2 a1 + d1, 2 a1 + e1, 2 a1 + f1,
      2 a1 + g1, 2 a1 + h1, a1 + 2 b1, a1 + b1 + c1, a1 + b1 + d1, a1 + b1 + e1, a1 + b1 + f1, a1 + b1 + g1, a1 + b1 + h1, a1 +
      2 c1, a1 + c1 + d1, a1 + c1 + e1, a1 + c1 + f1, a1 + c1 + g1, a1 + c1 + h1, a1 + 2 d1, a1 + d1 + e1, a1 + d1 + f1, a1 + d1 + g1, a1 + d1 + h1, a1 +
      2 e1, a1 + e1 + f1, a1 + e1 + g1, a1 + e1 + h1, a1 + 2 f1, a1 + f1 + g1, a1 + f1 + h1, a1 + 2 g1, a1 + g1 + h1, a1 + 2 h1, 3 b1, 2 b1 + c1, 2 b1 + d1, 2 b1 + e1, 2 b1 + f1, 2 b1 + g1, 2 b1 + h1, b1 + 2 c1, b1 + c1 + d1, b1 + c1 + e1, b1 + c1 + f1, b1 + c1 + g1, b1 + c1 + h1, b1 + 2 d1, b1 + d1 + e1, b1 + d1 + f1, b1 + d1 + g1, b1 + d1 + h1, b1 + 2 e1, b1 + e1 + f1, b1 + e1 + g1, b1 + e1 + h1, b1 + 2 f1, b1 + f1 + g1, b1 + f1 + h1, b1 + 2 g1, b1 + g1 + h1, b1 + 2 h1, 3 c1, 2 c1 + d1, 2 c1 + e1, 2 c1 + f1, 2 c1 + g1, 2 c1 + h1, c1 +
      2 d1, c1 + d1 + e1, c1 + d1 + f1, c1 + d1 + g1, c1 + d1 + h1, c1 + 2 e1, c1 + e1 + f1, c1 + e1 + g1, c1 + e1 + h1, c1 + 2 f1, c1 + f1 + g1, c1 + f1 + h1, c1 + 2 g1, c1 + g1 + h1, c1 + 2 h1, 3 d1, 2 d1 + e1, 2 d1 + f1, 2 d1 + g1,
      2 d1 + h1, d1 + 2 e1, d1 + e1 + f1, d1 + e1 + g1, d1 + e1 + h1, d1 +
      2 f1, d1 + f1 + g1, d1 + f1 + h1, d1 + 2 g1, d1 + g1 + h1, d1 +
      2 h1, 3 e1, 2 e1 + f1, 2 e1 + g1,2 e1 + h1, e1 + 2 f1, e1 + f1 + g1, e1 + f1 + h1, e1 + 2 g1, e1 + g1 + h1, e1 + 2 h1, 3 f1, 2 f1 + g1,
      2 f1 + h1, f1 + 2 g1, f1 + g1 + h1, f1 + 2 h1, 3 g1,
      2 g1 + h1, g1 + 2 h1, 3 h1

      Se puede ir dando valores a a1,b1 y c1, las demás letras se dejan sin valor, y contar las sumas distintas que aparecen. De esta forma se simula un algoritmo de backtraking y es mucho más rápido de calcular.

      El mínimo encontrado hasta ahora con este método es:
      1,2,5,21,76,102,136,145
      pero sigo buscando.
      Vicente iq.

      Eliminar
    2. El menor que encuentro:
      1,2,19,34,78,124,130,134

      Vicente iq.

      Eliminar
    3. menor todavía:
      1,3,6,35,75,108,121,130

      Vicente iq.

      Eliminar
  4. Para reducir el tiempo del cómputo y basándome en los resultados de 3 a 7 caras, publicados por Ed Pegg, yo establezco las siguientes hipótesis simplificantes:

    El primer término es siempre 1
    El segundo término es mayor que el primer término en al menos una unidad
    Del tercero al penúltimo término el valor menor es 2^i, i=2, 4, ...
    El último término es mayor que el penúltimo término en al menos una unidad

    Con dichas hipótesis mi programa está corriendo en caso de 8 caras.

    ResponderEliminar
  5. Pero por los resultados ya obtenidos por Vicente, veo que su programa es mucho más veloz que el mío. Abandonaré la búsqueda esta noche si no consigo nada hasta esa hora.

    ResponderEliminar

Si quieres deja un comentario, si la entrada tiene mas de 15 dias deberás esperar a que la autorice y por favor si no tienes gmail deja tu nombre si no quedas como anónimo. Gracias!