Buenas, el pasado fin de semana fue la regional latinoamericana de programación. De los 10 problemas sabemos(mi equipo y yo) más o menos cómo pensar 6, pero hay uno que está de para atrás y al parecer sólo un equipo de Perú pudo resolverlo. El problema, obviando la historia que echan, es que hay n cajas(\( B_1,B_2,...,B_n \)) y un conjunto S de m piedras. Las m piedras están distribuidas en las primeras n-1 cajas.
En cada ronda de un juego, el jugador 1 escoge un subconjunto P de las piedras y el jugador 2 decide o coger el conjunto P o coger el complemento del conjunto P de piedras(Llamémoslo Q). Si decide Coger P lo que hace es eliminar las piedras del conjunto P y a todas las piedras del conjunto Q las mueve una caja a la derecha. Si, en vez, escoje el conjunto Q, elimina esas piedras y mueve las piedras del conjunto P una caja a la derecha(osea que si \( p \in P\cap{B_k} \) entonces quita la piedra p de \( B_k \) y la pone en \( B_{k+1} \) ) El juego se termina cuando al menos una piedra alcanza la caja \( B_n \) en ese caso el jugador 1 gana, o hasta que no haya más piedras, en ese caso gana el jugador 2.
La pregunta es, dado el número de cajas y piedras de cuántas formas se puede hacer la distribución inicial de las piedras en las cajas, de tal forma que si los dos jugadores juegan optimamente, el jugador 2 siempre gane?
Lo ideal es que no me dijeran, si llegan, a la solución. Si no que me den algún hint para poder pensar.
Gracias
Adjunto el problema original.
