INMO 2022

We show that 5 numbers will suffice. Take $S=\{0,1,3,4,6\}$. Observe the following splitting:

$n$	$a$	$b$
0	0	0
1	0	1
2	1	1
3	0	3
4	1	3
5	1	4
6	3	3
7	3	4
8	4	4
9	3	6

Thus each digit in a given nonnegative integer is split according to the above and can be written as a sum of two numbers each having digits in $S$.

We show that $|S|>4$. Suppose $|S| \leq 4$. We may take $|S|=4$ as adding extra numbers to $S$ does not alter our argument. Let $S=\{a, b, c, d\}$. Since the last digit can be any one of the numbers $0,1,2, \ldots, 9$, we must be able to write this as a sum of digits from $S$, modulo 10. Thus the collection

$$A=\{x+y \quad(\bmod 10) \mid x, y \in S\}$$

must contain $\{0,1,2, \ldots, 9\}$ as a subset. But $A$ has at most 10 elements $\left(\binom{4}{2}+4\right)$. Thus each element of the form $x+y(\bmod 10)$, as $x, y$ vary over $S$, must give different numbers from $\{0,1,2, \ldots, 9\}$.

Consider $a+a, b+b, c+c, d+d$ modulo 10. They must give 4 even numbers. Hence the remaining even number must be from the remaining 6 elements obtained by adding two distinct members of $S$. We may assume that even number is $a+b(\bmod 10)$. Then $a, b$ must have same parity. If any one of $c, d$ has same parity as that of $a$, then its sum with $a$ gives an even number, which is impossible. Hence $c, d$ must have same parity, in which case $c+d(\bmod 10)$ is even, which leads to a contradiction. We conclude that $|S| \geq 5$.

We use Chebyshev’s inequality. Observe

$$\begin{aligned} & n\left(a_{1} a_{2} \cdots a_{n-1} + a_{1} a_{2} \cdots a_{n-2} + \cdots + a_{1} + 1\right) \\ & \quad = \left(a_{1} a_{2} \cdots a_{n-1} + a_{1} a_{2} \cdots a_{n-2} + \cdots + a_{1} + 1\right)\left(\left(a_{n} - 1\right) + \left(a_{n-1} - 1\right) + \cdots + \left(a_{1} - 1\right)\right) \\ & \quad \leq n\left(a_{1} a_{2} \cdots a_{n-1}\left(a_{n} - 1\right) + \cdots + a_{1}\left(a_{2} - 1\right) + 1\left(a_{1} - 1\right)\right) \\ & \quad \leq n\left(a_{1} a_{2} \cdots a_{n} - 1\right) \end{aligned}$$

It follows that

$$a_{1} a_{2} \cdots a_{n-1} + a_{1} a_{2} \cdots a_{n-2} + \cdots + a_{1} + 1 \leq a_{1} a_{2} \cdots a_{n} - 1$$

This gives the required inequality.

Suppose on the contrary that it is possible to cover the board with 16 strominos such that each unit square is covered by either one or two strominos. If there are $k$ squares that are covered by exactly one stromino then $2(25-k)+k=16 \times 3=48$ and hence $k=2$. Thus there are exactly two squares which are covered by only one stromino.

We colour the board with three colours red, blue, green as follows. The square corresponding to the $i$-th row and the $j$-th column is coloured red if $i+j \equiv 0 \pmod{3}$, green if $i+j \equiv 1 \pmod{3}$ and blue otherwise. Then there are 9 red squares, 8 green squares and 8 blue squares. Note that each stromino covers exactly one square of each colour. Therefore the two squares that are covered by only one stromino are both red. For each such square $i+j \equiv 0 \pmod{3}$ where $i$ and $j$ are its row and column number.

We now colour the board with a different scheme. We colour the square corresponding to the $i$-th row and the $j$-th column red if $i-j \equiv 0 \pmod{3}$, green if $i-j \equiv 1 \pmod{3}$ and blue otherwise. Again, there are 9 red squares and hence the two squares covered by only one stromino are both red. For each such square $i-j \equiv 0 \pmod{3}$ where $i$ and $j$ are its row and column number. Thus, each of the two squares covered by only one stromino satisfies $i+j \equiv 0 \pmod{3}$ and $i-j \equiv 0 \pmod{3}$ where $i$ and $j$ are its row and column number. This implies that $i=j=3$. This is a contradiction because there is only one such square.

