Given a set $S$ of integers, an allowed operation consists of the following three steps: $\bullet$ Choose a positive integer $n$. $\bullet$ Choose $n+1$ elements $a_0, a_1, \dots, a_n \in S$, not necessarily distinct. $\bullet$ Add to the set $S$ all the integer roots of the polynomial $a_n x^n + a_{n-1} x^{n-1} + \dots + a_2 x^2 + a_1 x + a_0$. Beto must choose an initial set $S$ and perform several allowed operations, so that at the end of the process $S$ contains among its elements the integers $1, 2, 3, \dots, 2023, 2024$. Determine the smallest $k$ for which there exists an initial set $S$ with $k$ elements that allows Beto to achieve his objective.
Problem
Source: Rioplatense Math Olympiad Level 3, P3 2024
Tags: algebra, rioplatense, roots
mijail
06.12.2024 02:31
Solved with @Enigma714
$k=1$
Lemma 0: If $M$ is a postive integer in $S$, then we can make $1,-1\in S$. Also, if $m \in S$, then $-m \in S$.
Taking $n=1$ and $a_0=a_1=M$ we have $-1$ is a root of $Mx+M$, so we get $-1\in S$.
Now, taking $n=M$, $a_0=M$ and $a_1=\dots=a_M=-1$, then $1$ is a root of $-x^M-x^{M-1}-\dots-x+M$, so we get $1\in S$.
Finally, take $n=1$, $a_0=m$ and $a_1=1$, then $-m$ is a root of $x+m$, so we get $-m\in S$.
Lemma 1: If $a^p\in S$, with $a\in \mathbb{Z}$ and $p>1$, then we can make $a\in S$.
We can make $-a^p\in S$ by Lemma 0, so with
$$\text{$n=2p-1$, $a_0=-a^p$, $a_p=1$ and $a_i=a^p$, $a_{i+p}=-1$ for all $1\leq i\leq p-1$,}$$we get the polynomial:
$$\sum_{i=1}^{p-1} (-1)x^{i+p}+x^p+\sum_{i=1}^{p-1} a^p x^{i}-a^p$$that has clearly $a$ as a root.
Lemma 2: If $N \mid K$ and $N^2 \nmid K$ then $K$ can be written $\sum_{r=1}^{l} a_{r}N^r $ with coefficients of the form $\{\pm 1, \pm 2, \dots , \pm(N-1) \}$
By induction on $K$, consider $K \equiv Nt \pmod{N^2}$ then $N \nmid t$ so we can choose $t$ in the set $\{\pm 1, \pm 2, \dots , \pm(N-1) \}$ such that $N \mid \frac{K-Nt}{N}$ but $N^2 \nmid \frac{K-Nt}{N}$ (this by considering $t$ or $t-N$) so use the induction on $\frac{K-Nt}{N}$
Then select $n= (\prod_{i=1}^{2024} p_i)^{2024!}$ where $p_1,p_2\dots$ are the primes in increasing order and use induction if we have in $S$ the numbers $1,2, \dots, k-1$ with $k \leq 2024$ then choose $r$ such that $(\prod_{i=1}^{2024} p_i)^r \in S$ is divisible by $k$ but not divisible by $k^2$ this election is possible by lemma 1, then by lemma 2 we have $k$ can be added to $S$ so we are done.
BR1F1SZ
08.12.2024 02:04
Proposed by Bruno MartÃn Ziger, Argentina. Beautiful problem!