IMO2024 Shortlisted Problems

If $\mathcal{S}$ has only one element $p$, then $b_i=p^{i-1}$ and we can easily find $a_1,\dots ,a_n$ with $2=\lceil {\sum }_{i=0}^{n-1}\frac{1}{p^i}\rceil ={\sum }_{i=0}^{n-1}\frac{a_i}{p^{i-1}}$ by taking $a_1=a_2=\cdots =a_{n-1}=1$ and choosing $a_n=p^{n-1}-(p+p^2+\dots +p^{n-2})$.

More generally, observe that the sum of $\frac{1}{b_i}$ over all $i$ is $$\begin{array}{rl}\sum _i\frac{1}{b_i}& =\prod _i\left(1+\frac{1}{p_i}+\frac{1}{p_i^2}+\dots \right)\\ & =\prod _{p\in \mathcal{S}}\frac{p}{p-1}\end{array}$$ In particular, if $n$ is large enough, then $$\lceil \sum _{j=1}^n\frac{1}{b_j}\rceil =\lceil \prod _{p\in \mathcal{S}}\frac{p}{p-1}\rceil$$ For the remainder of the proof, we will only consider $n$ large enough that this equality holds.

Next, we handle the special case $\mathcal{S}=\{2,3\}$, for which this product is $3$. Start by setting $$a_i=\{\begin{array}{ll}1,& \text{ if }2b_i⩽b_n\\ 2,& \text{ if }2b_i>b_n\end{array}$$ Then, $$\sum _{\begin{array}{c}i⩽n\\ {\nu }_3(b_i)=t\end{array}}\frac{a_i}{b_i}=\{\begin{array}{ll}\frac{2}{3^t},& \text{ if }{b}_n⩾3^t\\ 0,& \text{ otherwise }\end{array}$$ As a result, $$\begin{array}{rl}\sum _{i⩽n}\frac{a_i}{b_i}& =\sum _{\begin{array}{c}t⩾0\\ 3^t⩽b_n\end{array}}\frac{2}{3^t}\\ & =3-\frac{1}{3^T}\end{array}$$ where $T$ is the largest $t⩾0$ with $3^t⩽b_n$. Thus, increasing $a_j$ by one (where $b_j=3^T$) gives a sequence of $a_i$ that works.

Otherwise, we may assume that $|\mathcal{S}|>1$ and $\mathcal{S}\ne \{2,3\}$, which means that the product ${\prod }_{p\in \mathcal{S}}\frac{p}{p-1}$ is not an integer. Indeed, - if $|\mathcal{S}|>2$ then $2$ divides the denominator at least twice and so divides the denominator of the overall fraction; - if $|\mathcal{S}|=2$ and $2\notin \mathcal{S}$ then $2$ divides the denominator and not the numerator; - if $\mathcal{S}=\{2,p\}$ then the product is $2p/(p-1)$ which is not an integer for $p>3$.

It follows that for some fixed $\alpha >0$, we have that $$\lceil \prod _{p\in \mathcal{S}}\frac{p}{p-1}\rceil =\prod _{p\in \mathcal{S}}\frac{p}{p-1}+\alpha$$ from which it follows that $$\lceil \sum _{i=1}^n\frac{1}{b_i}\rceil -\sum _{i=1}^n\frac{1}{b_i}>\alpha$$ It will now suffice to prove the following claim.

Claim. Suppose that $n$ is large enough, and let $e_p$ be the largest nonnegative integer such that $p^{e_p}⩽b_n$. Let $M={\prod }_{p\in \mathcal{S}}{p}^{e_p}$. If $u$ is a positive integer such that $u/M>\alpha$, then there exist nonnegative integers $a_i$ such that $$\sum _i\frac{a_i}{b_i}=\frac{u}{M}.$$ The problem statement follows after replacing $a_i$ with $a_i+1$ for each $i$.

To prove this, choose some constant $c$ such that ${\sum }_{p\in \mathcal{S}}{p}^{-c}<\alpha$, and suppose $n$ is large enough that $p^c<b_n$ for each $p\in \mathcal{S}$; in particular, $p^c\mid M$ with $M$ defined as above.

For each $p\in \mathcal{S}$, let $i_p$ be such that $b_{i_p}=p^{e_p}$ and choose the smallest nonnegative integer $a_{i_p}$ satisfying $$p^{e_p-c}|a_{i_p}\left(\frac{M}{p^{e_p}}\right)-u$$ Such an $a_{i_p}$ must exist and be at most $p^{e_p-c}$; indeed, $\frac{M}{p^{e_p}}$ is an integer coprime to $p$, so we can take $a_{i_p}$ to be equal to $u$ times its multiplicative inverse modulo $p^{e_p-c}$.

The sum of the contributions to the sum from the $a_{i_p}$ is at most $$\sum _{p\in \mathcal{S}}\frac{p^{e_p-c}}{p^{e_p}}=\sum _{p\in \mathcal{S}}{p}^{-c}<\alpha$$ So, we have $$\frac{u}{M}=\sum _{p\in \mathcal{S}}\frac{a_{i_p}}{p^{e_p}}+\frac{r}{{\prod }_{p\in \mathcal{S}}{p}^c},$$ where $r$ is an integer because of our choice of $a_{i_p}$ and $r$ is nonnegative because of the bound on $u$. Simply choose $a_i=r$ where $b_i={\prod }_{p\in \mathcal{S}}{p}^c$ to complete the proof.

---

Alternative solution.

We reduce to the claim as in Solution 1, and provide an alternative approach for constructing the $a_i$.

Let $p_0\in \mathcal{S}$ be the smallest prime in $\mathcal{S}$. Let $z_0=u/M$. We construct a sequence $z_0,z_1,z_2,\dots$ and values of $a_i$ by the following iterative process: to construct $z_{j+1}$, - select the largest prime $p\in \mathcal{S}$ dividing the denominator of $z_j$, and let $\mu$ be the number of times $p$ divides the denominator of $z_j$; - choose the largest $\nu$ such that $p_0^{\nu }{p}^{\mu }⩽b_n$, and let $i⩽n$ be such that $b_i=p_0^{\nu }{p}^{\mu }$; - choose $0⩽a_i<p$ such that the denominator of $z_k-a_i/b_i$ has at most $\mu -1$ factors of $p$, and let $z_{k+1}=z_k-a_i/b_i$; - continue until $p_0$ is the only prime dividing the denominator of $z_k$.

Note that we can always choose $a_i$ in step 3; by construction, $z_k{b}_i$ has no factors of $p$ in its denominator, so must be realised as an element of ${\mathbb{Z}}_p$.

Each time we do this, $b_i>M/p_0$ by construction, so $$\frac{a_i}{b_i}<\frac{p{p}_0}{M}⩽\frac{p_0{p}_1}{M},$$ where $p_1$ is the largest prime in $\mathcal{S}$. And the number of times we do this operation is at most $$\sum _{\begin{array}{c}p\in \mathcal{S}\\ p>p_0\end{array}}{e}_p⩽|\mathcal{S}|{\log }_2(M)$$ so the sum of the $a_i/b_i$ we have assigned is at most $|\mathcal{S}|p_0{p}_1{\log }_2(M)/M$.

Choose $n$ large enough that ${\log }_2(M)/M<\alpha$; after subtracting the above choices of $a_i/b_i$ from $u/M$, we have a quantity of the form $r/p_0^{e_{p_0}}$, where $r$ is an integer by construction and $r$ is positive by the above bounds. Simply set $a_i=r$ where $b_i=p_0^{e_{P_0}}$ to complete the proof.

---

Alternative solution.

As in Solution 1, we may handle $|\mathcal{S}|=1$ and $\mathcal{S}=\{2,3\}$ separately; otherwise, we can define $\alpha$ as we did in that solution. Also define $e_p$ to be the largest nonnegative integer such that $p^{e_p}⩽b_n$ as we did in Solution 1.

We will show that, for $n$ sufficiently large, we may choose some $j⩽n$, and positive integers $a_i$, such that $$\sum _{i\ne j}\frac{a_i}{b_i}-\sum _{i\ne j}\frac{1}{b_i}<\alpha$$ and all $\frac{a_i}{b_i}$ are integer multiples of $\frac{1}{b_j}$. We then set $a_j$ to be the least positive integer such that the sum on the left is an integer, which will obviously have the required value.

Concretely, choose $j$ such that $b_j={\prod }_{p\in \mathcal{S}}{p}^{e_p/|\mathcal{S}|]}$, which is less than $b_n$ by construction. For $i\ne j$, set $a_i=b_i/\gcd (b_i,b_j)$. We have $$\sum _{i\ne j}\frac{a_i}{b_i}-\sum _{i\ne j}\frac{1}{b_i}<\sum _{\begin{array}{c}i\ne j\\ a_i>1\end{array}}\frac{a_i}{b_i}$$ If $a_i>1$, then there must be some $p\in \mathcal{S}$ for which $p^{\lfloor e_p/|\mathcal{S}|]+1}\mid b_i$, and so $$\frac{a_i}{b_i}=\frac{1}{\gcd (b_i,b_j)}⩽\frac{1}{p^{\left[e_p/|\mathcal{S}|\right]}}<\frac{p}{b_n^{1/|\mathcal{S}|}}$$ where the last inequality follows from the fact that $p^{e_p+1}>b_n$.

Now $n⩽{\prod }_{p\in \mathcal{S}}({\log }_p(b_n)+1)⩽(2\log b_n{)}^{|\mathcal{S}|}$, so $$\sum _{\begin{array}{c}i\ne j\\ a_i>1\end{array}}\frac{a_i}{b_i}⩽\frac{(2\log b_n{)}^{|\mathcal{S}|}}{b_n^{1/|\mathcal{S}|}}$$ and so we can choose $n$ large enough that this quantity is less than $\alpha$, as required.