IMO2024 Shortlisted Problems

Solution 1. Without loss of generality, we may divide all elements of $\mathcal{S}$ by any common factor, after which they cannot all be even. As $a\nmid b+2c$ for $a$ even and $b$ odd, the elements of $\mathcal{S}$ are all odd. We now divide into three cases: Case 1: $|\mathcal{S}|=1$. The set $\mathcal{S}=\{t\}$ clearly works. Case 2: $|\mathcal{S}|=2$. Say $\mathcal{S}=\{r,s\}$ with $r<s$, so either $s\mid r+2r$ or $s\mid r+2s$, and in either case $s\mid 3r$. We cannot have $s=3r/2$ as we assumed that $r$ is odd, so $s=3r$ and $\mathcal{S}=\{r,3r\}$, which clearly works by examining cases for $a$ and $b$. Case 3: $|\mathcal{S}|⩾3$. If all elements of $\mathcal{S}$ are odd then for any $b,c\in \mathcal{S},b+2c\not\equiv b(\mathrm{mod}4)$. If $a\mid b+2c$ with $a\equiv b(\mathrm{mod}4)$, this means there exists $k$ with $b+2c=ka$ and $k\equiv 3(\mathrm{mod}4)$, so $k⩾3$. If $a$ is the greatest element of $\mathcal{S}$ and $b<a$, we have $b+2c<3a$, a contradiction. Thus when $a$ is the greatest element, no $b<a$ has $b\equiv a(\mathrm{mod}4)$ (and thus all elements other than the greatest are congruent modulo 4). Let $d$ and $e$ be the largest and second largest element of $\mathcal{S}$ respectively. Let $f\ne d,e$ be any other element of $\mathcal{S}$. There is some $c\in \mathcal{S}$ with $e\mid f+2c$, and $e\not\equiv f+2c(\mathrm{mod}4)$, so $f+2c⩾3e$, so $c>e$. Since $e$ is the second largest element of $\mathcal{S},c=d$, so $e\mid f+2d$, and this holds for all $f\in \mathcal{S}$ with $f<e$, but can only hold for at most one such $f$. So $|\mathcal{S}|⩽3$. Hence the elements of $\mathcal{S}$ are $d>e>f$, and by the discussion above without loss of generality we may suppose these elements are all odd, $e\equiv f(\mathrm{mod}4)$ and $d\not\equiv e(\mathrm{mod}4)$. We have above that $e\mid f+2d$. Furthermore, there exists some $c\in \mathcal{S}$ with $d\mid f+2c$, and $c\ne d$ as $d>f$ so $d\nmid f$, so $c⩽e$; as $f+2e<3e$, we have $e>d/3$. Since $f+2c$ is odd and $f+2c<3d$, we have $f+2c=d$. Subcase 3.1: $c=f$. Here $d=3f$ and $e\mid f+2d=7f$. As $e>f$ and $e\equiv f(\mathrm{mod}4)$, we have $e=7f/3$ and the elements are some multiples of $\{3,7,9\}$. But $a=7$ and $b=9$ have no corresponding value of $c$. Subcase 3.2: $c=e$. Here $d=f+2e$ and $e\mid f+2d=3f+4e$ so $e\mid 3f$. But this is not possible with $e>f$ and $e\equiv f(\mathrm{mod}4)$.

---

Alternative solution.

Let $d$ be the largest element. For any $e\in \mathcal{S}$ with $e\ne d$ there must be a $f\in \mathcal{S}$ such that $d\mid e+2f$. This implies $2f\equiv -e(\mathrm{mod}d)$, hence $2f\equiv d-e(\mathrm{mod}d)$. Now $d-e$ is even (because all elements in $\mathcal{S}$ are odd) and $d$ is odd, so $\frac{d-e}{2}$ is an integer and we have $f\equiv \frac{d-e}{2}(\mathrm{mod}d)$. Further, $0<\frac{d-e}{2}<d$, while we must also have $0<f⩽d$, so $f=\frac{d-e}{2}$. We conclude that for any $e\in \mathcal{S}$ with $e\ne d$ the integer $\frac{d-e}{2}$ is also in $\mathcal{S}$ and not equal to $d$. Denote by $e_1<e_2<\cdots <e_k<d$ the elements of $\mathcal{S}$, where $k⩾1$. Then $\frac{d-e_1}{2}>\frac{d-e_2}{2}>\cdots >\frac{d-e_k}{2}$ are also elements of $\mathcal{S}$, none of them equal to $d$. Hence we must have $e_1=\frac{d-e_k}{2}$ and $e_k=\frac{d-e_1}{2}$, so $2e_1+e_k=d=2e_k+e_1$. We conclude $e_1=e_k$, so $k=1$, and also $d=2e_k+e_1=3e_1$. Hence $\mathcal{S}=\left\{e_1,3e_1\right\}$ for some positive integer $e_1$.

