Problem

Source: 2012 Baltic Way, Problem 10

Tags: modular arithmetic, number theory, prime factorization, combinatorics unsolved, combinatorics



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$, $\dots$, $p_n$ from the blackboard and writes all the prime factors of $p_1 p_2 \dotsm p_n - 2$ instead (if a prime occurs several times in the prime factorization of $p_1 p_2 \dotsm 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.