Mable and Nora play a game according to the following steps in order: 1. Mable writes down any 2015 distinct prime numbers in ascending order in a row. The product of these primes is Marble'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 Marble in step 3 to the number she has written in step 2, and the sum becomes Nora's score. If Marble and Nora's scores have a common factor greater than 1, Marble wins, otherwise Nora wins. Who has a winning strategy?
Problem
Source:
Tags: number theory, prime numbers
10.01.2016 20:03
i think this is the answer but i cant quite prove it
01.02.2016 05:04
My solution: We will show Nora has a winning strategy; that is, she can find a suitable positive integer $n$, so that for any $p_1<p_2<....<p_{2015}$, the numbers $n+p_1, n+p_1p_2, ... n +p_1p_2...p_{2015}$ are each relatively prime to $m=p_1p_2...p_{2015}$. It suffices to determine $n$ mod each $p_i, 1 \le i \le 2015$, and then use CRT. Now modulo each $p_i$, we need $n, n+p_1, n+p_1p_2, ... n+p_1p_2...p_{i-1} \neq 0$ mod $p_i$. Let $X$ be the set of all residues relatively prime to $p_i$ (taken mod $p_i$). Essentially, we need $X \cap \{X-p_1\} \cap \{ X-p_1p_2\} \cap ... \cap \{X-p_1p_2...p_{i-1}\} \neq \emptyset$, where $\{X-a\}$ means subtracting $a$ from each element of $X$ and then take mod $p$. Note that $|\{X-a\}| = p_i-1$ for each $a$. It follows that $|S \cap \{X- a\}| \ge |S|-1$ for each $a,S$ as we can only "lose" one residue each time. Then $|X \cap \{X-p_1\} \cap \{X-p_2\} \cap ... \cap \{X-p_1p_2...p_{i-1} \} | \ge |X| - (i-1) = p_i-i$. Showing this is $\ge 1$ is equivalent to showing $p_i \ge i+1$ which is trivial. Thus we are done. One question- is the Hong Kong TST2 2016 only four questions, or have problems 5/6 not been released yet? If this is the final one out of four problems it seems quite easy...