MathDB
Game with Primes

Source: 2012 Baltic Way, Problem 10

November 22, 2012
modular arithmeticnumber theoryprime factorizationcombinatorics unsolvedcombinatorics

Problem Statement

Two players AA and BB play the following game. Before the game starts, AA chooses 1000 not necessarily different odd primes, and then BB chooses half of them and writes them on a blackboard. In each turn a player chooses a positive integer nn, erases some primes p1p_1, p2p_2, …\dots, pnp_n from the blackboard and writes all the prime factors of p1p2⋯pn−2p_1 p_2 \dotsm p_n - 2 instead (if a prime occurs several times in the prime factorization of p1p2⋯pn−2p_1 p_2 \dotsm p_n - 2, it is written as many times as it occurs). Player AA 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.
Back to ProblemsView on AoPS