There are 2008 bags numbered from 1 to 2008, with 2008 frogs in each one of them. Two people play in turns. A play consists in selecting a bag and taking out of it any number of frongs (at least one), leaving $ x$ frogs in it ($ x\geq 0$). After each play, from each bag with a number higher than the selected one and having more than $ x$ frogs, some frogs scape until there are $ x$ frogs in the bag. The player that takes out the last frog from bag number 1 looses. Find and explain a winning strategy.
Problem
Source:
Tags: combinatorics proposed, combinatorics
14.06.2008 01:21
By Zermelo's theorem there is a winning strategy, indeed this is a finite (with at most $ 2008^2$ plays), bipersonal game with no tie possiblity. The first player has the winning strategy: As a first move remove $ 2007$ frogs from bag number $ 2$, this will result on $ 2008$ frogs on bag number $ 1$ and $ 1$ frog in the rest of bags. Then there will be $ 2\cdot 2007 +1$ frogs in game. Then continue playing "symmetrically" to the second player: If the second player takes out a frog of bag number $ a + 1$, first player must leave only $ a$ frogs on bag number $ 1$. This results on $ a$ frogs on bag number $ 1$ and $ 1$ frogs in bags $ 2,3,...,a$. If the second player leaves only $ a$ frogs on bag number $ 1$, first player must take out a frog from bag number $ a + 1$, this results the same as the previous consideration. In this way, at every turn beginning with the first play of second player, an even number of frogs are taken out from the bags (or escape...) Continue this process until only $ 1$ frog remais in bag number $ 1$, when this case came it will be the second player the one who moves, so second player loses.
14.06.2008 05:02
This is an instance of the game Chomp -- specifically, it's Chomp for a $ 2008 \times 2008$ rectangle.