49th Austrian Mathematical Olympiad, National Competition (Final Round, part 1)

Question

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?

Accepted Answer

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}

.

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

x

modulo 3, but

x

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

x

. After her move, the sum of digits is congruent to

2 x \equiv - x (mod 3)

. In order to get a multiple of 3, Bob would have to choose another

x

, which is prohibited.

Therefore, Bob cannot reach his goal.