We can slightly restate the problem. n is given. We seek to cover $ [0,n-1]$ with minimum number of progressions with steps dividing n and: 1) there is no progression when omitted, $ [0,n-1] $ still to be covered, i.e. there is no redundency of progressions. 2) n is lcm of all progressions' steps. Let begin with obvious observation: If there are some progressions and $lcm $ of their steps equals $M$, then we can consider the points covered by them only in the interval $[0,M-1]$ and then periodically extend this interval with period M. Let first consider the case $ n=p^\alpha $. Let $s_1$ be the number of progressions with steps multiple by $p^\alpha$. If these progressions be omited, lcd of the rest progressions' steps will be $\leq p^{\alpha -1}$ . Then $ \exists r_0 \in [0,p^{\alpha-1}-1] $ which is uncovered by all these progressions, because otherwise all points will be covered by them which contradicts 1). Moreover there will be uncovered by them series:$S:=\{r_0+jp^{\alpha -1} \}, j=0,1,...,p-1$ Every progression with step divisible by $p^\alpha$ could cover at most 1 poin of series $S$, so if $s_1$ is their number, $s_1 \geq p$. Let consider all progressions with steps multiple by $p^{\alpha-1}$ but not by $p^{\alpha}$, and $s_2$ be their number. If there remain only progressions with steps divisible by $p^{\alpha-2}$, there will be uncovered by them point $r_0 \in [0,p^{\alpha-2}-1]$ and so will the series $S:=\{r_0+j p^{\alpha-2}\}, j=0,1,...,p^2-1$. The $s_1$ progressions with step divisible by $p^\alpha$ cover at most 1 point of $S$, $s_2$ progressions with steps divisible by $p^{\alpha-1}$ each of them covers at most $p$ points of $S$, so:$s_2 p +s_1 \geq p^2, s_1 \geq p, \, \Rightarrow \,s_1+s_2 \geq p + p-1$ In similar way we obtain $s \geq \alpha (p-1) +1$. Inspired by this particular case let consider the general one. $n=p_1^{\alpha_1}...p_k^{\alpha_k}$. Denote by $P$ the set of all given progressions, if $A \subset P $, by $lcm(A)$ denote $lcm\{step(p): p \in A \}$. Let $n_1=max\{lcm(A): A \subset P, lcm(A) < n \} $ and $P_1$ be the maximum such set, i.e. $lcm(P_1)=n_1, \, \forall p \in P\setminus P_1, lcm(P_1 \cup \{p\})=n > n_1 $ Now if we omit all progressions $P\setminus P_1$ , there will be uncovered point $r_0 \in [0,n_1-1]$, and because of that a series $S=\{r_0+j n_1\}, j=0,..., \frac{n}{n_1}-1$ of $ \frac{n}{n_1}$ uncovered points on$[0,n-1] $. Every progression in $P\setminus P_1$ covers at most 1 point of $S$ Proof: if $p \in P\setminus P_1 $ is a progression with step $d$ that covers two points of $S, r_0+j_1 n_1, r_0+j_2 n_1 $, then $d/(j_2-j_1) n_1, \, n=lcm(d,n_1)\leq (j_2-j_1)n_1 < n$, contradiction. So the number $s_1$ of progressions $P\setminus P_1$ is at least $ \frac{n}{n_1}$. Now let $ n_2=max\{lcm(A), \, A \subset P_1,\, lcm(A) < n_1\}$, and $P_2,\, P_2 \subset P_1 \subset P $ be maximum set with $n_2=lcm(P_2)$, i.e. for all $p \in P_1\setminus P_2,\, lcm(P_2 \cup \{p\}) > n_2.$ If only progressions in $P_2$ remain, all the others omited, there will be uncovered point $r_0 \in [0,n_2-1]$ and series $S=\{r_0+j n_2\}, \, j=0,...,\frac{n}{n_2}-1$ of $\frac{n}{n_2}$ uncovered points on $[0, n-1]$. Everey progression in $P\setminus P_1$ will cover at most 1 point of $S$, and a progression in $P_1\setminus P_2$ wil cover at most $ \frac{n}{n_1}$ points of $S$. If $s_2$ is number of progressions in $P_1\setminus P_2$ then: $s_2 \frac{n}{n_1} + s_1 \geq \frac{n}{n_2}$. Because of $s_1 \geq \frac{n}{n_1} \, \Rightarrow s_1+s_2 \geq \frac{n}{n_1} + \frac{n_1}{n_2}-1$ Carry on in similar way: $ 1=n_l < n_{l-1} < ... < n_2 < n_1 <n , \, n_{j_1}/n_{j_2},\, j_1 > j_2 $ (3) $s \geq \frac{n}{n_1} + (\frac{n_1}{n_2}-1)+...+(\frac{n_{l-1}}{n_l}-1) $ One can guess that min of the right hand side of (3) could be attained when $\frac{n_j}{n_{j+1}} $ is prime, and there could be constructed appropriate progressions.

