Maths Olympiad Prep

Library / Hong Kong competition problems /34 of 42

Hong Kong competition problems, 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=p1p2…p2015P = p_1p_2\dots p_{2015} is Mable's score.
Let qk=p1p2…pkq_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 1≤k≤20151 \le k \le 2015, we choose rk∈Zr_k \in \mathbb{Z} such that
rk≠−qj(modpk) r_k \ne -q_j \pmod{p_k}
for all 1≤j≤20151 \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 pk∣qjp_k \mid q_j if j≥kj \ge k).

Now, there exists Q∈Z+Q \in \mathbb{Z}^+ such that Q≡rk(modpk)Q \equiv r_k \pmod{p_k} for all kk by the Chinese remainder theorem. For this choice of QQ, we have
Q+qj≡rk+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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.