General Tilly and the Duke of Wallenstein play "Divide and rule!" (Divide et impera!). To this end, they arrange $N$ tin soldiers in $M$ companies and command them by turns. Both of them must give a command and execute it in their turn. Only two commands are possible: The command "Divide!" chooses one company and divides it into two companies, where the commander is free to choose their size, the only condition being that both companies must contain at least one tin soldier. On the other hand, the command "Rule!" removes exactly one tin soldier from each company. The game is lost if in your turn you can't give a command without losing a company. Wallenstein starts to command. a) Can he force Tilly to lose if they start with $7$ companies of $7$ tin soldiers each? b) Who loses if they start with $M \ge 1$ companies consisting of $n_1 \ge 1, n_2 \ge 1, \dotsc, n_M \ge 1$ $(n_1+n_2+\dotsc+n_M=N)$ tin soldiers?
Problem
Source: Germany 2017, Problem 3
Tags: Game Theory, combinatorics, Combinatorial games, game, game strategy
04.05.2017 16:37
Answer of part a: NO Solution: Here whenever Tilly chooses to give command "Divide!", the Duke would also give command "Divide!" and divide one of the companies with one of them containing 1 tin soldier so that command "Rule!" cannot be given If Tilly chooses to give command "Divide!", the Duke would also give command "Divide!" and divide one of the companies with one of them containing 1 tin soldier . Clearly, now the command "Rule!" cannot be given. So they continuously divide the companies till all the companies have 1 tin soldier. This would take (including Tilly's 1st turn) $6 \times 7=42$ moves, so the last move would be performed the Duke, which would imply that the Duke has won. If Tilly chooses to give command "Rule!", the Duke would also give command "Rule!". If Till never gives command "Divide!", he will obviously loose, so he gives the command "Divide!". As the turns including Tilly's "Divide!" is always even( like $6 \times 7=42$, $64 \times 7=28$, $2 \times 7=14$)
08.05.2017 19:25
For a) Claim: If the Duke starts the game, then no matter how he plays, Tilly will always have a winning strategy. Proof of the claim: Call a company 'even' if it has an even no. of tin soldiers, otherwise 'odd'. To win the game, all Tilly needs to do is to make all 'even' companies 'odd' in each of his move. We shall now show that Tilly can always make this move. In his first move, if the Duke gives the command "Rule", then Tilly will be left with only 'even' companies and so, he can make his desired move by using the command "Rule". Suppose in his first move, the Duke gives the command "Divide". It is easy to notice that the partition of an odd number into two numbers will incude two numbers of opposite parity. Since $7$ is odd, so Tilly will be left with an 'even' company in his turn and so he can easily make the desired move. Using analogous logic, it can be seen that after each move of the Duke, Tilly will always be left with atleast one 'even' company and so the game will go in his favour. Hence, required answer is "NO". P.S.- In fact, whenever $n $ is odd, and there are $M $ companies consisting of $n $ tin soldiers each, then Tilly always has a winning strategy.
26.05.2021 12:59
surprisingly easy. only the answer for part b Context: Tilly is replaced by Sunny, and ruling soldiers is replaced by eating chocolate, and the answer is the condition when Tilly wins.
Attachments:
