Maths Olympiad Prep

Library / /39 of 48

, 2016

Number theory Difficulty 6.5 National Olympiad Prove it Hong Kong

Mable and Nora play a game according to the following steps in order.
(1) Mable writes down any 20152015 distinct prime numbers in ascending order in a row. The product of these primes is Mable's score.
(2) Nora writes down a positive integer.
(3) Mable draws a vertical line between two adjacent primes she has written in step (1), and compute the product of the prime(s) on the left of the vertical line.
(4) Nora must add the product obtained by Mable in step (3) to the number she has written in step (2), and the sum becomes Nora's score.
If Mable's and Nora's scores have a common factor greater than 11, Mable wins. Otherwise Nora wins.
Who has a winning strategy?

Solution

Nora has a winning strategy.
Let Mable write down p1<p2<<p2015p_1 < p_2 < \dots < p_{2015} in step (1). Then P=p1p2p2015P = p_1p_2\dots p_{2015} is Mable's score.
Let qk=p1p2pkq_k = p_1p_2\dots p_k for each kk. Nora needs to write down a positive integer QQ in step (2) such that (P,Q+qj)=1(P, Q + q_j) = 1 for all jj. Indeed, for each 1k20151 \le k \le 2015, we choose rkZr_k \in \mathbb{Z} such that
rkqj(modpk) r_k \ne -q_j \pmod{p_k}
for all 1j20151 \le j \le 2015. Such an rkr_k exists because there are at most k<pkk < p_k residues that rkr_k cannot take (as pkqjp_k \mid q_j if jkj \ge k).

Now, there exists QZ+Q \in \mathbb{Z}^+ such that Qrk(modpk)Q \equiv r_k \pmod{p_k} for all kk by the Chinese remainder theorem. For this choice of QQ, we have
Q+qjrk+qj≢0(modpk) Q + q_j \equiv r_k + q_j \not\equiv 0 \pmod{p_k}
for any jj and kk. Therefore, we have (P,Q+qj)=1(P, Q + q_j) = 1 for all jj as desired.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.