El problema de los tornillos

http://www.elpais.com/videos/sociedad/Pesando/tornillos/elpepusoc/20110526elpepusoc_1/Ves/

Tenemos seis cajas con 13 tornillos cada una. En tres cajas los tornillos pesan seis gramos cada uno y en las otras tres los tornillos pesan cinco gramos cada uno (todos los tornillos de cada caja pesan lo mismo), pero las cajas tienen todas el mismo aspecto. Tenemos también una báscula de precisión a nuestra disposición (no una balanza) donde podemos pesar los tornillos que queramos. ¿Cuál es el mínimo número de veces que necesitamos utilizar la báscula para saber qué cajas contienen los tornillos de cinco gramos y de qué manera se haría?

El mínimo número de pesadas es 1. Hay 4 soluciones:

Pesar de las distintas cajas 0,1,2,4,7,13 o bien 0,1,2,7,10,13 o bien 0,3,6,11,12,13 o 0,6,9,11,12,13 tornillos y ver el resultado de la pesada.

Vayamos al caso primero  0,1,2,4,7,13 (Total 27 tornillos) Si todos los tornillos pesaran 5 gr sería 135 gr y si fueran todos 6 gr -> 162 gr.

Esos dos valores no se pueden dar ya que al menos hay 3 tornillos de cada peso, la tabla queda:

  

Caja A      B       C       D       E        F        Suma

Tornillos

Pesados

       1       2       4        7     13        0

 

5	5	5	6	6	6	155
5	5	6	5	6	6	152
5	5	6	6	5	6	146
5	5	6	6	6	5	159
5	6	5	5	6	6	150
5	6	5	6	5	6	144
5	6	5	6	6	5	157
5	6	6	5	5	6	141
5	6	6	5	6	5	154
5	6	6	6	5	5	148
6	5	5	5	6	6	149
6	5	5	6	5	6	143
6	5	5	6	6	5	156
6	5	6	5	5	6	140
6	5	6	5	6	5	153
6	5	6	6	5	5	147
6	6	5	5	5	6	138
6	6	5	5	6	5	151
6	6	5	6	5	5	145
6	6	6	5	5	5	142

A la caja F le he dado el valor 0. Aunque no pesamos ningún tornillo de la caja F su contenido queda determinado por el contenido de las otras 5 cajas ya que han de ser 3 y 3 de cada clase. 

Como vemos cada caso se corresponde con un resultado diferente de la pesada.

¿Cómo han salido estos valores? El primer conjunto son los primeros valores de la secuencia Conway-Guy:

0,1,2,4,7,13,24,44,84,161,309,594,1164,2284,4484,8807,17305,34301,68008,134852, 267420,530356,1051905,2095003,4172701,8311101,16554194

Que tiene la propiedad de que todas las sumas de los diferentes subconjuntos de esos números dan distinto valor. Nos basta en realidad con que las sumas de 3 en 3 den diferente.

Los otros conjuntos de números salen de un programa escrito en C que busca todas las posibles soluciones.

Sumas diferentes que han de verificarse: Combinaciones de 6 elementos tomados de 3 en 3 = 20.

Valores posibles a rastrear: Combinaciones de 13 elementos tomados de 5 en 5 =  1287

Resultado del programa 

Funciona 1 2 4 7 13
 Funciona 1 2 7 10 13
 Funciona 3 6 11 12 13
 Funciona 6 9 11 12 13
 Encontrados 4 casos de 1287 probados