51st IMO Shortlisted Problems

First, we prove the key lemma, and then we show how to apply it to finish the solution. Let $n_1,\dots ,n_k$ be positive integers. By an $n_1\times n_2\times \cdots \times n_k$ grid we mean the set $N=\left\{\left(a_1,\dots ,a_k\right):a_i\in \mathbb{Z},0\le a_i\le n_i-1\right\}$; the elements of $N$ will be referred to as points. In this grid, we define a subgrid as a subset of the form $$\begin{array}{c}L=\left\{\left(b_1,\dots ,b_k\right)\in N:b_{i_1}=x_{i_1},\dots ,b_{i_t}=x_{i_t}\right\}\end{array}\text{\hspace{1em}(1)}$$ where $I=\left\{i_1,\dots ,i_t\right\}$ is an arbitrary nonempty set of indices, and $x_{i_j}\in [0,n_{i_j}-1]$ $(1\le j\le t)$ are fixed integer numbers. Further, we say that a subgrid (1) is orthogonal to the $i$th coordinate axis if $i\in I$, and that it is parallel to the $i$th coordinate axis otherwise.

Lemma. Assume that the grid $N$ is covered by subgrids $L_1,L_2,\dots ,L_s$ (this means $N={\bigcup }_{i=1}^s{L}_i$ ) so that (ii') each subgrid contains a point which is not covered by other subgrids; (iii) for each coordinate axis, there exists a subgrid $L_i$ orthogonal to this axis. Then $$s\ge 1+\sum _{i=1}^k\left(n_i-1\right)$$ Proof. Assume to the contrary that $s\le {\sum }_i\left(n_i-1\right)=s^{\prime }$. Our aim is to find a point that is not covered by $L_1,\dots ,L_s$. The idea of the proof is the following. Imagine that we expand each subgrid to some maximal subgrid so that for the $i$th axis, there will be at most $n_i-1$ maximal subgrids orthogonal to this axis. Then the desired point can be found easily: its $i$th coordinate should be that not covered by the maximal subgrids orthogonal to the $i$th axis. Surely, the conditions for existence of such expansion are provided by Hall's lemma on matchings. So, we will follow this direction, although we will apply Hall's lemma to some subgraph instead of the whole graph. Construct a bipartite graph $G=\left(V\cup V^{\prime },E\right)$ as follows. Let $V=\left\{L_1,\dots ,L_s\right\}$, and let $V^{\prime }=\left\{v_{ij}:1\le i\le s,1\le j\le n_i-1\right\}$ be some set of $s^{\prime }$ elements. Further, let the edge $\left(L_m,v_{ij}\right)$ appear iff $L_m$ is orthogonal to the $i$th axis. For each subset $W\subset V$, denote $$f(W)=\left\{v\in V^{\prime }:(L,v)\in E\text{ for some }L\in W\right\}$$ Notice that $f(V)=V^{\prime }$ by (iii). Now, consider the set $W\subset V$ containing the maximal number of elements such that $|W|>|f(W)|$; if there is no such set then we set $W=\varnothing$. Denote $W^{\prime }=f(W),U=V\backslash W,U^{\prime }=V^{\prime }\backslash W^{\prime }$. By our assumption and the Lemma condition, $|f(V)|=|V^{\prime }|\ge |V|$, hence $W\ne V$ and $U\ne \varnothing$. Permuting the coordinates, we can assume that $U^{\prime }=\left\{v_{ij}:1\le i\le \ell \right\},W^{\prime }=\left\{v_{ij}:\ell +1\le i\le k\right\}$. Consider the induced subgraph $G^{\prime }$ of $G$ on the vertices $U\cup U^{\prime }$. We claim that for every $X\subset U$, we get $|f(X)\cap U^{\prime }|\ge |X|$ (so $G^{\prime }$ satisfies the conditions of Hall's lemma). Actually, we have $|W|\ge |f(W)|$, so if $|X|>|f(X)\cap U^{\prime }|$ for some $X\subset U$, then we have $$|W\cup X|=|W|+|X|>|f(W)|+|f(X)\cap U^{\prime }|=|f(W)\cup (f(X)\cap U^{\prime })|=|f(W\cup X)|.$$ This contradicts the maximality of $|W|$. Thus, applying Hall's lemma, we can assign to each $L\in U$ some vertex $v_{ij}\in U^{\prime }$ so that to distinct elements of $U$, distinct vertices of $U^{\prime }$ are assigned. In this situation, we say that $L\in U$ corresponds to the $i$th axis, and write $g(L)=i$. Since there are $n_i-1$ vertices of the form $v_{ij}$, we get that for each $1\le i\le \ell$, not more than $n_i-1$ subgrids correspond to the $i$th axis. Finally, we are ready to present the desired point. Since $W\ne V$, there exists a point $b=\left(b_1,b_2,\dots ,b_k\right)\in N\backslash \left({\cup }_{L\in W}L\right)$. On the other hand, for every $1\le i\le \ell$, consider any subgrid $L\in U$ with $g(L)=i$. This means exactly that $L$ is orthogonal to the $i$th axis, and hence all its elements have the same $i$th coordinate $c_L$. Since there are at most $n_i-1$ such subgrids, there exists a number $0\le a_i\le n_i-1$ which is not contained in a set $\left\{c_L:g(L)=i\right\}$. Choose such number for every $1\le i\le \ell$. Now we claim that point $a=\left(a_1,\dots ,a_{\ell },b_{\ell +1},\dots ,b_k\right)$ is not covered, hence contradicting the Lemma condition. Surely, point $a$ cannot lie in some $L\in U$, since all the points in $L$ have $g(L)$th coordinate $c_L\ne a_{g(L)}$. On the other hand, suppose that $a\in L$ for some $L\in W$; recall that $b\notin L$. But the points $a$ and $b$ differ only at first $\ell$ coordinates, so $L$ should be orthogonal to at least one of the first $\ell$ axes, and hence our graph contains some edge $\left(L,v_{ij}\right)$ for $i\le \ell$. It contradicts the definition of $W^{\prime }$. The Lemma is proved.