Let $m_{1}, n_{1}, m_{2}, n_{2}$ be integers satisfying $m_{1} n_{2}-m_{2} n_{1}= \pm 1$. By changing the signs of $m_{2}, n_{2}$ if need be, we may assume that

$$m_{1} n_{2}-m_{2} n_{1}=1$$

If $m_{3}, n_{3}$ are integers satisfying $m_{1} n_{3}-m_{3} n_{1}= \pm 1$, again we may assume (by changing their signs if necessary) that

$$m_{1} n_{3}-m_{3} n_{1}=1$$

So $m_{1}\left(n_{2}-n_{3}\right)=n_{1}\left(m_{2}-m_{3}\right)$. As $m_{1}, n_{1}$ are relatively prime, $m_{1}$ divides $m_{2}-m_{3}$; say, $m_{2}-m_{3}=m_{1} a$ for some integer $a$. Thus, we get $n_{2}-n_{3}=n_{1} a$. In other words,

$$m_{3}=m_{2}-m_{1} a, \quad n_{3}=n_{2}-n_{1} a$$

Now, if $m_{2} n_{3}-n_{2} m_{3}= \pm 1$, we get

$$\pm 1=m_{2}\left(n_{2}-n_{1} a\right)-n_{2}\left(m_{2}-m_{1} a\right)=\left(m_{1} n_{2}-m_{2} n_{1}\right) a=a$$

Thus, $m_{3}=m_{2}-m_{1} a=m_{2} \pm m_{1}, \quad n_{3}=n_{2}-n_{1} a=n_{2} \pm n_{1}$. Now if we were to have another pair of integers $m_{4}, n_{4}$ such that

$$m_{1} n_{4}-n_{1} m_{4}= \pm 1$$

we may assume that $m_{1} n_{4}-n_{1} m_{4}=1$. As seen above, $m_{4}=m_{2} \mp m_{1}, \quad n_{4}=n_{2} \mp n_{1}$. But then

$$m_{3} n_{4}-n_{3} m_{4}=\left(m_{2} \pm m_{1}\right)\left(n_{2} \mp n_{1}\right)-\left(n_{2} \pm n_{1}\right)\left(m_{2} \mp m_{1}\right)= \pm 2$$

Therefore, there can be only 3 pairs of such integers.

Alternate Solution: It is clear that $r$ can be 3 due to the valid solution $m_{1}=1, n_{1}=1, m_{2}=1, n_{2}=2, m_{3}=2, n_{3}=3$. If possible, let $r>3$. We observe that:

$$\begin{aligned} & m_{1} n_{2} n_{3}-m_{2} n_{1} n_{3}= \pm n_{3} \\ & m_{2} n_{3} n_{1}-m_{3} n_{2} n_{1}= \pm n_{1} \\ & m_{3} n_{1} n_{2}-m_{1} n_{3} n_{2}= \pm n_{2} \end{aligned}$$

Adding, we get $\pm n_{1} \pm n_{2} \pm n_{3}=0$; which forces at least one of $n_{1}, n_{2}, n_{3}$ to be even; WLOG let $n_{1}$ be even. Repeating the argument for indices $2,3,4$, we deduce that at least one of $n_{2}, n_{3}, n_{4}$ is even; WLOG let $n_{2}$ be even. This leads to a contradiction, since $\left|m_{1} n_{2}-m_{2} n_{1}\right|=1$ cannot be even. Hence $r>3$ is not possible, as claimed.

Solution 1.

The only such pair is $(0,0)$, which clearly works. To prove this is the only one, let us prove an auxiliary result first.

Lemma If $\alpha, \beta, \gamma$ are reals so that $\alpha+\beta+\gamma=0$ and $|\alpha|,|\beta|,|\gamma| \geq 2$, then

