Maths Olympiad Prep

Library / /147 of 155

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it Saudi Arabia

On the table, there are 10241024 marbles and two students A,BA, B alternatively take a positive number of marble(s). The student AA goes first, BB goes after that and so on. On the first move, AA takes kk marbles with 1<k<10241<k<1024. On the moves after that, AA and BB are not allowed to take more than kk marbles or 00 marble. The student who takes the last marble(s) on the table will be the winner. Find all values of kk the student AA should choose to make sure that there is a strategy for him to win the game.

Solution

After the first move, there are 1024k1024-k marbles remaining and both students A,BA, B cannot take more than kk marbles during their turn.

We shall prove that if k+11024kk+1 \mid 1024-k then the student AA will have the strategy to win the game.

Indeed, let 1024k=m(k+1)1024-k = m(k+1) with mZ+m \in \mathbb{Z}^{+}. On each turn, if BB chooses xx marble(s) then AA will choose k+1xk+1-x marble(s) on his next turn. Since x{1,2,3,,k}x \in \{1,2,3, \ldots, k\} then k+1x{1,2,3,,k}k+1-x \in \{1,2,3, \ldots, k\} which implies that AA always can perform his turn. After mm turns of AA and mm turns of BB, student AA takes the last marble then wins the game.

If 1024k1024-k is not divisible by k+1k+1 then we put 1024k=m(k+1)+n1024-k = m(k+1) + n with 0<n<k+10 < n < k+1. In this case, the student BB can take nn marbles on the next turn. The number of remaining marbles is m(k+1)m(k+1) then by applying the same argument above, the student BB has the strategy to win the game.

Hence, the condition we have to find is k+11024kk+1 \mid 1024-k or k+11025k+1 \mid 1025. Note that the divisors of 10251025 are 1,5,25,41,205,10251,5,25,41,205,1025 then
k+1{1,5,25,41,205,1025} and 0<k<1024. k+1 \in \{1,5,25,41,205,1025\} \text{ and } 0<k<1024.
This means that all values of kk we need to find are 4,24,40,2044,24,40,204.

\square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.