Now we turn to the problem. Let $d_j$ be the step of the progression $P_j$. Note that since $n=$ l.c.m. $\left(d_1,\dots ,d_s\right)$, for each $1\le i\le k$ there exists an index $j(i)$ such that $p_i^{{\alpha }_i}\mid d_{j(i)}$. We assume that $n>1$; otherwise the problem statement is trivial. For each $0\le m\le n-1$ and $1\le i\le k$, let $m_i$ be the residue of $m$ modulo $p_i^{{\alpha }_i}$, and let $m_i=\overline{r_{i{\alpha }_i}\dots r_{i1}}$ be the base $p_i$ representation of $m_i$ (possibly, with some leading zeroes). Now, we put into correspondence to $m$ the sequence $r(m)=\left(r_{11},\dots ,r_{1{\alpha }_1},r_{21},\dots ,r_{k{\alpha }_k}\right)$. Hence $r(m)$ lies in a $\underset{{\alpha }_1\text{ times}}{\underbrace{p_1\times \cdots \times p_1}}\times \cdots \times \underset{{\alpha }_k\text{ times}}{\underbrace{p_k\times \cdots \times p_k}}\mathrm{grid}N$. Surely, if $r(m)=r\left(m^{\prime }\right)$ then $p_i^{{\alpha }_i}\mid m_i-m_i^{\prime }$, which follows $p_i^{{\alpha }_i}\mid m-m^{\prime }$ for all $1\le i\le k$; consequently, $n\mid m-m^{\prime }$. So, when $m$ runs over the set $\{0,\dots ,n-1\}$, the sequences $r(m)$ do not repeat; since $|N|=n$, this means that $r$ is a bijection between $\{0,\dots ,n-1\}$ and $N$. Now we will show that for each $1\le i\le s$, the set $L_i=\left\{r(m):m\in P_i\right\}$ is a subgrid, and that for each axis there exists a subgrid orthogonal to this axis. Obviously, these subgrids cover $N$, and the condition (ii') follows directly from (ii). Hence the Lemma provides exactly the estimate we need. Consider some $1\le j\le s$ and let $d_j=p_1^{{\gamma }_1}\dots p_k^{{\gamma }_k}$. Consider some $q\in P_j$ and let $r(q)=\left(r_{11},\dots ,r_{k{\alpha }_k}\right)$. Then for an arbitrary $q^{\prime }$, setting $r\left(q^{\prime }\right)=\left(r_{11}^{\prime },\dots ,r_{k{\alpha }_k}^{\prime }\right)$ we have $$q^{\prime }\in P_j⟺p_i^{{\gamma }_i}\mid q-q^{\prime }\text{ for each }1\le i\le k⟺r_{i,t}=r_{i,t}^{\prime }\text{ for all }t\le {\gamma }_i.$$ Hence $L_j=\{\left(r_{11}^{\prime },\dots ,r_{k{\alpha }_k}^{\prime }\right)\in N:r_{i,t}=r_{i,t}^{\prime }$ for all $t\le {\gamma }_i\}$ which means that $L_j$ is a subgrid containing $r(q)$. Moreover, in $L_{j(i)}$, all the coordinates corresponding to $p_i$ are fixed, so it is orthogonal to all of their axes, as desired.

Comment 1. The estimate in the problem is sharp for every $n$. One of the possible examples is the following one. For each $1\le i\le k,0\le j\le {\alpha }_i-1,1\le k\le p-1$, let $$P_{i,j,k}=k{p}_i^j+p_i^{j+1}\mathbb{Z}$$ and add the progression $P_0=n\mathbb{Z}$. One can easily check that this set satisfies all the problem conditions. There also exist other examples. On the other hand, the estimate can be adjusted in the following sense. For every $1\le i\le k$, let $0={\alpha }_{i0},{\alpha }_{i1},\dots ,{\alpha }_{i{h}_i}$ be all the numbers of the form ${\mathrm{ord}}_{p_i}\left(d_j\right)$ in an increasing order (we delete the repeating occurences of a number, and add a number $0={\alpha }_{i0}$ if it does not occur). Then, repeating the arguments from the solution one can obtain that $$s\ge 1+\sum _{i=1}^k\sum _{j=1}^{h_i}\left(p^{{\alpha }_j-{\alpha }_{j-1}}-1\right)$$ Note that $p^{\alpha }-1\ge \alpha (p-1)$, and the equality is achieved only for $\alpha =1$. Hence, for reaching the minimal number of the progressions, one should have ${\alpha }_{i,j}=j$ for all $i,j$. In other words, for each $1\le j\le {\alpha }_i$, there should be an index $t$ such that ${\mathrm{ord}}_{p_i}\left(d_t\right)=j$.

---

Alternative solution.

We start with introducing some notation. For positive integer $r$, we denote $[r]=\{1,2,\dots ,r\}$. Next, we say that a set of progressions $\mathcal{P}=\{P_1,\dots ,P_s\}$ cover $\mathbb{Z}$ if each integer belongs to some of them; we say that this covering is minimal if no proper subset of $\mathcal{P}$ covers $\mathbb{Z}$. Obviously, each covering contains a minimal subcovering.

Next, for a minimal covering $\{P_1,\dots ,P_s\}$ and for every $1\le i\le s$, let $d_i$ be the step of progression $P_i$, and $h_i$ be some number which is contained in $P_i$ but in none of the other progressions. We assume that $n>1$, otherwise the problem is trivial. This implies $d_i>1$, otherwise the progression $P_i$ covers all the numbers, and $n=1$.

We will prove a more general statement, namely the following

Claim. Assume that the progressions $P_1,\dots ,P_s$ and number $n=p_1^{{\alpha }_1}\dots p_k^{{\alpha }_k}>1$ are chosen as in the problem statement. Moreover, choose some nonempty set of indices $I=\{i_1,\dots ,i_t\}\subseteq [k]$ and some positive integer ${\beta }_i\le {\alpha }_i$ for every $i\in I$. Consider the set of indices $$T=\{j:1\le j\le s,\text{ and }{p}_i^{{\alpha }_i-{\beta }_i+1}\mid d_j\text{ for some }i\in I\}$$ Then $$\begin{array}{c}|T|\ge 1+\sum _{i\in I}{\beta }_i\left(p_i-1\right)\end{array}\text{\hspace{1em}(2)}$$ Observe that the Claim for $I=[k]$ and ${\beta }_i={\alpha }_i$ implies the problem statement, since the left-hand side in (2) is not greater than $s$. Hence, it suffices to prove the Claim.

1. First, we prove the Claim assuming that all $d_j$'s are prime numbers. If for some $1\le i\le k$ we have at least $p_i$ progressions with the step $p_i$, then they do not intersect and hence cover all the integers; it means that there are no other progressions, and $n=p_i$; the Claim is trivial in this case. Now assume that for every $1\le i\le k$, there are not more than $p_i-1$ progressions with step $p_i$; each such progression covers the numbers with a fixed residue modulo $p_i$, therefore there exists a residue $q_i\mathrm{mod}{p}_i$ which is not touched by these progressions. By the Chinese Remainder Theorem, there exists a number $q$ such that $q\equiv q_i\left(\mathrm{mod}{p}_i\right)$ for all $1\le i\le k$; this number cannot be covered by any progression with step $p_i$, hence it is not covered at all. A contradiction.

2. Now, we assume that the general Claim is not valid, and hence we consider a counterexample $\{P_1,\dots ,P_s\}$ for the Claim; we can choose it to be minimal in the following sense: - the number $n$ is minimal possible among all the counterexamples; - the sum ${\sum }_i{d}_i$ is minimal possible among all the counterexamples having the chosen value of $n$. As was mentioned above, not all numbers $d_i$ are primes; hence we can assume that $d_1$ is composite, say $p_1\mid d_1$ and $d_1^{\prime }=\frac{d_1}{p_1}>1$. Consider a progression $P_1^{\prime }$ having the step $d_1^{\prime }$, and containing $P_1$. We will focus on two coverings constructed as follows. (i) Surely, the progressions $P_1^{\prime },P_2,\dots ,P_s$ cover $\mathbb{Z}$, though this covering in not necessarily minimal. So, choose some minimal subcovering ${\mathcal{P}}^{\prime }$ in it; surely $P_1^{\prime }\in {\mathcal{P}}^{\prime }$ since $h_1$ is not covered by $P_2,\dots ,P_s$, so we may assume that ${\mathcal{P}}^{\prime }=\{P_1^{\prime },P_2,\dots ,P_{s^{\prime }}\}$ for some $s^{\prime }\le s$. Furthermore, the period of the covering ${\mathcal{P}}^{\prime }$ can appear to be less than $n$; so we denote this period by $$n^{\prime }=p_1^{{\alpha }_1-{\sigma }_1}\dots p_k^{{\alpha }_k-{\sigma }_k}=\text{ l.c.m. }\left(d_1^{\prime },d_2,\dots ,d_{s^{\prime }}\right)$$ Observe that for each $P_j\notin {\mathcal{P}}^{\prime }$, we have $h_j\in P_1^{\prime }$, otherwise $h_j$ would not be covered by $\mathcal{P}$. (ii) On the other hand, each nonempty set of the form $R_i=P_i\cap P_1^{\prime }(1\le i\le s)$ is also a progression with a step $r_i=$ l.c.m. $\left(d_i,d_1^{\prime }\right)$, and such sets cover $P_1^{\prime }$. Scaling these progressions with the ratio $1/d_1^{\prime }$, we obtain the progressions $Q_i$ with steps $q_i=r_i/d_1^{\prime }$ which cover $\mathbb{Z}$. Now we choose a minimal subcovering $\mathcal{Q}$ of this covering; again we should have $Q_1\in \mathcal{Q}$ by the reasons of $h_1$. Now, denote the period of $\mathcal{Q}$ by $$n^{\prime \prime }=\text{ l.c.m. }\{q_i:Q_i\in \mathcal{Q}\}=\frac{\text{ l.c.m. }\{r_i:Q_i\in \mathcal{Q}\}}{d_1^{\prime }}=\frac{p_1^{{\gamma }_1}\dots p_k^{{\gamma }_k}}{d_1^{\prime }}$$ Note that if $h_j\in P_1^{\prime }$, then the image of $h_j$ under the scaling can be covered by $Q_j$ only; so, in this case we have $Q_j\in \mathcal{Q}$. Our aim is to find the desired number of progressions in coverings $\mathcal{P}$ and $\mathcal{Q}$. First, we have $n\ge n^{\prime }$, and the sum of the steps in ${\mathcal{P}}^{\prime }$ is less than that in $\mathcal{P}$; hence the Claim is valid for ${\mathcal{P}}^{\prime }$. We apply it to the set of indices $I^{\prime }=\{i\in I:{\beta }_i>{\sigma }_i\}$ and the exponents ${\beta }_i^{\prime }={\beta }_i-{\sigma }_i$; hence the set under consideration is $$T^{\prime }=\{j:1\le j\le s^{\prime },\text{ and }{p}_i^{({\alpha }_i-{\sigma }_i)-{\beta }_i^{\prime }+1}=p_i^{{\alpha }_i-{\beta }_i+1}\mid d_j\text{ for some }i\in I^{\prime }\}\subseteq T\cap [s^{\prime }]$$ and we obtain that $$|T\cap [s^{\prime }]|\ge |T^{\prime }|\ge 1+\sum _{i\in I^{\prime }}({\beta }_i-{\sigma }_i)(p_i-1)=1+\sum _{i\in I}({\beta }_i-{\sigma }_i{)}_{+}(p_i-1),$$ where $(x{)}_{+}=\max \{x,0\}$; the latter equality holds as for $i\notin I^{\prime }$ we have ${\beta }_i\le {\sigma }_i$. Observe that $x=(x-y{)}_{+}+\min \{x,y\}$ for all $x,y$. So, if we find at least $$G=\sum _{i\in I}\min \{{\beta }_i,{\sigma }_i\}(p_i-1)$$ indices in $T\cap \{s^{\prime }+1,\dots ,s\}$, then we would have $$|T|=|T\cap [s^{\prime }]|+|T\cap \{s^{\prime }+1,\dots ,s\}|\ge 1+\sum _{i\in I}\left(({\beta }_i-{\sigma }_i{)}_{+}+\min \{{\beta }_i,{\sigma }_i\}\right)(p_i-1)=1+\sum _{i\in I}{\beta }_i(p_i-1),$$ thus leading to a contradiction with the choice of $\mathcal{P}$. We will find those indices among the indices of progressions in $\mathcal{Q}$.

3. Now denote $I^{\prime \prime }=\{i\in I:{\sigma }_i>0\}$ and consider some $i\in I^{\prime \prime }$; then $p_i^{{\alpha }_i}\nmid n^{\prime }$. On the other hand, there exists an index $j(i)$ such that $p_i^{{\alpha }_i}\mid d_{j(i)}$; this means that $d_{j(i)}\nmid n^{\prime }$ and hence $P_{j(i)}$ cannot appear in ${\mathcal{P}}^{\prime }$, so $j(i)>s^{\prime }$. Moreover, we have observed before that in this case $h_{j(i)}\in P_1^{\prime }$, hence $Q_{j(i)}\in \mathcal{Q}$. This means that $q_{j(i)}\mid n^{\prime \prime }$, therefore ${\gamma }_i={\alpha }_i$ for each $i\in I^{\prime \prime }$ (recall here that $q_i=r_i/d_1^{\prime }$ and hence $d_{j(i)}|r_{j(i)}|d_1^{\prime }{n}^{\prime \prime }$). Let $d_1^{\prime }=p_1^{{\tau }_1}\dots p_k^{{\tau }_k}$. Then $n^{\prime \prime }=p_1^{{\gamma }_1-{\tau }_1}\dots p_k^{{\gamma }_i-{\tau }_i}$. Now, if $i\in I^{\prime \prime }$, then for every $\beta$ the condition $p_i^{({\gamma }_i-{\tau }_i)-\beta +1}\mid q_j$ is equivalent to $p_i^{{\alpha }_i-\beta +1}\mid r_j$. Note that $n^{\prime \prime }\le n/d_1^{\prime }<n$, hence we can apply the Claim to the covering $\mathcal{Q}$. We perform this with the set of indices $I^{\prime \prime }$ and the exponents ${\beta }_i^{\prime \prime }=\min \{{\beta }_i,{\sigma }_i\}>0$. So, the set under consideration is $$\begin{array}{rl}{T}^{\prime \prime }& =\{j:Q_j\in \mathcal{Q},\text{ and }{p}_i^{({\gamma }_i-{\tau }_i)-\min \{{\beta }_i,{\sigma }_i\}+1}\mid q_j\text{ for some }i\in I^{\prime \prime }\}\\ & =\{j:Q_j\in \mathcal{Q},\text{ and }{p}_i^{{\alpha }_i-\min \{{\beta }_i,{\sigma }_i\}+1}\mid r_j\text{ for some }i\in I^{\prime \prime }\}\end{array}$$ and we obtain $|T^{\prime \prime }|\ge 1+G$. Finally, we claim that $T^{\prime \prime }\subseteq T\cap (\{1\}\cup \{s^{\prime }+1,\dots ,s\})$; then we will obtain $|T\cap \{s^{\prime }+1,\dots ,s\}|\ge G$, which is exactly what we need. To prove this, consider any $j\in T^{\prime \prime }$. Observe first that ${\alpha }_i-\min \{{\beta }_i,{\sigma }_i\}+1>{\alpha }_i-{\sigma }_i\ge {\tau }_i$, hence from $p_i^{{\alpha }_i-\min \{{\beta }_i,{\sigma }_i\}+1}\mid r_j=$ l.c.m. $\left(d_1^{\prime },d_j\right)$ we have $p_i^{{\alpha }_i-\min \{{\beta }_i,{\sigma }_i\}+1}\mid d_j$, which means that $j\in T$. Next, the exponent of $p_i$ in $d_j$ is greater than that in $n^{\prime }$, which means that $P_j$ \notin ${\mathcal{P}}^{\prime }$. This may appear only if $j=1$ or $j>s^{\prime }$, as desired. This completes the proof.