Olympiad Maths Prep

Library / /2 of 2

Number theory Difficulty 6.6 National olympiad Prove it Austria

Alice and Bob determine a number with 2018 digits in the decimal system by choosing digits from left to right. Alice starts and then they each choose a digit in turn. They have to observe the rule that each digit must differ from the previously chosen digit modulo 3.

Since Bob will make the last move, he bets that he can make sure that the final number is divisible by 3. Can Alice avoid that?

Solution

It is well-known that every number is congruent to its sum of digits in the decimal system modulo 3. It is therefore sufficient to consider the digits modulo 3. In particular, it is enough to only consider digits in {1,2,3}\{1, 2, 3\}.

In the fourth move from the end, Alice makes sure that the sum of the digits is not divisible by 3 after her move. This is always possible because she has two options which cannot both lead to multiples of 3. After the next move, the sum of digits is congruent to some xx modulo 3, but xx is not the digit chosen by Bob because the sum of digits was not a multiple of 3 before Bob's move.

In the penultimate move, Alice can therefore choose xx. After her move, the sum of digits is congruent to 2xx(mod3)2x \equiv -x \pmod{3}. In order to get a multiple of 3, Bob would have to choose another xx, which is prohibited.

Therefore, Bob cannot reach his goal.

Looking for a route rather than 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.