Problema 5 del primer nivel de la Olimpiada de Mayo 2023
Se dirige a una edad de: 11-12 años

Se tienen 100 cajas que se etiquetaron con los números 00, 01, 02, …, 99. En mil tarjetas se escribieron los números 000, 001, 002, …, 999, uno en cada tarjeta.

Está permitido colocar una tarjeta en una caja si el número de la caja se puede obtener al eliminar uno de los dígitos del número de la tarjeta. Por ejemplo, está permitido colocar la tarjeta 037 en la caja 07, pero no está permitido colocar la tarjeta 156 en la caja 65.

¿Puede ocurrir que luego de colocar todas las tarjetas en las cajas, haya exactamente 50 cajas vacías?

Si la respuesta es sí, indicar cómo se colocan las tarjetas en las cajas; si la respuesta es no, explicar por qué es imposible.

Solución:

En este tipo de problemas es muy difícil manejar números tan grandes, conviene practicar con una colección más pequeña. Por ejemplo, podemos ensayar con los números de caja 00, 01, 02, 03, 10, …, 33, usando sólo 3 dígitos, 16 cajas, y los de las tarjetas 000 a la 333 (64 tarjetas).

Está clara que la pregunta aquí se reduce a estudiar si podemos dejar 8 cajas vacías o no.

Lo primero, hay 4 tarjetas que no queda más remedio que entren en una caja determinadas, 000, 111, 222, 333, que obligatoriamente usarán 00, 11, 22, y 33.

Podemos meter los números con dos cifras repetidas en esas que ya tienen relleno, y sólo nos quedan los números con las tres cifras diferentes, 012, 013, 021, 023, 031, 032, 102, 103, etcétera (24 tarjetas).

Supongamos que usamos la caja 01 para guardar todos los que llevan un 0 y un 1 en ese orden. La clave es usar también la 10, y sólo nos quedarán los que NO llevan un 0 y un 1. Por eliminación, si no llevan a la vez un 0 y un 1, llevan un 2 y un 3, por lo que podemos repartir los demás en las cajas 23 y 32, así que la respuesta es que sí en este contexto.

Pasemos al problema completo y extendamos este método.

Tenemos que meter todas las tarjetas en 50 cajas.

Diez de ellas serán las que tienen números repetidos, y allí meteremos las que tienen un par de números repetidos.

Las otras 40, las iremos poniendo de 2 en 2, la 01 y la 10, la 02 y la 20, la 12 y la 21, así podemos usar las 20 tarjetas que usan los dígitos del 0 al 4 en cualquier orden (5·4 = 20 cajas). Podremos guardar todas las tarjetas que tienen un par de números menores que 5, es decir que todos los demás tienen al menos 2 números mayores que 5, así que usamos las otras 20 cajas que tienen las parejas de números entre el 5 y el 9 (de nuevo otras 20 cajas), y podremos guardar todas las tarjetas.

Y para ver que no hay 51 cajas vacías, podemos buscar algunos número concretos que entren en cada una de las cajas concretas que hemos citado (de hecho, es inevitable que todas las cajas tengan alguna tarjeta, por ejemplo en la caja 97 debemos meter el 197, porque ninguna de las otras cajas seleccionadas permite guardarla). Sin embargo, el 578 podemos guardarlo en 3 cajas distintas a nuestro gusto.