---

Alternative solution.

Let $d$ be the largest element, and let $e\in \mathcal{S}$ be any other element. We will say that $x\in \mathcal{S}(\mathrm{mod}d)$ if the unique element $y$ in $\{1,\dots ,d\}$ such that $x\equiv y(\mathrm{mod}d)$ is an element of $\mathcal{S}$. Note that by the choice of $d$ being the largest element, if $x\ne d$, then $x\not\equiv 0(\mathrm{mod}d)$. The given condition implies that if $b\in \mathcal{S}$, then $-\frac{b}{2}\in \mathcal{S}(\mathrm{mod}d)$. Repeating this gives $-\frac{b}{2}\in \mathcal{S}\Rightarrow \frac{b}{4}\in \mathcal{S}(\mathrm{mod}d)$, and by iterating, we have $b\in \mathcal{S}\Rightarrow \frac{b}{(-2{)}^k}\in \mathcal{S}(\mathrm{mod}d)$ for all $k$. Since $d$ is odd, there is some $g$ such that $(-2{)}^g\equiv 1(\mathrm{mod}d)$, so by setting $k=g-1$, we get that $$\text{ for all }d\ne e\in \mathcal{S},-2e\in \mathcal{S}(\mathrm{mod}d)\text{. }$$ Now, if $e>\frac{d}{2}$, then $-2e\in \mathcal{S}(\mathrm{mod}d)$ and $d-2e<0$, so $2d-2e\in \mathcal{S}$, contradicting the lack of even elements. Then $e<\frac{d}{2}$ for any $e\in \mathcal{S}\backslash \{d\}$, so we have $e\in \mathcal{S}\Rightarrow d-2e\in \mathcal{S}$. Since $d-2e\ne d$, we must have $d-2e<\frac{d}{2}$, which rearranges to $e>\frac{d}{4}$. Let $\lambda \in (0,1)$ be a positive real number and suppose we have proved that $e>\lambda d$ for any $e\in \mathcal{S}\backslash \{d\}$. Then $d-2e>\lambda d$, which rearranges to $e<\frac{(1-\lambda )d}{2}$. Then $d-2e<\frac{(1-\lambda )d}{2}$, which rearranges to $e>\frac{(1+\lambda )d}{4}$. Defining ${\lambda }_0=\frac{1}{4}$ and ${\lambda }_i=\frac{1+{\lambda }_{i-1}}{4}$ for $i⩾1$, we have shown that for all $e\in \mathcal{S}\backslash \{d\}$ and all ${\lambda }_i,e>{\lambda }_{i}d$. Now note that the sequence ${\lambda }_i$ is increasing and bounded above by $\frac{1}{3}$, so it converges to some limit $\ell$, which satisfies $\ell =\frac{1+\ell }{4}$, so $\ell =\frac{1}{3}$. Hence $e⩾\frac{d}{3}$, but then $d-2e⩾\frac{d}{3}$ implies $e⩽\frac{d}{3}$, so $e$ must be $\frac{d}{3}$, and we are done. Comment. We can finish Solution 3 alternatively as follows: after showing that if $e\in \mathcal{S}\backslash \{d\}$ then $d-2e\in \mathcal{S}\backslash \{d\}$, note that $$(d-2e)-\frac{d}{3}=\frac{2d}{3}-2e=-2\left(e-\frac{d}{3}\right)$$ So consider $e\in \mathcal{S}\backslash \{d\}$ maximising $\left|e-\frac{d}{3}\right|$. If $e\ne \frac{d}{3}$, them the above shows that $\left|(d-2e)-\frac{d}{3}\right|>\left|e-\frac{d}{3}\right|$, which is a contradiction. Thus $\mathcal{S}\backslash \{d\}$ is empty or equal to $\left\{\frac{d}{3}\right\}$, which completes the proof.