Assume $\Omega(n),\omega(n)$ be the biggest and smallest prime factors of $n$ respectively . Alireza and Amin decided to play a game. First Alireza chooses $1400$ polynomials with integer coefficients. Now Amin chooses $700$ of them, the set of polynomials of Alireza and Amin are $B,A$ respectively . Amin wins if for all $n$ we have : $$\max_{P \in A}(\Omega(P(n))) \ge \min_{P \in B}(\omega(P(n)))$$Who has the winning strategy. Proposed by Alireza Haghi
Problem
Source: Iranian TST 2021, first exam day 2, problem 4
Tags: number theory, polynomial, prime numbers, function, algebra, Combi
17.05.2021 18:11
So the question is who has the winning strategy, right?. Also it is P(n) on both side, not n.
17.05.2021 18:16
Justanaccount wrote: So the question is who has the winning strategy, right? Thanks! Edited @below ,read more carefully
17.05.2021 18:24
By the way, I think the problem is wrong because of course LHS >= RHS. Even if it is P(n) for both side, the problem is still wrong because if p is the biggest prime of the 700 polynomials, it is bigger than the smallest prime of the 700 polynomials, and of course bigger than the smallest prime of the 1400 polynomials.
22.05.2021 15:42
Switch Alireza and Amin to players A and B respectively. A chooses 1400 polynomials satisfying the next conditions: for some fixed integers $a_1, a_2,...,a_m$ (let $m$ be even) and for every polynomial $Q(x)$ ( from these 1400) it is either $Q(a_i)=1$ or $Q(a_i)=p$ where $p$ is some prime the value of which we will clarify later(note, that A can choose such polynomials by Lagrange interpolation theorem). The important thing is that A chooses polynomials such that for every 700 polynomials there exists some $a_i$ that all these 700 polynomials will be equal to 1 and all left 700 polynomials will be equal to $p$ at this $a_i$, and player A ALWAYS can do it by Lagrange theorem. This guarantees us if B chose some 700 polynomials there will be a value $n$ that all his polynomials will be equal to 1 and polynomials of $A$ - to $p$, at this value, so $$\max_{P \in B}(\Omega(P(n)))=1 \ge \min_{P \in A}(\omega(P(n)))=p$$- contradiction and B loses. Now I stupidly thought it was the end but thanks to ilya_math for noticing that this is not a complete solution because we can`t guarantee that these polynomials are with integer coefficients! Now, we must choose such prime $p$ that there will exist polynomials satisfying the conditions above. We`ll show how to choose such $p$ that there will exist one polynomial with integer coefficients and then similarly do it for others. Integers $x_1,x_2,...,x_k, y_1,...,y_k$ are all from the set $(a_1,a_2,...,a_m)$ and $2k=m$. By Dirichlet theorem there exist prime p such that $p\equiv 1\ mod |{(x_1-x_2)(x_1-x_3)...(x_1-x_k)(x_2-x_1)(x_2-x_3)...(x_i-x_1)...(x_i-x_{i-1})(x_i-x_{i+1})...(x_k-x_{k-1})(y_1-y_2)...(y_i-y_{i-1})(y_i-y_{i+1})...(y_k-y_{k-1})}|$. $1$)By Lagrange theorem there exist a polynomial $R(x)$ such that $R(x_i)=0$ and $R(y_i)=p-1$. From interpolation formula we get that $R(x)$ is a polynomial with integer coefficients because $(x_j-x_1)(x_j-x_2)...(x_j-x_k)$ divides $p-1$ for all $j$ from ($1;k$) and similarly $(y_j-y_1)(y_j-y_2)...(y_j-y_k)$ divides $p-1$ (it obviously follows from $p\equiv 1\ mod |{(x_1-x_2)(x_1-x_3)...(x_1-x_k)(x_2-x_1)(x_2-x_3)...(x_i-x_1)...(x_i-x_{i-1})(x_i-x_{i+1})...(x_k-x_{k-1})(y_1-y_2)...(y_i-y_{i-1})(y_i-y_{i+1})...(y_k-y_{k-1})}|$.), so all $z_il_i=0$ or $z_il_i=Q_i(x)$ where $Q_i(x)$ is a polynomial with integer coefficients ($l_i$ was taken from here :https://en.wikipedia.org/wiki/Lagrange_polynomial#Definition and $z_i$ are either 0 or $p-1$, (in Wikipedia it`s noted as $y_i$)). So this guarantees us that $R(x)$ is a polynomial with integer coefficients. Now just take $P(x)=R(x)+1$ and $P(x)$ is the polynomial satisfying the conditions above. $\blacktriangle$ Now, just 'swap' the values in $R(x)$ ( I mean take polynomial $R_1(x)$ such that $R_1(x_{i_1})=0, R_1(x_{i_2})=0,...R_1(x_{i_k})=0,R_1(y_{i_1})=p-1,R_1(y_{i_2})=p-1,...,R_1(y_{i_k})=p-1$ for some other $x_{i_1},x_{i_2},...,x_{i_k},y_{i_1},y_{i_2},...,y_{i_k}$ from the set $(a_1,a_2,...,a_m)$) and we can apply similar arguments as in $1$) and take polynomial $P_1(x)=R_1(x)+1$ and get another polynomial, different from $P(x)$, satisfying the conditions. Then 'swap' it again and again and for big enough $m$ we will get 1400 polynomials with integer coefficients and satisfying the conditions and different from each other, so we are done and A indeed has a winning strategy. $\blacksquare$
22.05.2021 21:04
Congratulations to above's great solution. I just formulated a bit to make it more readable. Let $M=\binom{1400}{700}$ and $N=\binom{1399}{699}=\frac{M}{2}$ . Pick any set $A$ of $M$ distinct positive integers: $A=\{ a_1, a_2, \cdots, a_M \}$. Clearly, there exists a natural bijection $f$ from $A$ to all $700 ~ \text{- element}$ subsets of $\{1,2, \cdots, 1400 \}$. Let $Q= \mid \prod_{1 \le k < \ell \le 1400} (a_k-a_{\ell} ) \mid$ . By Dirichlet Theorem, there exist a prime $p$ such that $p \equiv 1 \pmod Q$. For fixed $1 \le j \le 1400$, $j$ is contained in exactly $=\binom{1399}{699}=N$ $700 ~ \text{- element}$ subsets of $\{1,2, \cdots, 1400 \}$. Let $$X_j := \{ f^{-1} (S) : j \in S \subset \{1,2,\cdots, 1400 \} , |S|=700 \}$$be set of their corresponding "$a_i$s". Clearly, $|X_j|=N=\frac{M}{2}$ . Using Lagrange interpolation formula, there exists a polynomial $R_j(x) \in \mathbb{Q} [x] $, such that $$ R_j(a_i) = \begin{cases} ~ 0 , & ~ \text{if} ~ a_i \in X_j , \\ ~p-1 , & ~ \text{if} ~ a_i \notin X_j . \end{cases} $$ To be more specific, $$ R_j(x)=\sum_{k=1}^{M} R_j(a_k) \prod_{1 \le i \le M, i \neq k} \frac{x-a_i}{a_k-a_i} .$$ Because all $R_j(a_k)$ are divisible by $Q$, hence, by the definition of $Q$, we actually have $R_j(x) \in \mathbb{Z} [x]$ . Let $P_j(x)=R_j(x)+1$, we have $$ P_j(a_i) = \begin{cases} ~ 1 , & ~ \text{if} ~ a_i \in X_j , \\ ~p , & ~ \text{if} ~ a_i \notin X_j . \end{cases} $$ Now, Alireza chooses $1400$ polynomials $P_1(x), P_2(x), \cdots, P_{1400}(x)$. Let Amin chooses $700$ of them, called $A$; other $700$ polynomials are called $B$. Let $I= \{ j : 1 \le j \le 1400, P_j \in A \}$ be the set of index of polynomials in $A$. Then $I$ is a $700 ~ \text{- element}$ subset of $\{1,2, \cdots, 1400 \}$, so it is mapped to an element $a_t := f^{-1} (I) \in A$. By the definition of polynomials, For $P_j \in A$, i.e. $j \in I$, we have $a_t \in X_j$, so $P_j(a_t)=1$. For $P_j \in B$, i.e. $j \notin I$, we have $a_t \notin X_j$, so $P_j(a_t)=p$. Hence $\max_{P \in A}(\Omega(P(a_k))) =1 < p= \min_{P \in B}(\omega(P(a_t)))$ . Therefore, Alireza wins.
08.06.2021 08:09
There is a way to just skip the lagrange interpolation part: Set $N=\binom{1400}{700}$ and let $A_1,\dots,A_N$ be all the ways to choose $700$ of the polynomials $P_1,\dots,P_{1400}$. Now define $P_i (x)=1+\prod_{P_i \in A_j} {(x-j)}$ So now if Amin chooses the $700$ polynomials as $A_k$, then by checking $k$ we get that the LHS is 1 and neither of the numbers on the RHS are $1,-1$ so the minimum is larger than 2. So Alireza wins.
08.06.2021 08:35
I think $\Omega (n) ,\omega (n)$ are undefined when $n$ is 1 or -1 So, we can't say that the inequality works But, it works well when we take two numbers $N! +1$ and $(N!+1)!+1$ for the range of $P:[N]\to Z$ when we use the lagrange interpolation ($N=\binom{1400}{700}$)
08.06.2021 08:46
Within the exam it was assumed that $\omega(1)=\Omega(1)=1$
11.06.2021 12:02
How is $\Omega (0),\omega(0)$ defined?
16.06.2021 18:49
Well, $\omega(0)=2$ and if I’m not mistaken, $\Omega(0)=\infty$ as in if one of the $P(n)$ s in the LHS is $0$ then the inequality automatically holds.
16.07.2021 19:42
Mr.C wrote: Assume $\Omega(n),\omega(n)$ be the biggest and smallest prime factors of $n$ respectively . Alireza and Amin decided to play a game. First Alireza chooses $1400$ polynomials with integer coefficients. Now Amin chooses $700$ of them, the set of polynomials of Alireza and Amin are $B,A$ respectively . Amin wins if for all $n$ we have : $$\max_{P \in A}(\Omega(P(n))) \ge \min_{P \in B}(\omega(P(n)))$$Who has the winning strategy. Proposed by Alireza Haghi $A\subset B$? $|B|=1400$ and $|A|=700$?
21.02.2023 22:08
Nice problem ! Alireza always can win I provide an algorithm for construction polynomials let all grouping to two sets be $G_1,G_2,...,G_{\binom{1400}{700}}$ and polynomials are $P_1,P_2,...,P_{1400}$ , for each $G_i$ I will found some $x_i$ such that $\forall P \in A : P_j(x_i) = q_i^{\alpha_{i,j}}$ and $\forall P \in B : P(x_i) = r_i^{\beta_{i,j}}$ such that $q_i , r_i$ are prime and $r_i > q_i$ and I choose very large $q_i,r_i$ such that $gcd(q_ir_i , \prod (x_j-x_k))=1$ So... we need this lemma : Lemma : we can find $P\in \mathbb{Z}[x]$ such that for some $x_1,x_2,...,x_n$ and primes $p_1,p_2,...,p_n$ : $$P(x_i) = p_i^{\alpha_i} \text{ for some } \alpha_i$$now using Newton's interpolation, and just let $\alpha_i \equiv 0 \pmod{\phi(x_j-x_k)}$ and it is easy to check this polynomial will have integer coefficients : $$P(x) = p_1^{\alpha_1} + (x-x_1) \frac{p_2^{\alpha_2} - p_1^{\alpha_1}}{x_2-x_1} + (x-x_1)(x-x_2)\frac{p_3^{\alpha_3} - (x_3-x_1) \frac{p_2^{\alpha_2} - p_1^{\alpha_1}}{x_2-x_1} - p_1^{\alpha_1}}{(x_3-x_1)(x_3-x_2)} + ... $$