42nd Balkan Mathematical Olympiad

First, we will prove the following lemma: Lemma. Let $f$ be a polynomial with rational coefficients such that $f(n)$ is an integer for any integer $n$. Then there exist integers $a_0,a_1,\dots ,a_p$ such that $f(x)={\sum }_{i=0}^p{a}_i\left(\genfrac{}{}{0ex}{}{x}{i}\right)$. Proof. Let us first prove that for any polynomial with rational coefficients $f$ there are rational numbers $a_0,a_1,\dots ,a_p$ (where $p=\mathrm{deg}f(x)$) such that $f(x)={\sum }_{i=0}^p{a}_i\left(\genfrac{}{}{0ex}{}{x}{i}\right)$. We will prove this by induction on $p=\mathrm{deg}f(x)$, with the base case $p=0$ being clear. Assuming that $p\ge 1$ and that the result holds for polynomials of degree not exceeding $p-1$, consider a polynomial $f(x)$ of degree $p$. Then choose $a_p$ such that $f(x)-a_p\left(\genfrac{}{}{0ex}{}{x}{p}\right)$ has degree not exceeding $p-1$ (namely, if $a$ is the leading coefficient of $f$, choose $a_p=a\cdot p!$). By the inductive hypothesis we can write $$f(x)-a_p\left(\genfrac{}{}{0ex}{}{x}{p}\right)=\sum _{i=0}^{p-1}{a}_i\left(\genfrac{}{}{0ex}{}{x}{i}\right)$$ for some rational numbers $a_0,\dots ,a_p$, and thus $f$ has the required form. Assuming that $f(n)$ is an integer for all integers $n$, then $$a_1=(a_0+a_1)-a_0=f(1)-f(0)$$ is an integer, as a difference of two integers. Clearly, $a_0=f(0)$ is also an integer. Assuming that $a_0,\dots ,a_{k-1}$ are integers for some $k\ge 2$, the relation $$f(k)=a_0\left(\genfrac{}{}{0ex}{}{k}{0}\right)+a_1\left(\genfrac{}{}{0ex}{}{k}{1}\right)+\cdots +a_{k-1}\left(\genfrac{}{}{0ex}{}{k}{k-1}\right)+a_k$$ shows that $a_k$ is an integer, as well. Therefore $a_0,a_1,\dots ,a_p$ are all integers and the proof of the lemma is complete.

Now let's return to the original problem. For all $n>k$, we have that $$2025^n=(2024+1{)}^n=\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})2024^i\equiv \sum _{i=0}^{k-1}(\genfrac{}{}{0ex}{}{n}{i})2024^i(\mathrm{mod}11^k).$$ Let $Q(n)={\sum }_{i=0}^{k-1}\left(\genfrac{}{}{0ex}{}{n}{i}\right)2024^i$, which is a polynomial with rational coefficients of degree $k-1$ in $n$. Then the condition is equivalent to $$P(n)+Q(n)\equiv 0(\mathrm{mod}11^k)$$ for all positive integers $n>k$. Let $Q(x)={\sum }_{i=0}^{k-1}{q}_i{x}^i$ and $P(x)={\sum }_{i=0}^d{p}_i{x}^i$. If $d\ge k-1$, we can select $p_i=-q_i$ for all $0\le d\le k-1$ and $p_i=11^k$ for $i>k-1$ and the condition is satisfied. Obviously all $q_i$ are rational numbers, and hence $P$ is a polynomial with rational coefficients. Let $p_i=\frac{a_i}{b_i}$ where $a_i,b_i$ are integers such that $\text{GCD}(a_i,b_i)=1$, for all $i\in \{0,1,\dots ,k-1\}$ (or if $p_i=0$ we set $a_i=0,b_i=1$). Notice that $\left(\genfrac{}{}{0ex}{}{x}{i}\right)\cdot 2024^i=\frac{x(x-1)\dots (x-i+1)}{1\cdot 2\dots i}\cdot 2024^i$, and since

$v_{11}(i!)=\lfloor \frac{i}{11}\rfloor +\lfloor \frac{i}{11^2}\rfloor +\cdots <i=v_{11}(2024^i)$, the denominator of this fraction (after reduction) is not divisible by $11$, for all $i\in \{0,1,\dots ,k-1\}$. Hence, none of the $b_i$'s is divisible by $11$. Let $S=\text{LCM}(b_0,b_1,b_2,\dots ,b_{k-1})$ and let $S_{inv}$ be an integer such that $S\cdot S_{inv}\equiv 1(\mathrm{mod}11^k)$ ($S_{inv}$ exists because $S$ is not divisible by $11$). Define $P^{\prime }(x)=P(x)\cdot S\cdot S_{inv}$. Now, first notice that $P^{\prime }(x)$ has integer coefficients ($P(x)\cdot S$ has integer coefficients, and multiplying it by $S_{inv}$ doesn't change that fact) and due to the construction of $S_{inv}$, for each positive integer $n>k$ we have that $P^{\prime }(n)\equiv P(n)(\mathrm{mod}11^k)$. Thus, $P^{\prime }$ also satisfies the condition and has integer coefficients. In conclusion, all $d\ge k-1$ satisfy the problem condition.

Now, suppose that $d<k-1$ and let $$R(x)=P(x)+Q(x).$$ Then $\text{deg}R(x)=k-1$ and $\frac{R(n)}{11^k}$ is an integer for all positive integers $n>k$ (hence, in fact, for all positive integers due to the periodicity of $R$ modulo $11^k$). Let $$T(x)=\frac{R(x)}{11^k}=\sum _{i=0}^{k-1}\frac{r_i}{11^k}{x}^i.$$ Then the leading coefficient of $T(x)$ is equal to $$\frac{r_{k-1}}{11^k}=\frac{q_{k-1}}{11^k}=\frac{2024^{k-1}}{(k-1)!11^k}.$$ Also, using the lemma we can write $$T(x)=\sum _{i=0}^{k-1}{a}_i\left(\genfrac{}{}{0ex}{}{x}{i}\right)$$ with $a_i\in \mathbb{Z}$ for all $0\le i\le k-1$. Comparing the leading coefficients we get that $$\frac{2024^{k-1}}{(k-1)!11^k}=\frac{a_{k-1}}{(k-1)!}$$ which implies that $$\frac{2024^{k-1}}{11^k}=a_{k-1}\in \mathbb{Z},$$ a contradiction. In conclusion, the desired positive integers $d$ are all such that $d\ge k-1$.