Please edit your post so that it's legible. In the future, use the preview button to view your draft before you post it. Note the LaTeX command \max; you can also use \text{lcm} to get $\text{lcm}$, and you can use > and < to get greater-than and less-than signs (no special command needed).

Sorry, JBL, it is now corrected.

http://www.math.uga.edu/~rlivings/pubs/dcsSurvey.pdf

dgrozev wrote: Inspired by this particular case let consider the general one. $n=p_1^{\alpha_1}...p_k^{\alpha_k}$. Denote by $P$ the set of all given progressions, if $A \subset P $, by $lcm(A)$ denote $lcm\{step(p): p \in A \}$. Let $n_1=max\{lcm(A): A \subset P, lcm(A) < n \} $ and $P_1$ be the maximum such set, i.e. $lcm(P_1)=n_1, \, \forall p \in P\setminus P_1, lcm(P_1 \cup \{p\})=n > n_1 $ Now if we omit all progressions $P\setminus P_1$ , there will be uncovered point $r_0 \in [0,n_1-1]$, and because of that a series $S=\{r_0+j n_1\}, j=0,..., \frac{n}{n_1}-1$ of $ \frac{n}{n_1}$ uncovered points on$[0,n-1] $. Every progression in $P\setminus P_1$ covers at most 1 point of $S$ Proof: if $p \in P\setminus P_1 $ is a progression with step $d$ that covers two points of $S, r_0+j_1 n_1, r_0+j_2 n_1 $, then $d/(j_2-j_1) n_1, \, n=lcm(d,n_1)\leq (j_2-j_1)n_1 < n$, contradiction. So the number $s_1$ of progressions $P\setminus P_1$ is at least $ \frac{n}{n_1}$. Now let $ n_2=max\{lcm(A), \, A \subset P_1,\, lcm(A) < n_1\}$, and $P_2,\, P_2 \subset P_1 \subset P $ be maximum set with $n_2=lcm(P_2)$, i.e. for all $p \in P_1\setminus P_2,\, lcm(P_2 \cup \{p\}) > n_2.$ If only progressions in $P_2$ remain, all the others omited, there will be uncovered point $r_0 \in [0,n_2-1]$ and series $S=\{r_0+j n_2\}, \, j=0,...,\frac{n}{n_2}-1$ of $\frac{n}{n_2}$ uncovered points on $[0, n-1]$. Everey progression in $P\setminus P_1$ will cover at most 1 point of $S$, and a progression in $P_1\setminus P_2$ wil cover at most $ \frac{n}{n_1}$ points of $S$. How do you prove the red statement?

Funny. R.K Guy cites this very result as having been established by R. J. Simpson. From when do we propose established theorems for the IMO ?

@math154: Sorry, I really don't know what I meant when I wrote this, but apparently the red statement is not generally true. About the history- the link cited by mahanmath states that a weaker version of this result was first proposed as a conjecture by J. Mylcieski and W. Sierpinski and proved by S. Znam. Then it was further generalized and proved by R. Simpson in the form equivalent to this problem.

