Solución al 11º Desafío matemático de El País


Ya hay solución para el undécimo desafío matemático con el que EL PAÍS celebra el centenario de la Real Sociedad Matemática Española. Varios niños del IES Alameda de Osuna de Madrid propusieron el problema (ver vídeo de la izquierda) y lo resuelven ahora (vídeo de la derecha): es posible hacerlo en una sola pesada eligiendo bien el número de tornillos que se extraen de cada caja (de hecho hay cuatro soluciones posibles). La ganadora de una biblioteca matemática como la que entrega cada semana EL PAÍS ha sido en esta ocasión Antonia Rodríguez Paredes, Montcada i Reixac (Barcelona). Este domingo, en el quiosco, por 9,95 euros con el periódico, La armonía es numérica (música y matemáticas), de Javier Arbonés y Pablo Milrud.

Recordemos el enunciado del problema: 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?

La solución es que puede conseguirse con una solo pesada. En ella incluiremos un número diferente de tornillos de cada caja (entre el 0 y el 13). Si el total de tornillos que pesamos es N, el peso será 5xN más el número de tornillos que hayamos usado de las 3 cajas con tornillos de 6 gramos.

Probemos primero con un tornillo de la primera, dos de la segunda, tres de la tercera… En total tendremos 21 tornillos en la báscula y, por tanto marcará 21 X 5 = 105 gr mas un gramo por cada tornillo de las cajas de 6 gramos que hayamos puesto. Si la báscula marcara 112 gr sabríamos que hay 7 tornillos de 6 gramos y, como 7 = 1 + 2 +4, los tornillos de 6 gramos estarían en las cajas a, b y d. Lo malo es que si la báscula marca, por ejemplo, 114 gr sabríamos que hay 9 tornillos de 6 gramos pero como 9 se puede escribir de muchas formas distintas como suma de tres de esos números (9 = 1 + 2 + 6 = 1 + 3 + 5 = 2 +3 + 4) no podemos saber de qué cajas los he cogido.

Así que, para evitar confusiones, tenemos que conseguir 6 números entre 0 y 13 de manera tal que las sumas de tres de ellos sean siempre números distintos. Para ello se debe cumplir además que la suma de dos de ellos sean distintas (si por ejemplo en mi lista esta tengo 1, 2, 3, 4 y dos números más , como 1 + 4 = 2 + 3 usando otro de los números tendré dos ternas -grupos de tres- que suman lo mismo).

El desafío, tal y como está planteado, admite cuatro posibles soluciones: 0, 1, 2, 4, 7, 13 y su complementaria (restando de 13) 0, 6, 9, 11, 12, 13, que son las dos que aparecen en el vídeo, y también 0, 1, 2, 7, 10, 13 y su complementaria 0, 3, 6, 11, 12, 13. La primera, la que encuentran nuestros jóvenes presentadores, es la que requiere pesar menos tornillos. Decimos que hay sólo cuatro soluciones porque no importa de qué caja se tome cada número de tornillos. Si queremos tomar en consideración las 720 maneras en que podemos ordenar las cajas las soluciones serían 2880.

Se han recibido 1.040 respuestas, de las que el 55% son correctas, un 30% no han conseguido dar con la estrategia acertada y el 15% apuntan a que hay que buscar 6 números de manera que sus sumas 3 a 3 sean todas distintas (esto está bien), pero los números que dan no funcionan. Vale la pena señalar que algunos lectores apuestan por la base 2, lo que en principio es una buena idea porque permite resolver problemas más generales, y proponen como solución 0, 1, 2, 4, 8, 16 (o 1, 2, 4, 8, 16, 32). Pero en nuestro desafío cada caja tiene sólo 13 tornillos.

Queremos destacar la manera en que ha resuelto el problema, encontrando todas las soluciones, Rodrigo Rivas Costa, porque es un buen ejemplo de que el pensamiento abstracto y los métodos modernos de cálculo no están reñidos. Rodrigo empieza por tener la idea de que quizás pueda hacerlo en una pesada tomando un número adecuados de tornillos de cada caja. Observa que hay 20 maneras en las que pueden estar distribuidos los tornillos de 5 y 6 gramos, y que lo que necesita es que el peso de los tornillos que pone en la báscula sea distinto en cada uno de los 20 casos. Tiene por tanto que buscar 6 números entre 0 y 13 con esas condiciones.

