Given 2015 balls. Astri and Budi will play a game. At first, Astri will choose two different numbers $a$ and $b$ from the set $S = \{ 1, 2, 3, \dots, 30 \}$. Budi will then choose another 2 different numbers $c$ and $d$ from the remaining 28 numbers in set $S$. By taking turns, starting from Astri, they take balls with the following rules: (1) Astri could only take $a$ or $b$ balls. (2) Budi could only take $c$ or $d$ balls. until someone couldn't take any balls satisfying the condition given (and that person will lose). Prove that Budi could choose $c,d$ such that he has a strategy to ensure his victory on this game.
Problem
Source: INAMO 2015 Shortlist C9
Tags: combinatorics, Game Theory
bruckner
30.12.2018 13:13
I don't think that's right... $a=26$ and Astri wins.
GorgonMathDota
30.12.2018 13:21
bruckner wrote: I don't think that's right... $a=26$ and Astri wins. Could you elaborate more? What numbers does Astri choose and how does she win?
Seicchi28
21.05.2019 07:42
If $a+b \neq 31$, Budi chooses $c = 31-a$, $d = 31-b$. If Astri takes $a$ balls, Budi takes $c$ balls in the next step. Else, he takes $d$ ball. By following this procedure, the number of balls will always be decreased by 31 after one round of their turn. Since $2015 = 5 \times 13 \times 31$, $31$ divides $2015$. It is easy to see that Budi will win because at some point Astri will have no balls to take and therefore couldn't move.
Now if $a+b = 31$, without losing generality suppose $b \le 15 < 16 \le a$ and divide into cases. (The strategy is still same; if Astri takes $a$ balls Budi takes $c$ balls, else $d$.
$15\ge b \ge 14$. Take $(c,d) = ( 26-a, 26-b )$. After one round, number of balls modulo 26 is preserved. Since $2015\mod 26 \equiv 13$, eventually there are $13$ balls and Astri couldn't move.
$13 \ge b \ge 6$. Take $(c,d) = ( 30-a, 30-b )$. Number of balls modulo 30 is preserved. Since $2015 \mod 30 \equiv 5$, eventually there are $5$ balls and Astri couldn't move.
$5 \ge b \ge 3$. Take $(c,d) = ( 33-a, 33-b )$. Number of balls modulo 33 is preserved. Since $2015 \mod 33 \equiv 2$, eventually there are 2 balls and Astri couldn't move.
$b=2,a=29$. Take $(c,d) = ( 38-a, 19-b ) = ( 9,17 )$. The number of balls modulo 19 is preserved. Since $2015 \mod 19 \equiv 1$, eventually there are $20$ or $39$ balls. It's easy to check at the end there will be $1$ ball, and Astri couldn't move.
$b=1,a=30$. Take $(c,d) = ( 9,12 )$. Number of balls modulo 13 is preserved. If there are $13$ or $26$ balls left, Astri could only take one and Budi will take $12$ after that. All cases lead to no ball left right before Astri's turn, so Astri couldn't move.