miércoles, 19 de marzo de 2014

Agrupando tarjetas

Enunciado

El máximo teórico de puntos que tenemos repartidos en todas las tarjetas es 5*200 + 2*200 + 1*200 = 8*200 = 1600. Si pudiéramos separar los puntos de las tarjetas, podríamos hacer 1600/9 = 177, y sobrarían 7 puntos. Pero como no podemos separarlos, vamos a tratar de agruparlas de varias formas hasta dar con el máximo.

Hay varias formas de razonarlo.

Por ejemplo, si apartamos las tarjetas de 5, disponemos de tarjetas pequeñas que seguro podemos agrupar al máximo, y después ir añadiendo una a una tarjetas de 5 para tratar de dejar el mínimo de puntos fuera.

También podemos intentarlo al revés, de forma que agrupemos todas las tarjetas de 5 que podamos y después ver cuántas sobran.

Tomemos la primera de las ideas: Si agrupamos todas las de 1 y 2, el total de puntos es 600, que en teoría da para 600/9 = 66 y sobran 6. Podemos formar grupos de 9 con cuatro tarjetas de 2 y una de 1, hasta que nos quedemos sin tarjetas de 2 (200/4 = 50), eso hará 50 grupos, y aún quedarán 150 tarjetas de 1, que se repartirán en (150/9 = 16) 16 grupos de 9 tarjetas de 1, donde sobrarán sólo 6 tarjetas de 1 punto. Efectivamente, alcanzamos el máximo teórico.

Ahora, si introducimos tarjetas de 5 (en un grupo de 9 puntos, las tarjetas de 5 deben ir de una en una, no pueden unirse dos), necesitamos romper un grupo que tenga tarjetas 2 y reagrupar dos de ellas con cada 5, y unir las tarjetas de 1 entre sí para agrupar 9 cuando tengamos suficientes (la alternativa también es posible, romper los grupos de 1, pero podemos dejar esto para el final, ya que las tarjetas de 1 son más fáciles de reagrupar). Es decir, si incorporamos 36 tarjetas de 5, por ejemplo, tendríamos que romper 18 grupos de 2 + 2 + 2 + 2 + 1, originando 36 grupos de 5 + 2 + 2, y 4 nuevos grupos de 9*1, dejando siempre de exceso los 6 unos del principio. Este proceso sólo lo podemos hacer mientras queden grupos de 4*2 + 1, es decir, sólo 100 tarjetas 5 podrán ser incorporadas con éxito de esa forma. Pasamos ahora a una situación en la que tenemos 100 grupos 5 + 2*2, y las tarjetas 1 se situarán formando grupos de 9, 22 grupos de 9, sobrando 2 de ellas.

Ahora, las tarjetas 5 que añadamos (recuerda que tenemos 100 todavía), no pueden conseguir más 2, pero aún pueden romper un grupo de 9 unos para formar 5 + 4*1, y si añadimos dos 5 sólo quedará una tarjeta de 1 sobrante (que se podrá unir a los demás 1, quedando un resto si suman menos que 9). Así podremos añadir (200 / 4 = 50) 50 tarjetas de 5, hasta tener 50 grupos más con 5 + 4*1, y en ese caso no sobrará ningún 1.

Lamentablemente, aún nos quedarán 50 tarjetas 5 por agrupar, y no podremos incorporarlas sin romper un grupo y dejar, a su vez, una tarjeta 5 sin agrupar. Por tanto, nuestro procedimiento nos proporciona 150 grupos de tarjetas (100 de 5 + 2*2 y 50 de 5 + 4*1) y un excedente de 50 tarjetas 5, que sumarán 150*9 + 50*5 = 1350 + 250 = 1600 puntos en total.

Pero ¿es esa la cantidad máxima que podemos lograr? ¿habrá un reparto en el que haya más grupos?

Para estar seguros de que no, ahora que tenemos la respuesta que creemos correcta, lo plantearemos por reducción al absurdo.

Supongamos que hemos conseguido un reparto con más de 150 grupos. Para fijar ideas, pensemos que logramos 151 grupos y ponemos en otro montón las tarjetas restantes. Si sumamos los puntos, en el montón sobrante habrá menos de 250 puntos, es decir, que fuera de los grupos hay menos de 50 tarjetas de 5, pero eso quiere decir que en los repartos hemos usado más de 150 tarjetas con 5, y como sólo puede haber una de 5 en cada grupo, significa que habrá exactamente 1 en cada grupo.

Por tanto, en cada grupo de los 151 hay 4 puntos en tarjetas de 2 y de 1, es decir 151*4 = 604 puntos al menos, cuando sabemos que a lo sumo hay 600 puntos entre todas las tarjetas de esos tipos.

Esto es imposible.

Por tanto, en efecto el máximo posible de grupos es 150, y anteriormente se ha descrito uno de los repartos posibles.