En principio hay 14^6=7.529.536 colecciones de 6 números entre 0 y 13 pero, dice Rodrigo, el orden no importa y, además no puede haber dos números iguales en la lista porque se producirían repeticiones en las pesadas, así que sólo hay que probar con 3003 casos. Señala también que puede restar 5 gramos a cada tornillo y trabajar con pesos 0 y 1; por eso son las suma de 3 números las que deben ser distintas. Hasta aquí tenemos la idea inicial (que es lo más importante) y una serie de razonamientos abstractos (todo esto valdría en otras situaciones).

Dice ahora Rodrigo “Como 3003 es un número razonablemente pequeño, una selección de tornillos válida se puede buscar a mano, por tanteo, o con un programa de ordenador. He optado por escribir un programa de ordenador que recorra esas 3003 combinaciones, y así he encontrados todas las selecciones de tornillos válidas, que son 4 [las que hemos indicado anteriormente]”.

José Luis Sánchez del Villar, como otros lectores, nos pregunta: “¿Os habéis acordado de marcar los tornillos antes de pesarlos o de no mezclar los de distintas cajas en el platillo de la báscula? Son idénticos (si no, bastaría una pesada para ver qué tipo de tornillo pesa 5 gramos) así que si se mezclan no habrá manera de separarlos.” y propone “se pueden marcar con una lima: la marca se puede hacer todo lo pequeña que queramos para no afectar a la medición, o mejor todavía, se puede usar la lima de manera que las virutas caigan en el platillo, así la medida seguiría siendo correcta.”

Belén, Dana, Daniel, Irene, Javier, Jimena y Patricia sí se habían percatado de este problema y habían pintado de distintos colores las cabezas de los tornillos, pero dificultades técnicas en la grabación impidieron mostrarlo. La solución al desafío es un ejemplo sencillo de Conjunto de Sidon, un tema activo de investigación.

El jueves plantearemos un nuevo reto.

 

7 comentarios

Archivado bajo OTROS