For the sake of completeness, here's a (IMO) somewhat simplified version of Simpson's proof, with a little motivation. I meant to post a while ago but got caught up in some things (also this is really annoying to write up...). Define $f(n) = \sum_{i=1}^{k} \alpha_i(p_i - 1)$ ($f(1) = 0$ for convenience), $S=\{P_i\}$, and suppose $P_i=a_i\pmod{d_i}$ for $i=1,2,\ldots,s$. For a set of indices $A$, let $L(A) = \operatorname{lcm}_{i\in A}(d_i)$, so we want to show $|S| \ge 1+f(L(S))$. Note that $f(mn) = f(m)+f(n)$ for positive integers $m,n$. For $i=0,1,\ldots,p_1-1$, let $S_i$ be the set of indices of a minimal cover of the residues $i\pmod{p_1}$. Clearly $S = \bigcup_{i=0}^{p_1-1} S_i$ and by (ii), each $S_i$ contains $j$ with $p_1\mid d_j$ (which of course requires $a_j \equiv i\pmod{p_1}$). Similarly, $S_i,S_j$ can only intersect at indices $l$ with $p_1\nmid l$. Furthermore, for fixed $j$, there must exist $i$ such that $p_j^{\alpha_j}\mid L(S_i)$. When $k=1$, it's obvious how to proceed: WLOG $L(S_0) = p_1^{\alpha_1}$; then noting that $P_j\cap 0\pmod{p_1}$ is an AP with step divisible by $p_1$, we get \begin{align*} |S| &\ge |S_0|+|S_1\setminus S_0|+\cdots+|S_{p_1-1}\setminus S_0,\ldots,S_{p_1-2}| \\ &\ge 1+f(L(S_0)/p_1)+p-1 = 1+f(L(S)) \end{align*} by the inductive hypothesis (base case is trivial), as desired. For $k>1$, we'll need something a bit stronger, but it's natural to conjecture something like $|S_i\setminus T_{i-1}| \ge 1+ f\left(\frac{L(T_i)}{L(T_{i-1})}\right)$ for $i\ge1$, where $T_i = \bigcup_{j=0}^{i}S_j$ (which clearly suffices). Thus we try to prove the following: Quote: If $S$ is a minimal covering set of the integers with $n=L(S)$, then for any $m\mid n$ with $m<n$, $S$ has at least $1+f(n/m)$ progressions $P_j=a_j\pmod{d_j}$ with $d_j\nmid m$. Equality holds, for instance, when $S$ consists of $0\pmod{n}$ and for each $i$, $jp_i^{\ell-1}\pmod{p_i^{\ell}}$ for $j=1,2,\ldots,p_i-1$, $\ell=1,2,\ldots,k$. To set an inductive proof (on $n$) up, let $M=\{j : d_j\mid m\}$. WLOG $p_1\mid n/m$ (since $m<n$) and $p_1^{\alpha_1}\mid L(S_0)$. Fix $i$; for $P_j\in S_i$, define $P^{(i)}_j = a^{(i)}_j \pmod{d^{(i)}_j}$ so that $P_j \cap i\pmod{p_1} = p_1P^{(i)}_j$. Note that $d^{(i)}_j = \frac{d_j}{\gcd(p_1,d_j)}$ and $S^{(i)}_i$ (slight abuse of notation here) must be a minimal cover of the integers (since $S_i$ is a minimal cover of $i\pmod{p_1}$). Observe that $L(S^{(i)}_i) = L(S_i)/p_1$ and for any positive integer $t$, $d^{(i)}_j\nmid \frac{t}{(t,p_1)}\implies d_j\nmid t$. (*) First we consider $S_0\setminus M$. If $L(S_0)/p_1 = (m,L(S_0))/(m,L(S_0),p_1)$, this is obvious from $p_1^{\alpha_1}\mid L(S_0)$. Otherwise, $d_j\mid m$ iff $d_j\mid (m,L(S_0))$, so by (*), $|S_0\setminus M|$ is at least the number of $j\in S_0$ such that $d^{(0)}_j \nmid (m,L(S_0))/(m,L(S_0),p_1)$, which is at least \begin{align*} 1+f\left(\frac{|S^{(0)}_0|}{(m,L(S_0))/(m,L(S_0),p_1)}\right) &= 1+f\left(\frac{L(S_0)/p_1}{(m,L(S_0))/(m,L(S_0),p_1)}\right) \\ &= 1+f\left(\frac{(m,L(S_0),p_1)}{p_1}\frac{\operatorname{lcm}(m,L(S_0))}{m}\right) \end{align*} by the inductive hypothesis, since $(m,L(S_0))\mid L(S_0)$ forces $(m,L(S_0))/(m,L(S_0),p_1)\mid L(S_0)/p_1$. For $i\ge1$, $S_i\setminus M,T_{i-1}$ contains all $j\in S_i$ such that $d_j\nmid m$ and $d_j\nmid L(T_{i-1})$, and thus all $j$ with $d_j\nmid \operatorname{lcm}(m,L(T_{i-1}))$ (although this is a weaker condition), or equivalently, $d_j\nmid (L(S_i),\operatorname{lcm}(m,L(T_{i-1})))$. Using (*) as in the previous paragraph, $|S_i\setminus M,T_{i-1}|$ is at least the number of $j\in S_i$ such that $d^{(i)}_j\nmid (L(S_i),\operatorname{lcm}(m,L(T_{i-1})))/p_1 = L(S_i)\operatorname{lcm}(m,L(T_{i-1}))/p_1\operatorname{lcm}(m,L(T_i))$ (note $p_1\mid T_0\mid L(T_{i-1})$ and of course $p_1\mid L(S_i)$). If $L(S_i)/p_1 > (L(S_i),\operatorname{lcm}(m,L(T_{i-1})))/p_1$, we get a lower bound of \[ 1+f\left(\frac{L(S_i)/p_1}{L(S_i)\operatorname{lcm}(m,L(T_{i-1}))/p_1\operatorname{lcm}(m,L(T_i))}\right) = 1+f\left(\frac{\operatorname{lcm}(m,L(T_i))}{\operatorname{lcm}(m,L(T_{i-1}))}\right). \]Otherwise, if $\operatorname{lcm}(m,L(T_i)) = \operatorname{lcm}(m,L(T_{i-1}))$, we get a lower bound of $\ge1 = 1+f\left(\frac{\operatorname{lcm}(m,L(T_i))}{\operatorname{lcm}(m,L(T_{i-1}))}\right)$ when $p_1\nmid m$ (as $S_i$ has at least one $j$ with $p_1\mid d_j$, which clearly must be unique to $S_i$) and obviously $\ge0 = f\left(\frac{\operatorname{lcm}(m,L(T_i))}{\operatorname{lcm}(m,L(T_{i-1}))}\right)$ when $p_1\mid m$. Case 1. $p_1\nmid m$. Then $S\setminus M$ has at least $p_1 + f\left(\frac{(m,L(S_0),p_1)}{p_1}\frac{\operatorname{lcm}(m,L(T_{p_1-1}))}{m}\right) = 1+f\left(\frac{n}{m}\right)$ elements, as desired. Case 2. $p_1\mid m$. Then $S\setminus M$ has at least $1 + f\left(\frac{(m,L(S_0),p_1)}{p_1}\frac{\operatorname{lcm}(m,L(T_{p_1-1}))}{m}\right) = 1+f\left(\frac{n}{m}\right)$ elements, so we're done in this case too.

