Maths Olympiad Prep

Library / /209 of 299

Combinatorics Difficulty 6.9 National Olympiad Prove it Iran

Let us denote by Ω(n)\Omega(n) and ω(n)\omega(n) the largest and the smallest prime divisors of nn, respectively. Alireza and Amin decided to play the following game. Starting with Alireza, he chooses 1400 polynomials with integer coefficients. Then, Amin chooses 700 polynomials among them and denotes their sets by AA and BB, respectively. Amin shall win the game if for each positive integer nn
max{PA}(Ω(P(n)))min{QB}(ω(Q(n))), \max_{\{P \in A\}}(\Omega(P(n))) \geq \min_{\{Q \in B\}}(\omega(Q(n))),
otherwise, Alireza shall win the game. Which player has the winning strategy?

Solution

Let us denote by A1,,ANA_1, \dots, A_N all the 700-element subsets of {1,2,,1400}\{1, 2, \dots, 1400\}. Let N=(1400700)N = \binom{1400}{700}. Now, choose 1400 polynomials P1,,P1400P_1, \dots, P_{1400} of the following form:
Pi(x)=1+10101jN, jAi(xj). P_i(x) = 1 + 10^{10} \prod_{1 \le j \le N,\ j \in A_i} (x - j).
We now claim that if Alireza chooses these 1400 polynomials, he shall win the game. Assume that Amin chooses 700 polynomials Pi1,,Pi700P_{i_1}, \dots, P_{i_{700}}. Let us denote by AlA_l the set {i1,,i700}\{i_1, \dots, i_{700}\}. Then, for all iAli \in A_l we have Pi(l)=1P_i(l) = 1 hence Ω(Pi(l))=1\Omega(P_i(l)) = 1. Otherwise, Pi(l)=1+1010KiP_i(l) = 1 + 10^{10} K_i then Pi(l)>2|P_i(l)| > 2 and hence ω(Pi(l))2>1\omega(P_i(l)) \ge 2 > 1.

Hence, for n=ln = l;
1=maxiAl(Ω(Pi(l)))<miniAl(ω(Pi(l))). 1 = \max_{i \in A_l} (\Omega(P_i(l))) < \min_{i \notin A_l} (\omega(P_i(l))).
Thus, by choosing such polynomials, Alireza shall win.

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.