7 Respuestas a “Solución al 11º Desafío matemático de El País

  1. Copio aquí los comentarios que D. Francisco Javier Cilleruelo, profesor de la Universidad Autónoma de Madrid y miembro del Instituto Ciencias Matemáticas (ICMAT), (ver Tercer Desafío Matemático) nos hizo sobre este problema:

    “Después de todas las entradas anteriores, está claro que de lo que se trata es de elegir en el conjunto {0,1,2,…,13} un subconjunto de 6 números con la propiedad de que todas las sumas de tres de ellos sean distintas.
    La manera más natural (pero no la única) de buscar un subconjunto con esta propiedad es ir eligiendo los números más pequeños posibles. Empezamos eligiendo el 0, luego el 1, luego el 2. Si elegimos el 3 ya no podemos seguir porque 0+3+x=1+2+x para cualquier otro número x que elijamos posteriormente. Así que pasamos a elegir el 4, que de momento no viola la propiedad. El 5 no podemos elegirle porque 0+2+5=1+2+4. El 6 tampoco podemos porque 0+1+6=1+2+4. El 7 sí que podemos. Siguiendo con esta estrategia, tampoco podríamos elegir ni el 8, ni el 9, ni el 10, ni el 11, ni el 12. Finalmente el 13 sí que podemos y ya tenemos nuestro subconjunto de 6 elementos con la propiedad de que todas las sumas de tres elementos son distintas: 0, 1, 2, 4, 7, 13. Es claro que el conjunto simétrico, 13,12,11,9,6,0 también es una solución. Pero además, como ya se ha apuntado en entradas anteriores, existe otro subconjunto (y su simétrico) que también es una solución.

    Este problema está muy relacionado con un problema de teoría combinatoria de números que sigue sin estar resuelto. Si alguien está interesado puedo hacer otra entrada explicando la conexión.”

    “Gracias por animarme a escribir esta entrada.

    El problema admite muchas generalizaciones, todas ellas interesantes.
    Voy a comentar una de estas variantes. Primero lo haré dentro del contexto del problema de los tornillos de EL PAIS, y posteriormente enunciaré la misma variante, pero con un enunciado más matemático.
    Acabaré la entrada comentando la conexión de este problema con los conjuntos de Sidon.

    Variante (versión tornillos):
    Tenemos n cajas de tornillos (en lugar de 6). Los tornillos de cada caja pesan todos 5 gramos excepto los que hay en tres cajas defectuosas que pesan 6 gramos. ¿cuántos tornillos tiene que haber en cada caja para poder detectar las tres cajas en una sola pesada?

    Si llamemos T(n) a la solución del problema, lo que el problema de EL PAIS nos dice es que T(6)=13. No es difícil comprobar que si las cajas hubieran tenido 12 tornillos cada una, el problema no se podría haber resuelto con una pesada.

    Variante (enunciado matemático): Decimos que una sucesión creciente de enteros es una sucesión B_3 si todas las sumas de tres elementos distintos de la sucesión son distintas. ¿Cuál es menor valor que puede tener el último término de una sucesión B_3 de n enteros que empieza en 0?

    Como los dos problemas son equivalentes, llamemos de nuevo T(n) a la respuesta. La sucesión 0, 1, 2, 4, 7, 13 es una sucesión B_3 y no es difícil comprobar que no se puede construir ninguna cuyo último término sea menor que 13. Así que, como ya sabíamos, T(6)=13.

    Calcular el valor exacto de T(n) para un valor de n concreto es un problema que sólo se sabe hacer para valores pequeños de n, y por métodos computacionales. Ni siquiera se conoce una estimación aproximada para T(n) cuando n es grande. No es difícil demostrar que
    n(n-1)(n-2)/18<T(n) y también se sabe (aunque es bastante más difícil de demostrar) que hay infinitos valores de n para los que T(n)<n^3.
    La mejor estimación en este problema se debe a Ben Green, uno de los mejores matemáticos del momento, conocido por haber demostrado, junto con Terence Tao, que los primos contienen progresiones aritméticas arbitrariamente largas. Ben Green consiguió sustituir el número 18 de la primera desigualdad por el número 7/2.

    ¿Cuál es el límite de T(n)/n^3 cuando n tiende a infinito?
    Nadie lo sabe. Se cree que es 1, pero sólo se sabe que, si el límite existe, es un número entre 2/7 y 1.

    CONJUNTOS DE SIDON.
    Si en lugar de tres cajas defectuosas hubiera dos, estaríamos hablando de sucesiones B_2 (también llamados conjuntos de Sidon) que tienen la propiedad que todas las sumas de dos elementos de la sucesión son distintas. Para estos conjuntos sí que se ha demostrado (lo demostró Paul Erdos) que el límite de T(n)/n^2 cuando n tiende a infinito es 1.

    Como curiosidad comento que si en el problema de EL PAIS hubiera habido dos cajas con tornillos de 6 gramos y las otras cuatro con tornillos de 5 gramos, sólo hubieran hecho falta 12 tornillos en cada caja para detectar las dos cajas defectuosas en una pesada. Es decir, T(6)=12 (cuando hay dos cajas defectuosas). En ese caso la solución sí que es única (salvo la simétrica).

    Un cordial saludo"

  2. Al final, como era esperable, la solución “oficial” de El País suponía que, una vez se tuviera claro el concepto (seis números del 0 al 13, con suma siempre distinta de tres en tres) el hallar los números exactos habría de hacerse un poco por “ensayo y error”, o por medio de “ayudas mécanicas” ( = excel, un programita…) sin buscarle ningún meollo téorico o abstracto. Siendo sincero, reconozco que me decepciona un poco (personalmente, sobre todo después de haber intentado “currarme” un algoritmo para generalizar para “n” cajas, je, je… y también después de todo lo que se habló en los comentarios del blog sobre si se podría demostrar que esas 4 soluciones eran únicas)…

    … por eso es alucinante y un orgullo el ser consciente de que nuestros “humildes comentarios” han sido vistos y completados con una explicación del nivel que ansiábamos ni más ni menos que por una eminencia, además uno de los encargados de por lo menos uno de los problemas propuestos. Será una tontería, pero me ha dado un “subidón” el verlo.

    Estoy pensando (no sé si él mismo querrá o podrá confirmarlo) que, puesto que este último problema de los tornillos estaba relacionado con los Conjuntos de Sidon, y que él mismo parece ser un estudioso de ese tema, que tal vez el propio Dr. Cilleruelo es el responsable de este último problema… y esto nos quitaría una de esas dudas del tipo de “si lo presentan chavales, tal vez es que ellos han contribuido a la elaboración del problema”.

  3. Borja

    Aquí os dejo un enlace interesante acerca de la demostración del tamaño de los conjuntos g-Sidón, por parte del Dr. Cilleruelo y su equipo.

    Admirable…

  4. jabon

    Uno se queda más tranquilo viendo estas explicaciones.
    Muchas gracias al Dr. Cilleruelo.
    Mira que me tenía el coco comido el reto, aunque supiese las respuestas, mas que nada porque lo presentasen los niños.
    Y también gracias a Santi, que estás consiguiendo que tu blog sea lo que es. Enhorabuena.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s