$$|\alpha \beta+\beta \gamma+\gamma \alpha|<|\alpha \beta \gamma|$$

Proof. Some two of these reals have the same sign; WLOG, suppose $\alpha \beta>0$. Then $\gamma=-(\alpha+\beta)$, so by substituting this,

$$|\alpha \beta+\beta \gamma+\gamma \alpha|=\left|\alpha^{2}+\beta^{2}+\alpha \beta\right|,\ |\alpha \beta \gamma|=|\alpha \beta(\alpha+\beta)|$$

So we simply need to show $|\alpha \beta(\alpha+\beta)|>\left|\alpha^{2}+\beta^{2}+\alpha \beta\right|$. Since $|\alpha| \geq 2$ and $|\beta| \geq 2$, we have

$$\begin{aligned} & |\alpha \beta(\alpha+\beta)|=|\alpha||\beta(\alpha+\beta)| \geq 2|\beta(\alpha+\beta)| \\ & |\alpha \beta(\alpha+\beta)|=|\beta||\alpha(\alpha+\beta)| \geq 2|\alpha(\alpha+\beta)| . \end{aligned}$$

Adding these and using triangle inequality,

$$\begin{aligned} 2|\alpha \beta(\alpha+\beta)| & \geq 2|\beta(\alpha+\beta)|+2|\alpha(\alpha+\beta)| \geq 2|\beta(\alpha+\beta)+\alpha(\alpha+\beta)| \\ & \geq 2\left(\alpha^{2}+\beta^{2}+2 \alpha \beta\right)>2\left(\alpha^{2}+\beta^{2}+\alpha \beta\right) \\ & =2\left|\alpha^{2}+\beta^{2}+\alpha \beta\right| \end{aligned}$$

Here we have used the fact that $\alpha^{2}+\beta^{2}+2 \alpha \beta=(\alpha+\beta)^{2}$ and $\alpha^{2}+\beta^{2}+\alpha \beta=\left(\alpha+\frac{\beta}{2}\right)^{2}+\frac{3 \beta^{2}}{4}$ are both nonnegative. This proves our claim.

For our main problem, suppose the roots of $x^{3}+a x+b$ are the integers $r_{1}, r_{2}, r_{3}$ and the roots of $x^{3}+b x+a$ are the integers $s_{1}, s_{2}, s_{3}$. By Vieta’s relations, we have

$$\begin{gathered} r_{1}+r_{2}+r_{3}=0=s_{1}+s_{2}+s_{3} \\ r_{1} r_{2}+r_{2} r_{3}+r_{3} r_{1}=a=-s_{1} s_{2} s_{3} \\ s_{1} s_{2}+s_{2} s_{3}+s_{3} s_{1}=b=-r_{1} r_{2} r_{3} \end{gathered}$$

If all six of these roots had an absolute value of at least 2, by our lemma, we would have

$$|b|=\left|s_{1} s_{2}+s_{2} s_{3}+s_{3} s_{1}\right|<\left|s_{1} s_{2} s_{3}\right|=\left|r_{1} r_{2}+r_{2} r_{3}+r_{3} r_{1}\right|<\left|r_{1} r_{2} r_{3}\right|=|b|$$

which is absurd. Thus at least one of them is in the set $\{0,1,-1\}$; WLOG, suppose it’s $r_{1}$.

1. If $r_{1}=0$, then $r_{2}=-r_{3}$, so $b=0$. Then the roots of $x^{3}+b x+a=x^{3}+a$ are precisely the cube roots of $-a$, and these are all real only for $a=0$. Thus $(a, b)=(0,0)$, which is a solution.

2. If $r_{1}= \pm 1$, then $\pm 1 \pm a+b=0$, so $a$ and $b$ can’t both be even. If $a=-s_{1} s_{2} s_{3}$ is odd, then $s_{1}, s_{2}, s_{3}$ are all odd, so $s_{1}+s_{2}+s_{3}$ cannot be zero. Similarly, if $b$ is odd, we get a contradiction.

The proof is now complete.

Solution 2.

