Maths Olympiad Prep

Library / /4 of 4

Combinatorics Difficulty 7.9 National olympiad, round 2 Prove it Silk Road Mathematics Competition

An odd integer a>1a > 1 is given. Initially, Basil chooses an even positive integer bb such that b<ab < a and tells it to Pete. Basil then writes down three integers on a blackboard. After that, Pete makes a sequence of moves. By a move, Pete can either add aa to one of the numbers on the blackboard, add bb to the second number, and subtract a+b+1a+b+1 from the third number, or, conversely, subtract aa from one number on the blackboard, subtract bb from the second number, and add a+b+1a+b+1 to the third one. At each move, Pete can independently choose which number on the blackboard is the first, the second, and the third. Pete wins if, after some moves, all three numbers on the blackboard are zero. For which aa Basil cannot prevent Pete's win?

Solution

Answer. a=4n13a = \frac{4^n - 1}{3} for an integer n>1n > 1 and a=2p13a = \frac{2p-1}{3}, where pp is an odd prime number (necessarily having remainder 2 when divided by 3).

We start with describing the set of pairs (a,b)(a, b) for which Pete can win.

Lemma.
(a) If gcd(2a+b+1,ab)>1\gcd(2a + b + 1, a - b) > 1, then Pete cannot win.
(b) If gcd(2a+b+1,ab)=1\gcd(2a + b + 1, a - b) = 1, then Pete can win.

Proof.
(a) Set d=gcd(2a+b+1,ab)>1d = \gcd(2a+b+1, a-b) > 1. Then we have b=a(ab)a(modd)b = a - (a-b) \equiv a \pmod d and (a+b+1)=a(2a+b+1)a(modd)-(a+b+1) = a - (2a+b+1) \equiv a \pmod d. This means that, on each move, all three numbers on the blackboard increased by aa modulo dd (or, conversely, decreased by aa modulo dd). Hence, if the three numbers written by Basil are not all congruent modulo dd, then this property will be preserved during Pete's moves, so that they will never be all equal (so they will never become all zero).

(b) Let x,y,zx, y, z be three numbers on the blackboard at some moment. Then Pete can perform, by several moves, any of the following operations:

1. To yield numbers x+(ab)x + (a-b), y(ab)y - (a-b), and zz. For this purpose, he can add aa to the first number and bb to the second number, and then subtract aa from the second number and bb from the first one.

2. To yield numbers x(2a+b+1)x - (2a + b + 1), y+(2a+b+1)y + (2a + b + 1), and zz. For that, he can subtract aa from the first number and add a+b+1a+b+1 to the second one, and then subtract a+b+1a+b+1 from the first number and add aa to the second one.

3. To yield numbers x+1x + 1, y1y - 1, zz. Indeed, since 2a+b+12a + b + 1 and aba - b are coprime, there exist positive integers uu and vv such that u(ab)v(2a+b+1)=1u(a - b) - v(2a + b + 1) = 1. Applying operation 1 uu times and operation 2 vv times, Pete gets the desired situation.

4. Pete can, by one move, either decrease the sum of all numbers by 1 (using the first described move) or increase that sum by 1 (using the second move).

Performing operations 3 and 4, Pete can reach his goal: first, using operation 4, he gets three numbers summing up to zero; then, using operation 3, he makes one number on the blackboard zero, and then another number becomes zero. Since the sum of numbers on the blackboard does not change during these operations, the third number also vanishes at the end. \square

Due to the lemma, an odd number a>1a > 1 satisfies the requirements if and only if the following condition holds:

(*) For every even b<ab < a, the numbers aba-b and 2a+b+12a+b+1 are coprime.

Notice that
gcd(ab,2a+b+1)=gcd(ab,2a+b+1+(ab))=gcd(ab,3a+1). \gcd(a - b, 2a + b + 1) = \gcd(a - b, 2a + b + 1 + (a - b)) = \gcd(a - b, 3a + 1).
Notice also that the number aba-b runs over all odd positive integers smaller than aa. Therefore, property (*) is equivalent to the fact that the number 3a+13a+1 is coprime to any odd positive integer smaller than aa; or, in other words, that 3a+13a+1 has no odd divisors smaller than aa and greater than 11 — let us call such divisors bad.

Notice that the number 3a+13a+1 is even; then 3a+1=2k3a+1 = 2^k\ell, where kk is a positive integer, and \ell is an odd positive integer. If k2k \ge 2 and >1\ell > 1, then 3a+14<a\ell \le \frac{3a+1}{4} < a is a bad divisor. If \ell is composite, i.e., =12\ell = \ell_1\ell_2 with 1,23\ell_1, \ell_2 \ge 3, then 1=3a+12k23a+16<a\ell_1 = \frac{3a+1}{2^k\ell_2} \le \frac{3a+1}{6} < a is a bad divisor.

The remaining cases are (1) =1\ell = 1, and (2) k=1k = 1 and \ell is a prime number. It is easy to see that, in both cases, 3a+13a+1 has no bad divisors. Therefore, the desired cases are precisely 3a+1=2k3a+1 = 2^k and 3a+1=2p3a+1 = 2p, where pp is a prime. Checking modulo 3 it follows that kk is even in the former case, and \ell has a remainder 2 when divided by 3 in the latter. The result follows.

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.