jueves, 3 de diciembre de 2009

Tarjetas en pilas

XV Olimpiada de Mayo, tercer problema del primer nivel, 2009

Se tienen 26 tarjetas y cada una tiene escrito un número. Hay dos con el 1, dos con el 2, dos con el 3, y así siguiendo hasta dos con el 12 y dos con el 13. Hay que distribuir las 26 tarjetas en pilas de manera que se cumplan las dos condiciones siguientes:

(i) Si dos tarjetas tienen el mismo número están en la misma pila.

(ii) Ninguna pila contiene una tarjeta cuyo número es igual a la suma de los números de dos tarjetas de esa misma pila.

Determina cuál es el mínimo número de pilas que hay que hacer. Da un ejemplo con la distribución de las tarjetas para ese número de pilas y justifica por qué es imposible tener menos pilas.

Solución

3 comentarios:

Alex dijo...

Yo he encontrado una manera de distribuir que consigue pocas pilas, en este caso 4, pero todavía no he conseguido demostrar que sea el mínimo.

- En la primera pila tomo los impares: 1, 3, 7, 9, 11, 13 (15, 17, 19, ... si hubieran más cartas)

- En la segunda los pares, pero tomados de cuatro en cuatro: 2, 6, 10 (14, 18, 22, ... si hubieran más cartas)

- En la tercera comienzo con el cuatro y le voy sumando 8: 4, 12 (20, 28, ... si hubieran más cartas)

- En la cuarta comienzo con el ocho y le voy sumando 16: 8 (24, 40, ... si hubieran más cartas)

Vamos, que la he tomado con las potencias de dos (deformación profesional, que soy informático).

Si las filas estuvieran numeradas: fila 1, fila 2, fila 3, ...

sea la fila n: su primera carta es 2^(n-1) y las siguientes cartas de la misma fila las obtengo sumando 2^n

Gracias por tu blog. Mi pasión de siempre fueron las matemáticas, pero finalmente estudié informática y nunca encontraba tiempo para trabajar un poquito las mates. Ahora los viajes en autobús del trabajo a casa los dedico a intentar resolver estos problemas tan entretenidos que propones.

Proble Mático dijo...

La sugerencia de Alex nos deja con cuatro montones, ¡a ver si alguien demuestra que tres no es suficiente, o bien encuentra una distribución en tres montones!
(recordad que son 26 cartas, del 1 al 13 dos veces)

Alex dijo...

El método que propuse no consigue el mínimo número de pilas.

una pista ¿puede ser que para del 1 al 33 parejas de cartas basten 4 pilas, pero para del 1 al 34 parejas se necesiten ya 5 pilas?