The only such pair is $(0,0)$, which clearly works. Let us prove this is the only one. In what follows, we use $\nu_{2}(n)$ to denote the largest integer $k$ so that $2^{k} \mid n$ for any non-zero $n \in \mathbb{Z}$.

If one of the cubics has 0 as a root, say the first one, then $0^{3}+0 \cdot a+b=0$, so $b=0$. Then the roots of $x^{3}+b x+a=x^{3}+a$ are precisely the cube roots of $-a$, and these are all real only for $a=0$. Thus $(a, b)=(0,0)$.

So suppose none of the roots are zero. Take the cubic $x^{3}+a x+b$, and suppose its roots are $x, y, z$. We cannot have $\nu_{2}(x)=\nu_{2}(y)=\nu_{2}(z)$; indeed, if we had $x=2^{k} x_{1}, y=2^{k} y_{1}, z=2^{k} z_{1}$ for odd $x_{1}, y_{1}, z_{1}$, then

$$0=x+y+z=2^{k}\left(x_{1}+y_{1}+z_{1}\right)$$

But $x_{1}+y_{1}+z_{1}$ is odd, and hence non-zero, so this cannot happen.

Thus we can assume WLOG that $\nu_{2}(x)>\nu_{2}(y)$. Then the third root is $-(x+y)$. Similarly, the three roots of $x^{3}+b x+a$ can be written as $p, q,-(p+q)$ where $\nu_{2}(p)>\nu_{2}(q)$. By Vieta’s relations,

$$\begin{gathered} x y-x(x+y)-y(x+y)=-\left(x^{2}+x y+y^{2}\right)=a=p q(p+q) \\ p q-p(p+q)-q(p+q)=-\left(p^{2}+p q+q^{2}\right)=b=x y(x+y) \end{gathered}$$

Suppose $x=2^{k} x_{1}$ and $y=2^{\ell} y_{1}$ for odd $x_{1}, y_{1}$ and $k>\ell$; in particular $k>0$. Then

$$x y(x+y)=2^{k} x_{1} \cdot 2^{\ell} y_{1} \cdot\left(2^{k} x_{1}+2^{\ell} y_{1}\right)=2^{k+2 \ell} x_{1} y_{1}\left(2^{k-\ell} x_{1}+y_{1}\right)$$

Here $x_{1} y_{1}\left(2^{k-\ell} x_{1}+y_{1}\right)$ is clearly odd, so $\nu_{2}(x y(x+y))=k+2 \ell$.

Also,

$$x^{2}+x y+y^{2}=2^{2 k} x_{1}^{2}+2^{k} x_{1} \cdot 2^{\ell} y_{1}+2^{2 \ell} y_{1}^{2}=2^{2 \ell}\left(2^{2 k-2 \ell} x_{1}^{2}+2^{k-\ell} x_{1} y_{1}+y_{1}^{2}\right)$$

Again, all the terms in the second factor are even except $y_{1}^{2}$, so the entire factor is odd. This means $\nu_{2}\left(x^{2}+x y+y^{2}\right)=2 \ell$.

Therefore

$$\nu_{2}(x y(x+y))>\nu_{2}\left(x^{2}+x y+y^{2}\right)$$

Similarly, one may show

$$\nu_{2}(p q(p+q))>\nu_{2}\left(p^{2}+p q+q^{2}\right)$$

But then

$$\nu_{2}(b)=\nu_{2}(x y(x+y))>\nu_{2}\left(x^{2}+x y+y^{2}\right)=\nu_{2}(p q(p+q))>\nu_{2}\left(p^{2}+p q+q^{2}\right)=\nu_{2}(b)$$

Here we have used the fact that $\nu_{2}(n)=\nu_{2}(-n)$ for any integer $n$. But this is a contradiction, proving our claim.

Solution 1.

The answer is ‘yes’. To prove this, we will first prove two lemmas:

Lemma 1 Given any two points $A, B$, their midpoint $M$, and any point $C$, Vikram can draw a line parallel to $A B$ through $C$.

