Maths Olympiad Prep

Library / /27 of 27

Number theory Difficulty 7.5 National olympiad, round 2 Prove it Austria

Anna, Berta and Clara write the square numbers 1,4,9,,20251, 4, 9, \dots, 2025 on a blackboard, compute their sum and observe that it is divisible by 33. Then, they agree to the following game: In each round, Anna will cross out one number, then Berta will do the same, and then Clara will do the same. This continues until all numbers are crossed out. Clara has the goal that the sum of the remaining numbers after each round is divisible by 33.

a) Prove that Anna cannot stop Clara from reaching her goal if Clara has Berta's help.

b) Prove that Berta can stop Clara from reaching her goal even if Clara has Anna's help.

(Richard Henner)

Solution

On the blackboard, we have 1515 integers with residue 00 modulo 33 and 3030 integers with residue 11 modulo 33. If, in a certain round, Berta and Clara cross out numbers that have the same residue modulo 33 as the number crossed out by Anna, then they have removed either 0+0+00+0+0 or 1+1+11+1+1 modulo 33.

In both cases, the sum does not change modulo 33 and therefore remains divisible by 33. Since 1515 and 3030 are multiples of 33, it is possible for Berta and Clara to always choose the same residue as Anna. Therefore, Anna cannot stop Clara from reaching her goal if Clara has Berta's help.

However, if Berta chooses in the first round a residue modulo 33 that is different from the one chosen by Anna, they have crossed out 0+10+1 or 1+01+0 modulo 33. Therefore, Clara's only choices for the sum of the remaining numbers after the first round are 11 or 22 modulo 33. In both cases, the sum is not divisible by 33. Therefore, Clara has failed in her goal already in the first round if Berta plays uncooperatively.

(Richard Henner) ☐

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.