Competition problem — Number theory

Library / /470 of 520

Number theory Difficulty 7.3 National olympiad, round 2 Prove it

Two players $A$ and $B$ play the following game. Before the game starts, $A$ chooses 1000 not necessarily different odd primes, and then $B$ chooses half of them and writes them on a blackboard. In each turn a player chooses a positive integer $n$ , erases some primes $p_{1}, p_{2}, \ldots, p_{n}$ from the blackboard and writes all the prime factors of $p_{1} p_{2} \ldots p_{n}-2$ instead (if a prime occurs several times in the prime factorization of $p_{1} p_{2} \ldots p_{n}-2$ , it is written as many times as it occurs). Player $A$ starts, and the player whose move leaves the blackboard empty loses the game. Prove that one of the two players has a winning strategy and determine who.

Remark: Since 1 has no prime factors, erasing a single 3 is a legal move.

Solution

Player $A$ has a winning strategy.

Figure 1

Figure 2

Let player $A$ choose 1000 primes all congruent to 1 modulo 4. Then there are 500 primes congruent to 1 modulo 4 when the game begins. Let $P$ denote the parity of the number of primes congruent to 3 modulo 4 on the blackboard. When the game starts, $P$ is even. Remember that the number of primes congruent to 3 modulo 4 in the prime factorization of a number is even if the number is congruent to 1 modulo 4, and odd if the number is congruent to 3 modulo 4. In each turn the parity of $P$ changes, because the number of primes congruent to 3 modulo 4 among $p_{1}, p_{2}, \ldots, p_{n}$ and in the prime factorization of $p_{1} p_{2} \ldots p_{n}-2$ is of different parity. Hence $P$ is odd after each of $A$ 's turns and even after each of $B$ 's turns, so $A$ cannot lose. Since the product of all the primes on the blackboard decreases with each turn, the game eventually ends, hence $A$ wins.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.