Proof. If $C$ is on line $A B$ we are already done. If not, extend $B C$ to $X$ as shown, draw $P = A C \cap X M$, and then draw $D = B P \cap A X$. We claim $C D$ is the desired line. Indeed, using Ceva’s theorem on triangle $A B X$ and the fact $A M = M B$, we see that

$$\frac{A M}{M B} \cdot \frac{B C}{C X} \cdot \frac{X D}{D A} = 1 \Longrightarrow \frac{X C}{C B} = \frac{X D}{D A}$$

This means $C D \parallel A B$.

Lemma 2 Given two non-parallel segments $A B, B C$ and their midpoints $M, N$, Vikram can draw the midpoint of any other segment $X Y$.

Proof. Assume first $X Y$ is not parallel to $A B$ or $B C$. Using lemma 1, draw lines $\ell_1$ and $\ell_2$ through $X$ parallel to $A B$ and $B C$ respectively, and similarly draw $m_1$ and $m_2$ through $Y$ parallel to $A B$ and $B C$ respectively. If we draw $P = \ell_1 \cap m_2$ and $Q = \ell_2 \cap m_1$, then $X P Y Q$ is a parallelogram, so intersecting $P Q$ and $X Y$ gives the midpoint of $X Y$.

As for the remaining case, one can draw $A C$ and construct the midpoint $P$ of $A C$ by the construction described above. Since $X Y$ can be parallel to at most one of the sides $A B, B C$ and $A C$, we can pick the two non-parallel sides, and use the above construction to draw the midpoint of $X Y$.

Now for the main problem, note that if no two of the $1011$ chosen segments share an endpoint, then we have at least $2 \cdot 1011 = 2022$ distinct endpoints, a contradiction. Thus there must be two segments $A B$ and $B C$ which have their midpoints marked. Since no three of the chosen $2021$ points were collinear, $A B$ and $B C$ are not parallel, so using lemma 2, Vikram can construct the midpoint of any other segment, in particular, the segment chosen by Betal.

Solution 2.

As in the previous solution, note that there exist $A B$ and $A C$ whose midpoints $C^{\prime}$ and $B^{\prime}$ are marked. Using the straightedge, Vikram can draw the two medians $A C^{\prime}$ and $A B^{\prime}$ and obtain their intersection, the centroid $G$ of $\triangle A B C$. Now intersecting $A G$ with $B C$ gives $A^{\prime}$, the midpoint of $B C$.

Lemma Given a point $P$ not on $A B, A C$, Vikram can draw the midpoint of $P A$.

Proof. If $P B \parallel A C$ and $P C \parallel A B$, then $P B A C$ is a parallelogram, in which case $A^{\prime}$ constructed above is the midpoint of $P A$. Without loss of generality, we may assume $P B \nparallel A C$.

Using the straightedge, one can mark the points $D = P B \cap A C$ and $P B \cap A^{\prime} C^{\prime} = D^{\prime}$. Since $C A \parallel A^{\prime} C^{\prime}$, we have

$$\frac{B D^{\prime}}{D^{\prime} D} = \frac{B C^{\prime}}{C^{\prime} A} = 1$$

so $D^{\prime}$ is the midpoint of $B D$. Now in $\triangle A B D$, two midpoints $C^{\prime}$ and $D^{\prime}$ are known, so the midpoint $Q^{\prime}$ of $A D$ can be constructed using the centroid construction outlined before. Let $P^{\prime} = C^{\prime} Q^{\prime} \cap P A$; this exists as $C^{\prime} Q^{\prime} \parallel B P \nparallel A P$. As before, $C^{\prime} P^{\prime} \parallel B P$, so

$$\frac{A P^{\prime}}{P^{\prime} P} = \frac{A C^{\prime}}{C^{\prime} B} = 1$$

which means $P^{\prime}$ is the desired midpoint of $P A$.

Now suppose we need to find the midpoint of $P Q$. If $P, Q$ are different points from $A$, then one can draw the midpoints of $A P$ and $A Q$ using the lemma. Then by using the centroid of $\triangle A P Q$, one can find the midpoint of $P Q$ as we did for $B C$. If $P$ or $Q$ is $A$, the above lemma immediately yields the required midpoint.