Anselmo and Claudio are playing alternatively a game with fruits in a box. The box initially has $32$ fruits. Anselmo plays first and each turn consists of taking away $1$, $2$ or $3$ fruits from the box or taking away $\frac{2}{3}$ of the fruits from the box (this is only possible when the number of the fruits left in the box is a multiple of $3$). The player that takes away the last fruit from the box wins. Which of these two players has a winning strategy? How should that player play in order to win?
Problem
Source: Lusophon Mathematical Olympiad 2022 Problem 2
Tags: combinatorics, Game Theory
09.12.2022 22:43
32 = 4 × 8, and our special, "magic" number for this game is 4. Why? 4 = 1 + 3 = 2 + 2 = 3 + 1 Therefore, if this game has no provision of "2/3 takings for multiples of 3 fruits in the box", Claudio would be the one with the advantage of this particular game since he can always keep the number even (at multiples of 4) by taking the complementary of 4 (that is 4 — x) to any selection x (of 1 or 2 or 3) that Anselmo opt for. However, the slight twist in game's rule changes the play. 24 and 12 are multiples of both 4 and 3 (which are less than 32, of course), so if Claudio sticked to his strategy above, at these two turns, Anselmo may (or may not) choose to take 16 or 8 respectively. Doing this won't change the "0 mod 4" state at all (with remainders being 8 or 4), but it swaps the roles between the players since Claudio will be stucked at a position where he starts with 0 mod 4 state (before taking his fruit selection in that turn) for a change instead of his previous role of returning it to 0 mod 4 as the winning strategy. Sure Claudio can choose other numbers which won't make him leave 24 (or 12) fruits in the box, but picking a random number won't guarantee him a win as the 0 mod 4 strategy could give before. Anyway, if we look at it objectively, we found : 1) without the twist, players would prefer to leave multiples of 4 in the box (attracted to 28, 24, 20, 16, 12, 8, 4 and the final winning 0) 2) with the twist, players would avoid leaving multiples of 4 which are also multiples of 3 in the box (so no 24 nor 12, ever) while other multiples of 4 less than 12 is very desirable (any earlier / bigger multiples of 4 is useless since the flow would be broken by both 24 and 12) 3) so in the second case, we have a series of "undesirables" from 12, 11, 10 and 9 4) the only way to win is forcing the opponent's hand into choosing one of the 4 undesirables, and it's only possible when the winning player can leave 13 fruits in the box 5) as 13 = 1 mod 4, it's an automatic win for Anselmo since he gets the first hands on the fruits; takes 3 out of it and leaves 32 — 3 = 29 mod 4 = 1 mod 4 in, and he can keep doing it (the 1 mod 4 strategy) up until only 13 fruits are left for Claudio 6) even if Anselmo might encounter 1 mod 4 numbers which are also multiples of 3 like 21 (or 9, but 9 is already an identified "undesirable" less than our critical number of 13), but 1 — 2/3 = 1/3 of those numbers are not multiples of 4 and already less than 13; all Anselmo has to do in the very next turn is change his strategy and take up the 0 mod 4 to replace the previous one of 1 mod 4 Answer : Anselmo is the winner, take 3 first, keep the 1 mod 4 until he can leave 13 fruits for Claudio, go 2/3 if Claudio took 1 fruit or go for 8 otherwise, and keep the 0 mod 4 up until the very end.
29.05.2023 14:00
Once that the numbers are very small, we can trivially realize that work with loser/winner positions will do the trick. We denote by L, a loser position, defined by not being able to place your opponent on another loser position. We also use W to express a winner position, where the player can return the play to the opponent on a loser position. Small cases: 0- Loser by definition 1- Winner ‘cause you can place your opponent in zero by taking 1 stone 2- W (take 2) 3- W (take 3) 4- L(can only leave your opponent on winner positions 1 2 or 3) 5- W (take 1) 6- W(take 2) 7- W(-3) 8- L 9-W(-1) 10-W(-2) 11-W(-3) 12-W(-2/3) 13-L We realize that in a pile with n stones, if n is divisible by four(congruent to zero mod 4) it is a loser position, and it has three winner positions after. Nevertheless, if n is a multiple of twelve, it “delays” the loser position by one. So for any n, it is a loser position if and only if it is congruent mod 4 to the floor of n/12. Otherwise, it’s a winner position. We can also work manually the W/L positions, arriving that Anselmo has the winning strategy