I have not read math154's solution entirely, so I cannot say what the degree of similarity between mine and his solution is, although I sense that they have some underliyng common ideas ( I refer to his taking minimal covers of the congruence classes $\mod p_1$). I think, however, that if one has the idea of taking hyperrectangles (which is not that trivial ), then partitioning it into other hyperrectangles becomes extremely natural. Of course, if we do not generalize the problem (that is not take the summy set $S$ in the third paragraph) complications arise right at the end (how I know this: personal experience). I hope that you'll enjoy this solution: First of all, it is rather clear that we might look at the restrictions of the progressions to the numbers between $0$ and $n-1$. We now shall view these numbers as points of integer coordinates in an appropriately defined hyperrectangle. We shall first define the intervals that define the hyperrectangle and then see the bijection between the points of the hyperrectangle and numbers between $0$ and $n-1$. For each $p_i$, we shall have $a_i$ intervals $[0,p_i-1]$, that is, the points of the hyperrectangle can be characterised as points in $\mathbb{N}^{a_1+\ldots+a_k}$, so that the first $a_1$ coordinates are integers between $0$ and $p_1-1$, the next $a_2$ are integers between $0$ and $p_2-1$ and so on. We now move on to defining a bijection. Let's take a number $x$. The $a_i$ intervals corresponding to $p_i$ will represent $x$'s representation in base $p_i$, in the following way: the first of these intervals will represent the remainder of $x$ when divided by $p_i$, the second interval the remainder when the quotient of the division mentioned earlier is divided by $p_i$ and so on. It is easy to see that this provides us with a bijection. What we are going to do next is to find the images of the progressions. Let a progression $P$ have ratio $r=p_1^{b_1}\cdots p_k^{b_k}$ where $0\leq b_i\leq a_i$ and let's suppose that $a$ is one of the progression's terms. We shall look at the $a_i$ intervals corresponding to $p_i$. The coordinates of the first $b_i$ of these intervals are fully determined by $a$; however, the other $a_i-b_i$ are totally free, which means that given any combination of $a_i-b_i$ numbers between $0$ and $p_i-1$ we may find a term of the progression that has these elements (in the corresponding position) as coordinates. Actually, by using the Chinese Remainder Theorem (or a counting argument), any point of the hyperrectangle that has those first $b_i$ as those of $a$ for each $i$ corresponds to a number of the progression. This means that each progression can be written as the product of some intervals; however, these intervals are not entirely random: for each $p_i$ the intervals are the last $a_i-b_i$ ones. We shall say that this progression \textit{uses} these intervals and does \textit{not use} the other intervals. From now on we shall only work with the hyperrectangle. We now shall make a few remarks and then proceed to prove the problem. First of all, we shall drop the condition that each $p_i$ is a prime number; this will enable us to make induction. Furthermore, because $n$ is the \textit{least} common multiple of the ratios of the progressions, for each $i$ we may find a $j$ so that the ratio of $P_j$ is divisible by $p_i^{a_i}$; this, by what we proved in the last paragraph, means that this progression does not use any of the $a_i$ intervals corresponding to $p_i$. In particular, for any interval we may find a progression that does not use it. Therefore, we shall suppose that no intervals are "interdependent", that is we shall not have $a_i$ intervals corresponding to $p_i$ that depend on each other but rather $a_i$ independent intervals (this is the situation that normally occurs only when $n$ is squarefree, but as we proved earlier we might consider it for a general $n$). We now summarize what we have to prove. We have a hyperrectangle defined by $k$ intervals $[0,n_1]$,$\ldots$, $[0,n_k]$ that is covered by some progressions (which denote hyperrectangles that use some of the $k$ intervals) so that each progression has a point that does not belong to the other progressions and for each interval it is possible to find a progression that does not use it. Then we must prove that the number of progressions is at least $\displaystyle 1+\sum_{i=1}^{k}n_i$. We will actually prove a more general statement: we will consider the hyperrectangle (although now it is not formally one; we shall, however, keep this name) to be the product of an arbitrary set $S$ with the above specified intervals and let progressions be products of some of those intervals and a nonempty subset $S'$ of $S$. We still insist that no progression is useless and that every interval is not used by at least a progression; we shall, however, impose no condition on $S$ and the subsets corresponding to the progressions. What we will prove is that we have at least $\displaystyle 1+\sum_{i=1}^{k}n_i$ (the cardinality of $S$ will not matter). As stated earlier, we shall use induction. First of all, when all the $n_i$ are equal to $0$ the statement is clearly true. We now shall make the induction step (we suppose that the problem holds for any hyperrectangle with $n_1'+\ldots +n_{k'}'<n_1+\ldots n_k$; this sum is what we make induction on, which in particular means that the size of $S$ is not relevant to the induction). As $n_1+\ldots n_k>0$ we can find an $i$ so that $n_i>0$ so we may as well suppose that $i=1$. We now divide our hyperrectangle into two hyperrecatngles: the first one will use the intervals $[0,n_1-1]$, $[0,n_2]$,$\ldots$, $[0,n_k]$ (that is, only the first one is modified) and the set $S$, while the other uses the intervals $[0,n_2]$, $\ldots$, $[0,n_k]$ and the set $S$ (it does not use the first interval, but it is helpful to see it as having a dummy first coordinate equal $n_1$ so that also the second hyperrectangle is included in the original hyperrectangle). We now divide the progressions to the two hyperrectangles; if a progression does not use the interval $[0,n_1]$ then there is nothing to be done, and if it uses the interval we shall divide it into two progressions just as we did with the hyperrectangle. Now, both these hyperrectangles are covered by the progressions; however, the coverings might fail to have the two properties stated in the preceeding paragraph. We will now study these coverings in more detail. We first look at the covering of the first hyperrectangle (the one that uses the interval $[0,n_1-1]$). Suppose that a progression has now become "useless", that is it does not contain a point that does not belong to other progression. If this is the case, we eliminate it from the progressions. We continue this process until every progression has a point that does not belong to other progressions. Let's observe that every eliminated progression uses the interval $[0,n_1-1]$, as otherwise it would be useless in the covering of the original hyperrectangle. We do the same for the covering of the second hyperrectangle and observe that the eliminated progressions were in the original covering progressions that used the interval $[0,n_1]$. Let $x_1$ be the number of progressions in the first covering that do not use the interval $[0,n_1-1]$, $x_2$ the ones that use the interval $[0,n_1-1]$, $x_3$ the number of progressions from the second covering that do not use the interval $[0,n_1]$ in the original covering and finally $x_4$ the number of progressions from the second covering that use the interval $[0,n_1]$ in the original covering. The number of progressions in the original covering may be now computed as $x_1+x_2+x_3+x_4-x_5$ where $x_5$ is the number of progressions from the original covering which use the interval $[0,n_1]$ and have both progressions obtained from its division used in the two coverings (some sort of common part of the two coverings); we have used the fact that for any progression (including the ones that use the interval $[0,n_1]$) we may find at least a progression from the two coverings that corresponds to it (as the only problem might occur at the progressions that use the interval $[0,n_1]$, but if both progressions obtained from its division are not used then it means that the progression itself is useless, false). We now study the second condition of the coverings, that is for each interval we may find a progression that does not use it. Let $S_1$ be the set of indices of the intervals which are not used by at least a progression of the first covering and $S_2$ be the corresponding set for the second covering. $1$ is included in $S_1$, as otherwise the first hyperrectangle would be coverered by progressions using the interval $[0,n_1-1]$ and then these same progression would alone cover the whole original hyperrectangle, fact which has only two possible explanations: either one of the original progressions was useless or all the progressions used the first interval. Both these explanations are in contradiction with the properties of the covering. Furthermore, each other interval (more precisely its index) belongs to at least one of the two sets; otherwise all progressions from the original covering would use that interval. Also let $M$ be the set of all indices (that is, $M=\{1,\ldots ,k\}$). Let us first look at the first covering. Every progression uses the intervals with index in the set $M\backslash S_1$ and supressing these intervals we might consider that we have a covering of the hyperrectangle which uses the intervals in the set $S_1$ (and the set $S$) and now satisfies both properties mentioned in the third paragraph. Therefore we have the inequality $\displaystyle x_1+x_2\geq 1+\sum_{i\in S_1} n_i'$, where $n_i'=n_i$ for $i\geq 2$ and $n_1'=n_1-1$ (also, $n_1'$ appears in the sum from the fact that $1$ is in $S_1$). We now look at the second covering. In the same way we supress the intervals in $M\backslash S_2$. Now we are left with a proper covering of the hyperrectangle generated by the intervals in $S_2$ and the set $S$. We now look at the progressions correponding to those $x_5$ ones. Because they appear in both coverings, all of them use the intervals in $(M\backslash S_1)\cup (M\backslash S_2)$ in the second covering. In the newly created covering, all of them (the $x_5$ ones) use the intervals in $S_2\backslash S_1$. Let $C$ be the set of points these $x_5$ progressions cover. These $x_5$ progressions do not cover the whole hyperrectangle; indeed, from their definition, they are hyperrectangles that resulted from the ones which used the interval $[0,n_1]$, which means that if they covered the hyperrectangle generated by $S_2$ (and $S$) then they would also cover the original hyperrectangle (generated by the intervals in $M$ and the set $S$), a contradiction (either we would have useless progressions or all the progressions would use the first interval). Therefore they do not cover the whole hyperrectangle and then there does exist a point $y$ not covered by them. We assert the following: if a point $y'$ which differs from $y$ only in the coordinates corresponding $S_2\backslash S_1$ then $y'$ is also not covered. Indeed, where $y'$ to be covered by the $x_5$ progressions, then, by invoking the fact that each of the $x_5$ uses the intervals in $S_2\backslash S_1$, $y$ would also have to be covered, false. Therefore, if $C$ is the set of points not covered by the $x_5$ (and so covered by the other $x_3+x_4-x_5$ progressions), $C$ can be written as the product of the intervals with indeces in $S_2\backslash S_1$ and a set $S^{*}$(which normally is richer than $S$). We now apply induction (we may, as only the size of the intervals matter and not the size of $S^{*}$) and obtain that $\displaystyle x_3+x_4-x_5\geq 1+\sum_{i\in S_2\backslash S_1} n_i'$. Combining the two inequalities and the fact that $S_1\cup S_2=M$ we obtain that the number of progressions in the original covering is at least \[2+\sum_{i\in S_1} n_i'+\sum_{i\in S_2\backslash S_1}n_i'=1+\sum_{i\in M} n_1,\] where equality holds because $n_i=n_i'$ unless $i=1$, in which case $n_i=n_i'+1$.

It turns out that this inequality is sharp. For example, take the arithmetic progressions $n\mathbb{Z}$ and $kp_i^j+p_i^{j+1} \mathbb{Z}$ for every triple $(i,j,k)$ with $0 \leq k\leq p-1, 1 \leq i\leq k$, and $0 \leq j\leq \alpha_i-1$

This is a truly remarkable result and the bound is actually tight for every $n$. The following proof is from the official solution.

We will first discuss how this lemma connects with the original problem. Clearly, because $n$ is the LCM of the progression steps, we only need to care about covering $\{0,1,\dots,n-1\}$ with arithmetic progressions. From now on $P_1,\dots,P_s$ will be restricted on $\{0,1,\dots,n-1\}$, possibly having only one or two terms. Build a grid $$P = p_1\times \dots\times p_1 \times p_2\times \dots \times p_k\times \dots \times p_k$$with $p_i$ crossed $\alpha _i$ times. Then we see the quantity $1+\sum_{i=1}^k\alpha_i(p_i-1)$ is just $1+\sum (a_i-1)$ in the context of the lemma. The slices then should somehow represent the arithmetic progressions.

Therefore, we have proven the problem assuming the lemma is true. Now we return to proving the main lemma. For contradiction suppose $s\le \sum_{i=1}^k(a_i-1)$; then it suffices to find a point in $A$ not covered by any slice. A natural idea is to expand the slices so that for each axis $A_i$, there are at most $a_i-1$ slices that cut $A_i$; then it would follow that there's at least one point not covered by any slice. This clearly points to applying Hall's theorem: let $X=\{P_1,P_2,\dots,P_s\}$ be the set of slices, and let $Y=\{A_1,\dots,A_1,A_2,\dots,A_k,\dots,A_k\}$ be a multiset of axes, where each axis $A_i$ is included exactly $a_i-1$ times. Then we build a bipartite graph $G$ on $X\cup Y$, where $P_i$ and $A_j$ are connected if and only if $P_i$ cuts $A_j$. Because of condition (2), $N(X)=Y$, where $N(X)$ is the set of neighbors of $X$. Also $|X|\le |Y|$ by assumption.

Now, we can apply Hall's theorem to $\overline{G}$: there exists a $\overline{X}$-saturating matching. Without loss of generality, suppose $\overline{Y} = \{A_1,\dots,A_1, A_2,\dots,A_l,\dots,A_l\}$ for some $1\le l\le k$. Then we extend the slices in $\overline{X}$, such that the only axis each slice in $\overline{X}$ is perpendicular to is the axis it matches with. We have now picked the first $l$ coordinates for the desired point not covered by slices. Because $X'\neq X$ and none of the slices are redundant, there exists a point $Z$ not covered by slices in $X'$. We take the last $(k-l)$ coordinates of that point, and merge it with the first $l$ coordinates chosen before. Let this point formed be $\heartsuit$, and we claim that this is the desired point. Indeed, $\heartsuit$ can't be in any of the slices in $\overline{X}$; if $\heartsuit$ is in some slice in $X'$, then recall that the last $(k-l)$ coordinates of $\heartsuit$ are the same as in $Z$, so the slice $S_i\in X'$ covering $\heartsuit$ must cut at least one of the first $l$ coordinate axes, which clearly can't happen. The proof is complete.