Al inicio Igna distribuye $1000$ bolillas en $30$ cajas. Luego Igna y Mica juegan alternadamente, comenzando por Igna. Cada jugador, en su turno, elige una caja y retira una bolilla. Cuando un jugador retira la última bolilla de una caja, gana una moneda. Hallar el máximo entero $k$, tal que independientemente de cómo juegue Mica, Igna puede ganar por lo menos $k$ monedas.
Notas:
1) Después de que Igna retira una bolilla, queda una cantidad impar de bolillas, por lo que queda una cantidad impar de cajas con un número impar de bolillas.
2) Después de que Mica retira una bolilla, queda una cantidad par de bolillas, por lo que queda una cantidad par de cajas (pudiendo ser 0) con un número impar de bolillas.
Definiciones. Decimos que:
1) una caja es `apropiada` por Mica cuando, después del turno de Mica queda con una cantidad de bolillas par y mayor que 0.
2) una caja es `ganada` por alguno de los dos, cuando gana la moneda por retirar la última bolilla de la caja.
Dicho esto, la estrategia de Mica será:
A) Si Igna retira una bolilla de una caja que tenía cantidad par de bolillas, dejándola en cantidad impar, Mica retira otra bolilla de la misma caja, volviéndola a dejar en cantidad par (pudiendo ser 0).
B) Si Igna retira una bolilla de una caja que tenía cantidad impar de bolillas, Mica retira una bolilla de otra caja que tenga cantidad impar de bolillas (esto lo puede hacer debido a que después de la jugada de Igna siempre queda un número impar de cajas con cantidad impar de bolillas).
Con esta estrategia de Mica, el movimiento en las etiquetas de las cajas será:
Caso A)
La caja en cuestión empieza siendo apropiada por Mica.
1) Si después de que Mica saque la bolilla de esa caja la caja queda con una cantidad par mayor que 0, la caja sigue siendo apropiada por Mica.
2) Si después de que Mica saque la bolilla de esa caja la caja queda vacía, la caja pasa a ser ganada por Mica.
Caso B)
Movimiento de Igna:
1) Si saca una bolilla de una caja con exactamente 1 bolilla, dejándola en 0, esa caja pasa a ser ganada por Igna.
2) Si saca una bolilla de una caja con una cantidad de bolillas impar mayor a 1, dejándola en una cantidad par mayor a 0, esa caja pasa a ser apropiada por Mica.
Movimiento de Mica:
1) Si saca una bolilla de una caja con exactamente 1 bolilla, dejándola en 0, esa caja pasa a ser ganada por Mica.
2) Si saca una bolilla de una caja con una cantidad de bolillas impar mayor a 1, dejándola en una cantidad par mayor a 0, esa caja pasa a ser apropiada por Mica.
Por lo tanto:
1) Todas las cajas apropiadas por Mica terminan siendo ganadas por Mica.
2) En el mejor de los casos para Igna, por cada caja nueva ganada por Igna, hay una nueva caja ganada/apropiada (que de acuerdo al punto anterior termina siendo lo mismo) por Mica.
Luego, con la estrategia de Mica mencionada anteriormente, Igna no puede ganar más cajas que Mica, por lo que puede ganar a lo sumo 15 cajas.
Un ejemplo es 29 cajas con 1 bolilla y una caja con 971 bolillas. En este caso, independientemente de la estrategia de Mica, Igna en sus primeros 15 movimientos puede ganar 1 moneda, asegurándose al menos 15 monedas.
