Amy and Bob choose numbers from $0,1,2,\cdots,81$ in turn and Amy choose the number first. Every time the one who choose number chooses one number from the remaining numbers. When all $82$ numbers are chosen, let $A$ be the sum of all the numbers Amy chooses, and let $B$ be the sum of all the numbers Bob chooses. During the process, Amy tries to make $\gcd(A,B)$ as great as possible, and Bob tries to make $\gcd(A,B)$ as little as possible. Suppose Amy and Bob take the best strategy of each one, respectively, determine $\gcd(A,B)$ when all $82$ numbers are chosen.
Problem
Source: CSMO 2019 Grade 11 Problem 7
Tags: combinatorics, Combinatorial games
31.07.2019 22:36
In this solution Bob$:=$ Ben. The answer is $\gcd(A,B)=41$. Note that $A+B=1+2+...+81=81\cdot 41$, and from Euclidean Algorithm we have $$\gcd(A,B)=\gcd(A,A+B)=\gcd(A,3^4\cdot41) \mid 3^4\cdot41$$ Claim. Ben can make $A,B$ not divisible by $3$. Proof: Divide the numbers in $14$ sets in this way, $A_1=\{0,1,2,3\} , A_2=\{4,5,6,7,8,9\}, \dots, A_{14}=\{76,77,78,79,80,81\}$ where all $A_i$'s have $6$ consecutive numbers for $i>1$. Whenever Amy takes a number from the set $A_i$, Ben is going to take the other number from that set. For $A_1$, whenever Amy takes a number divisible by $3$ then Ben takes another number divisible by $3$, so when all elements of $A_1$ are taken both sums are not divisible by $3$. For $A_i$, $i\geq 2$, whenever Amy takes a number of the form $3k+l$ then Ben is going to take a number of the same form, this keeps both sums of numbers Amy and Ben got from this set divisible by $3$. Finally, after adding all sums of these sets we get that $A,B$ are not divisible by $3$. $\blacksquare$ Claim. Amy can make both $A,B$ divisible by $41$. Proof: Write the $82$ numbers as two sets of complete residues $\pmod {41}$. Amy takes the first number randomly, if Ben takes the same number then Amy takes another random number and we do this procedure till Ben takes a number different from Amy's, then Amy takes the same number Ben took and repeat till Ben then takes a number Amy took, then we start again with Amy taking another random number. This procedure ensures that both Amy and Ben will take each residue exactly once. So we have $$A\equiv B\equiv 0+1+2+...+40\equiv 41 \cdot 20 \equiv 0 \pmod {41}$$$\blacksquare$
05.08.2019 21:52
Here is an alternative winning strategy for Ben. First, he pairs up the numbers into the pairs $(0, 1), (2, 3), \cdots, (80, 81).$ Then, whenever Amy takes a number in a pair, Ben takes the one which is paired with it. In this way, he ensures that $B$ is in the interval $[0+2+4+ \cdots + 80, 1 + 3 + \cdots + 81].$ If we let $S = 0+1+2 + \cdots + 81$ be the sum of all numbers ($A+B$), then we have $\gcd(A, B) = \gcd(A+B, B) = \gcd(S, B) \le \gcd(S, 2B) = \gcd(S, S-2B).$ However, as $S-2B$ is an odd number in the interval $[-41, 41]$, we must have $\gcd(A, B) \le 41$ as desired. $\square$