Proof of Bound: For each $i\ge 1$, let the first term of $S_i$ be $a_i$, and let $x_i = d_1\cdots d_n/d_i$. Suppose $x_i\in S_i$ and $x_j\in S_j$ for some fixed $i,j$. Since the arithmetic progressions partition $\mathbb{Z}_{>0}$, by density we have $\tfrac{1}{d_1}+\cdots+\tfrac{1}{d_n}=1$. Multiplying through, \[ x_1+\cdots+x_n = d_1\cdots d_n. \]Notice that $x_{i'}\equiv 0 \pmod{d_i}$ for each $i'\not = i$. So taking the above equation $\pmod{d_i}$ gives $x_i\equiv 0 \pmod{d_i}$. But since $x_i\in S_i$, combining with the above, we get $x_i\equiv a_i\equiv 0 \pmod{d_i}$. Therefore, $a_i=\ell_1d_i$ and similarly $a_j=\ell_2d_j$ for some $\ell_1,\ell_2 \in \mathbb{Z}$. Then \begin{align*} S_i &= (\ell_1 d_i, (\ell_1+1)d_i,\ldots) \\ S_j &= (\ell_2 d_j, (\ell_2+1)d_j,\ldots). \end{align*}Then, $N:=100\cdot \ell_1\ell_2 \cdot d_id_j$ is in both $S_i$ and $S_j$, contradiction. Construction: Consider the arithmetic progress $S_i$ in which $d_1\cdots d_n$ lies. We claim $d_1\cdots d_n/d_i \in S_i$. If for the sake of contradiction $d_1\cdots d_n/d_i \in S_j$ with $j\not = i$, then since this number is a multiple of $d_j$, in fact $S_j$ is simply the set of multiples of $d_j$ at least some fixed value. So in particular $d_1\cdots d_n \in S_j$, contradicting the partition.

. So the given condition is actually kind of a red-herring - the product isn't really that important.

The key observation is that $d_i\mid \prod\limits_{j\ne i}d_j$. To prove this, it suffices to show if $\nu_p(d_i)=k$ there exist another $j$ such that $p^k\mid d_j$; combining this result for all prime factors of $d_i$ gives the desired result. Note $\sum \frac{1}{d_i}=1$ because $S_i$ covers $\frac{1}{d_i}$ of the integers and $\cup_{i=1}^n S_i=\mathbb{N}$. A simple $\nu_p$ analysis gives the desired result. Now note $lcm(d_1,\cdots,d_n)$ is in one of the sequences. Since $lcm(d_1,\cdots,d_n)-\prod\limits_{j\ne i}d_j$ is divisible by $d_i$ for all $1\le i\le n$, only whichever sequence contains $lcm(d_1,\cdots,d_n)$ also contains $\prod\limits_{j\ne i}d_j$ so we win.

Here is a lengthier yet very low-tech second solution I found - my first solution is essentially #3 - posting for storage and also because it's a new solution.

Using the previous two claims that we have shown the uniqueness and existence of an index $1 \leq i \leq n$ satisfying the condition. $\blacksquare$

Here's what I did in the contest:

Esy One !! P-4 Let $a_i$ be the first term of the Arithmetic Progression $S_i$ , with common difference $d_i$. We start with an obvious claim - Claim: Any index $i$ satisfy $\frac{\prod_{j=1}^n {d_j}}{d_i}$ $\in$ $S_i$ if and only if $d_i | a_i$. Proof : Note that for $\frac{\prod_{j=1}^n {d_j}}{d_i}$ $\in$ $S_i$ we want an integer $k$ such that $\frac{\prod_{j=1}^n {d_j}}{d_i}$ = $a_i + kd_i$ or equivalently we want $ k$ = $\frac{\prod_{j=1}^n {d_j}}{d_i}$ $-$ $\frac{a_i}{d_i}$ , such an $k$ exist if and only if $d_i | a_i$. $\blacksquare$ Now we will prove that atmost one $ 1\le i \le n$ can exist for which $\frac{\prod_{j=1}^n {d_j}}{d_i}$ $\in$ $S_i$ , suppose assume the contrary that there exist 2 such indices $ i , j $ such that $\frac{\prod_{k=1}^n {d_k}}{d_i}$ $\in$ $S_i$ and $\frac{\prod_{k=1}^n {d_k}}{d_j}$ $\in$ $S_j$ . Note that $d_i \neq d_j$ , and let $\frac{\prod_{k=1}^n {d_k}}{d_i}$ = $ a_i + k_i d_i$ and $\frac{\prod_{k=1}^n {d_k}}{d_j}$ = $a_j + k_j d_j$ , Also by our previous claim we should have $d_i | a_i$ and $d_j | a_j$ , so let $a_i = x d_i$ and $a_j = y d_j$ for some naturals $x$ and $y$. Now , by dirichlet theorem there exist infinitely man prime $ a_i ( mod $ $d_i)$, and that primes will be in set $S_i$ , because in the union of all $S_i ' s$ , every natural number should cover, so take a prime $p \in S_i$ , then there exist a $z$ such that $a_i + z d_i = p$ , so $p = d_i ( x + z)$ , now note that here if $d_i = 1$ then all other $S_j 's$ must be finite , which is a contradiction , so $d_i \neq1$ this means that $x + z = 1$ but as both $x $ is a natural this means that $x = 1$ and $z= 0$ but this will gives that $a_i = p$ and $d_i = p$. So we got set $S_i = (p, 2p ,3p ,....)$ , and similarly we got $S_j = (q , 2q ,3q,.....)$ for some another prime $q$ , but now note that $\frac{\prod_{j=1}^n {d_j}}{d_i}$ = $\frac{\prod_{j=1}^n {d_j}}{p}$ , is $ 0 mod$ $q$ because $d_j = q$ , this means that $\frac{\prod_{j=1}^n {d_j}}{d_i}$ $\in$ $S_j$ , but this also belongs to $S_i$ ; a contradiction as $S_i$ and $S_j$ are disjoint. $\blacksquare$ Now we will prove that there exist atleast one index $ 1\le i \le n$ satisfying that given relation; note that if $i$ satisfy this then $S_i = ( p ,2p ,3p ,...)$ by our previous result. If any of $d_i$ is $0 mod$ $p$ , then we will be done , because this can ensure that $\frac{\prod_{j=1}^n {d_j}}{p}$ $\in$ $S_i$. Suppose assume the contrary that none of $d_i 's$ are $ 0 mod$ $p$ , then note that $a_j + kd_j$ can be $0 mod$ $p$ , by choosing $ k \equiv$ $ -a_j (d_j)^{-1}$ $mod$ $p$. A Contradiction. Hence we are done. $\blacksquare$

As a grader for this problem, I'll note a few things: Some common pitfalls: If $x$ is a term in $S_i$, it does not follow that $x-d_i \in S_i$; this needs to be proven (by density, contradiction, etc). Some approaches manage to avoid this entirely, while others don't. Some people claimed/"proved" that $\gcd(d_1,d_2,\ldots,d_n)>1$; this is actually not true, and a proof may fall apart if it revolves around this claim. A similar claim is that there exists $j$ with $d_i | d_j$ for every $i$; although this is true, it is difficult to prove (see post 3). Also, I apologize for any misgrades - almost every solution claimed that they solved the problem, so it was hard to differentiate between 0+s and 7-s. (also why is everyone using generating functions on this)

reaganchoi wrote: As a grader for this problem, I'll note a few things: Some common pitfalls: If $x$ is a term in $S_i$, it does not follow that $x-d_i \in S_i$; this needs to be proven (by density, contradiction, etc). Some approaches manage to avoid this entirely, while others don't. Some people claimed/"proved" that $\gcd(d_1,d_2,\ldots,d_n)>1$; this is actually not true, and a proof may fall apart if it revolves around this claim. A similar claim is that there exists $j$ with $d_i | d_j$ for every $i$; although this is true, it is difficult to prove (see post 3). Also, I apologize for any misgrades - almost every solution claimed that they solved the problem, so it was hard to differentiate between 0+s and 7-s. (also why is everyone using generating functions on this) But of course it does follow that $x+d_i \in S_i$ right? Because my proof (probably everyone's proof too) heavily relies on that. @above its more like formal series I think

When will the proposers of the problems (and possibly shortlist) be released? Note: and where is SHORTLIST 2020 when we need it

This is what I submitted. First set $S_i := \{a_i + (n)d_i\mid n \in \mathbb{Z}\}$ (We choose $n$ so that quantity is still a natural number.) Then define the product $P_i$ by $$P_i:= \frac{1}{d_i} \prod_{j=1}^n d_j~\text{for}~i\geq 1$$and $P_0:=\prod_{j=1}^n d_j$. Before proving the existence part, we present the following small claim. Claim. For a set $S = \{a+(n)d \mid n \in \mathbb{Z}\}$ such that $d \mid a$ holds, then if $s \in S$ then $ks \in S$ for $k \in \mathbb{N}$. Proof. Since $s \in S$, $s=a+md$ for some $m \in \mathbb{Z}$. Choose $m' := \frac{a(k-1) + kmd}{d}$ (this is an integer, since $d \mid a$). Then we show that $ks = a+m'd$. Indeed, $$a+m'd = a+\frac{a(k-1) + kmd}{d} \cdot d = a + ak - a + kmd = k(a+md) = ks$$which proves our claim. $\square$ We now show the existence part by way of contradiction. Assume for all $i \geq 1, P_i \not\in S_i$. Obviously $d_i \mid P_0$ for all $1 \leq i \leq n$ and that $d_j \mid P_k$ for $j \neq k$ ($k \geq 1)$. Also $P_0 = d_m P_m$ for all $m \geq 1$. Now note that since $P_0 \in \mathbb{N}$, $\exists j$ such that $P_0 \in S_j$. Since $P_0 \in S_j$, $P_0 \equiv a_j \pmod{d_j}$ but $P_0 \equiv 0 \pmod{d_j}$, so $a_j \equiv 0 \pmod{d_j}$ or $d_j \mid a_j$. As $P_1 \in \mathbb{N}$, $P_1$ lies in some set $S_\ell$ ($\ell \neq 1)$. If $\ell \neq j$ then $d_\ell \mid P_1$, but also $P_1 \equiv a_\ell \pmod{d_\ell}$ so $d_\ell \mid a_\ell$. But then from above lemma, since $P_1 \in S_\ell$, $P_0 = d_1P_1 \in S_\ell$. We have $P_0 \in S_j$ and $P_0 \in S_\ell$, which is a contradiction. Therefore, we must have $\ell = j$, and $P_1$ must lie in $S_j$. Similarly $P_2 \in S_j$, $P_3 \in S_j$, and continuing on in this manner, $P_j \in S_j$, contradiction. This proves the existence part. From here, uniqueness part is pretty simple. Let there exists two number $i \neq j$ such that $P_i \in S_i$ and $P_j \in S_j$. WLOG, we can assume $i<j$. Also assume $P_0 \in S_k$ for some $k$. Since $P_0 \in S_k$, $d_k \mid a_k$. Also, if $k \neq i$ then $d_k \mid P_i$, so $P_i \equiv 0 \equiv a_k \pmod{d_k}$ which implies that $P_i \in S_k$. Then we have $P_i \in S_k$ and $P_i \in S_i$ for $i \neq k$, contradiction. Therefore, we must have $i=k$. Similarly, $j=k$. Then we have $i=j$, contradiction. This finishes the uniqueness part.

$\textbf{Lemma1:}$ There exist $(x,y)$ such that $ax+by=c$ if and only if $gcd(a,b)|c$. Proof: If there exist right hand side is divisible by $gcd(a,b)$ so $gcd(a,b)|c$. If $gcd(a,b)|c$, we know that there exists $(x_0,y_0)$ such that $ax_0+by_0=gcd(a,b)$ from Bezout's Theorem. Multiplying both sides by $\frac{c}{gcd(a,b)}$ shows that $(x_0\frac{c}{gcd(a,b)},y_0\frac{c}{gcd(a,b)})$ is a solution of $ax+by=c$. $\blacksquare$ Let $a_i$ be the least element of $S_i$. Elements of $S_i$ are in the form of $d_ik+a_i$ where $k$ is a non-negative integer. $\textbf{Lemma2:}$ $gcd(d_i,d_j)$ is not a divisor of $gcd(a_i,a_j)$. Proof: Assume that $gcd(d_i,d_j)$ is a divisor of $d=gcd(a_i,a_j)$. Then there exists integer $(x,y)$ such that $d_ix+d_jy=a_j-a_i$. Moreover we can find $(x,y)$ such that $x \ge0$ and $y\le 0$ because if $(x_0,y_0)$ is a solution then $(x_0+td_j,y_0-td_i)$ is a solution where $t$ is an integer and we can take $t$ big enough. Thus we have $d_ix+a_i=d_j(-y)+a_j$ which contradicts with the fact that $S_i$ and $S_i$ are disjoint.$\blacksquare$ $i)$Note that $\textbf{Lemma2}$ shows that $gcd(d_i,d_j)>1$ so we can take any equation $\text{mod } gcd(d_m,d_k)$ . To prove that there exists at most one index, assume that there exist two such index. Then we have two indices $m$ and $k$ such that $$\frac{1}{d_m}\prod_{i=1}^{n} d_i \equiv a_m (\text{mod } d_m)$$$$\frac{1}{d_k}\prod_{i=1}^{n} d_i \equiv a_k (\text{mod } d_k)$$ If we take both equation $\text{mod } gcd(d_m,d_k)$ we have $gcd(d_m,d_k)|a_m,a_k$ which implies $gcd(d_m,d_k)|gcd(a_m,a_k)$ contradicts with $\textbf{Lemma2}$. $ii)$To prove that there exists at least one such index, assume that there is no such index. We know that $\frac{1}{d_1}\prod_{i=1}^{n} d_i $ is in $S_l$ for some $l$. If $l=1$, we are done. If not then $\frac{1}{d_1}\prod_{i=1}^{n} d_i \equiv a_l (\text{ mod }d_l)$ which implies $a_l\equiv 0 (\text{ mod }d_l)$. We have $\frac{1}{d_l}\prod_{i=1}^{n} d_i \equiv a_t (\text{ mod }d_t)$ for some $t$. If $t \neq l$, this implies $a_t\equiv 0 (\text{ mod }d_t)$. We have $a_l=d_lu$ and $a_t=d_tv$. Thus $d_l(u+e) \in S_l$ and $d_t(v+f) \in S_t$ where $e$ and $f$ are any non-negative integers. By taking $e=d_tz-u$ and $f=d_lz-v$ for $z$ big enough, we see that this contradicts with the fact that $S_l$ and $S_t$ are disjoint. Therefore we have $\frac{1}{d_l}\prod_{i=1}^{n} d_i \equiv a_l (\text{ mod }d_l)$. $i)$ and $ii)$ together imply there exist exactly one such index. $\square$

Observe that we must have $\frac{1}{d_1}+\frac{1}{d_2}+\cdots +\frac{1}{d_n}=1$ by say density. Now, we have that $d_i|\frac{d_1d_2\cdots d_n}{d_i}$. Now, $\frac{d_1d_2\cdots d_n}{d_i}\in S_i\implies d_1d_2\cdots d_n\in S_i$ which happens for at most one sequence so we have proved the upper bound. Now, let $d_1d_2\cdots d_n\in S_i$ for some $i$ and $\frac{d_1d_2\cdots d_n}{d_i}\in S_j$. Such $i,j$ exist as every positive term is in some $S_i$. Then, we have $d_1d_2\cdots d_n+ \frac{d_1d_2\cdots d_n}{d_i}\in S_i, S_j$ but then $i=j$ and we are done!

Evidently every sequence is a complete residue class. Exactly one sequence contains \[\sum_i\prod_{j\ne i}d_j,\]and that is the sequence that works.

(Throughout the solution, we take $n>1$, as the $n=1$ case is self-evident) Note first that $\text{gcd}(d_i,d_j) \nmid a_i - a_j$, where $a_i+kd_i$ represents set $S_i$—on the contrary, if this was possible, it'd be easy to force a positive integral solution $(k_i,k_j)$ to $a_i+k_id_i=a_j+k_jd_j$, hence contradicting the disjoint-ness of the partition. Now, say that there was more than one index for which the statement holds—without loss of generality, let $a_1+k_1d_1=d_2d_3...d_n$ and $a_2+k_2d_2=d_1d_3d_4...d_n$ $\implies \text{gcd}(d_1,d_2) \mid d_3d_4...d_n(d_2 -d_1) + a_2-a_1 \implies \text{gcd}(d_1,d_2) \mid a_2-a_1 \implies$ Contradiction. Again, let's assume that there was no index for which this held true. Without loss of generality, let $\frac{d_1d_2d_3...d_n}{d_2} \in S_1$. This forces $d_1 \mid a_1$, which in turn gives $a_1=d_1$ (otherwise, if $d_1 \in S_i$, then $(1+rd_i)d_1 \in S_i$ for arbitrarily large $r$, a clear contradiction to disjoint-ness as this $a_1+kd_1=d_1(k+ \alpha )$ belongs to $S_1$). This also forces $\frac{d_1d_2...d_n}{d_i} \in S_1$ for all $i \neq 1$. Going with the assumption, we must take $d_2d_3...d_n \in S_j$ for some $j \neq 1$—but this again leads to the same argument for $S_j$ as for $S_1$ (aka $d_j \mid a_j \implies a_j=d_j$), thus contradicting disjoint-ness, as $d_1d_j$ would belong to both sets $S_1$ and $S_j$. Hence proved.

2021 ELMO/4 wrote: The set of positive integers is partitioned into $n$ disjoint infinite arithmetic progressions $S_1, S_2, \ldots, S_n$ with common differences $d_1, d_2, \ldots, d_n$, respectively. Prove that there exists exactly one index $1\leq i \leq n$ such that\[ \frac{1}{d_i}\prod_{j=i}^n d_j \in S_i.\] I totally forgot about ELMO Claim 01. $d_i^2 \mid \prod_{j = 1}^n d_j$ for all $1 \le j \le n$. Proof. By density argument, we have \[ \frac{1}{d_1} + \frac{1}{d_2} + \dots + \frac{1}{d_n} = 1. \]This gives us \[ \prod_{j = 1}^n d_j = \sum_{1 \le k \le n} \prod_{\ell \not= k} d_{\ell} = d_{i} \cdot \left( \sum_{1 \le k \le n, k \not= i} \prod_{\ell \not= k, i} d_{\ell} \right) + \prod_{\ell \not= i} d_{\ell} \]which is enough to give us $d_i^2 \mid \prod_{j = 1}^n d_j$ for all $1 \le j \le n$. Let us define $S_i \equiv a_i \pmod{d_i}$, that is, all the members of $S_i$ are $a_i \pmod{d_i}$ (but not the other way). WLOG $0 < a_i \le d_i$ for $1 \le i \le n$. Claim 02. $a_i \in S_i$ for all $i$, forcing $S_i$ to be a complete residue class for each $i$. Proof. Suppose $a_i \in S_j$ for some $i \not= j$. We conclude that $S_j \equiv a_i \pmod{d_j}$, and therefore by taking large $k$, we know that $a_i + kd_i d_j$ lies on both sequence $S_i$ and $S_j$, which is a contradiction. Proof of Existence. Since $S_i$'s are the partition of $\mathbb{N}$, take the unique index $\ell$ such that \[ \prod_{j = 1}^n d_j \in S_{\ell} \]This forces $S_{\ell} \equiv 0 \pmod{d_{\ell}}$. However, from our first claim, we know that $\frac{1}{d_{\ell}} \prod_{j = 1}^n d_j \equiv 0 \pmod{d_{\ell}}$, which means that $\frac{1}{d_{\ell}} \prod_{j = 1}^n d_j \in S_{\ell}$ by the second claim, as desired. Proof of Uniqueness. By the first claim, this means that there exists two index $i$ and $j$ such that $S_i \equiv 0 \pmod{d_i}$ and $S_j \equiv 0 \pmod{d_j}$. However, we know that $\text{lcm}(d_i, d_j)$ lies on both sequence, which is a contradiction.

fakesolve, ignore

Write $L_i=\frac{1}{d_i}\prod_{j=1}^n d_j$ Claim1: $d_i|L_j\quad\forall i,j\in\{1,2,\dots,n\}$ Proof. If $i\ne j$ then obviously $d_i|L_j$. Now,By density argument $\sum_{i=1}^{n}\frac{1}{d_i}=1$.So we have $$L_1+L_2+\dots L_n=d_1d_3...d_n$$Since for all $j\ne i, d_i|L_j$ so $d_i|L_i$ as well. $\blacksquare$ Suppose $a_i$ be the first term of $S_i$ Claim2: Suppose $x\in S_i$ and $d_i|x$.Then $d_i|a_i$. Proof. As $x\in S_i$ so $x=a_i+n_xd_i$ for some integer $n_x$.As $d_i|x$ so $d_i|x-d_in_x=a_i$. $\blacksquare$ Claim3: For $i\ne j,\quad d_i|a_i\ \ d_j|a_j$ can't occur simultaneously. Proof.Suppose $d_i|a_i$.It means that all the multiples of $d_i$ which are greater than $a_i$ are in $S_i$.Now Suppose $d_i|a_i$ and $d_j|a_j$.So,for example $(a_i+a_j+2021)d_id_j$ belongs to both $S_i$ and $S_j$.This Contradicts $S_i\cap S_j=\phi$. $\blacksquare$ Claim4: For $i\ne j$ and $m\ne n$ it can't occur that $L_i\in S_m$ and $L_j\in S_n$. Proof. Suppose $L_i\in S_m$.By Claim1, $d_m|L_i$.As $L_i\in S_m$ and $d_m| L_i$ so by Claim2 $d_m|a_m$. Again suppose $L_j\in S_n$.Similarly we have $d_n|a_n$.But this contradicts Claim3. $\blacksquare$ Hence for all $i=1,2,\dots,n$, $L_i$ must belongs to a single set say $S_r$.So, $L_1,L_2,\dots L_n\in S_r$.In particular, $L_r\in S_r$ and this $r$ is unique.$\square$

Hold on, this problem thread says \[ \frac{1}{d_i}\prod_{j=i}^n d_j \in S_i.\]But the PDF I downloaded said \[ \frac{1}{d_i}\prod_{j=1}^n d_j \in S_i,\]and most of the solutions seem to indicate the second is correct. Which one is it? Thank you reagan for giving me a heart attack.

Here's my proof that all terms of the form $\frac{1}{d_i} \prod_{j=i}^n d_j$ are in the same sequence.

Anyways here is a sketch of my solution (well, it's basically a full solution), which I hope cleverly sidesteps issues with $x \in S_i \implies x-d_i \in S_i$. This doesn't seem to use a lot of the claims present in other solutions, so I'm not 100% sure it works, but I can't find any errors either... The index $i$ is the one such that $\prod_{j=1}^n d_j \in S_i$, which exists and is unique. To show nothing else works, suppose there was $k \neq i$ with $$\frac{1}{d_k}\prod_{j=1}^n d_j \in S_k.$$Then since $d_k \mid \prod_{j=1}^n d_j$, we would have $$\left(1+\frac{1}{d_k}\right) \prod_{j=1}^n d_j \in S_k,$$but at the same time this number is divisible by $d_i$ and is greater than $\prod_{j=1}^n d_j \in S_i$, hence $$\left(1+\frac{1}{d_k}\right) \prod_{j=1}^n d_j \in S_i,$$which is a contradiction. Hence no $k$ exists. To show that $i$ works, contradiction again. Suppose $$\frac{1}{d_i}\prod_{j=1}^n d_j\in S_k,$$where $k \neq i$. Then since $d_k \mid \prod_{j=1}^n d_j$ and $d_k \mid \frac{1}{d_i}\prod_{j=1}^n d_j$, we have $$\frac{1}{d_i}\prod_{j=1}^n d_j+\left(1-\frac{1}{d_i}\right)\prod_{j=1}^n d_j=\prod_{j=1}^n d_j \in S_k,$$which is a clear contradiction. This proof can be quickly adapted to show that all $\frac{1}{d_k}\prod_{j=1}^n d_j$ are in $S_i$

@above read #8. It's not possible to claim without proving that $x \in S_i \implies x-d_i \in S_i$. Also, how is $\gcd(d_1,d_2,\dots,d_n)>1$ not necessarily true? Can someone give me 1. an example

is wrong? @below thanks

asbodke wrote: @above read #8. It's not possible to claim without proving that $x \in S_i \implies x-d_i \in S_i$. Also, how is $\gcd(d_1,d_2,\dots,d_n)>1$ not necessarily true? Can someone give me 1. an example

is wrong? Consider the set $\{6, 10, 15\}$. Every pair of elements has a common factor, but their GCD overall equals $1$. (The issue is that the new term is not necessarily divisible by the LCM of the $k$ elements.)

Note that if $a \in S_i$, then $S_i$ is the set of all naturals that are $a\mod{d_i}$. Claim: There exists exactly one set $S_i$ such that $S_i$ is the set of numbers satisfying $0\mod{d_i}$. Consider $P$, the product of all $d_i$. For all $d_i$, $P\equiv 0\mod d_i$. Thus if we were to have multiple sets $S_i$ that satisfy $0\mod d_i$, then we would have an overlap with $P$, meaning at most one such set exists. But this set also must exist in order to cover $P$. WLOG, let this set be $S_1$. Clearly for all $1<i\leq n$, \[\frac{1}{d_i}\cdot P=d_1\cdot\left(\text{n-2 other d's}\right)\equiv 0 \mod d_1\implies \frac{1}{d_i}\cdot P\in S_1\]so we can't have $\frac{1}{d_i}\cdot P\in S_i$. We now show that $\frac{1}{d_1}\cdot P\in S_1$. Claim: We have that the sum of $\frac{1}{d_i}$ is $1$. Note that each $S_i$ covers exactly $\frac{1}{d_i}$ of the naturals, so summing gives the result. We now have \[\sum_{i=1}^n \frac{1}{d_i}=1\]\[\implies \frac{1}{d_1}\cdot P\cdot \sum_{i=1}^n \frac{1}{d_i}=\frac{1}{d_1}\cdot P\]\[\implies \frac{P}{d_1}\cdot \frac{1}{d_1}+\left(\text{n-1 other integers}\right)=\text{integer}\]So we must have $\frac{1}{d_1}\cdot P\equiv 0\mod d_1$. Thus, $\frac{1}{d_1}\cdot P\in S_1$ and we are done.

asbodke wrote: @above read #8. It's not possible to claim without proving that $x \in S_i \implies x-d_i \in S_i$ The main solution only uses the clearly true $x \in S_i \implies x+d_i\in S_i$ only, so I’m not sure what youre referring to. If it’s the remark I put at the end, I believe you’re right.

Let $k=\operatorname{lcm}(d_1,d_2,\ldots,d_n)$, and denote $\frac{1}{d_i}\displaystyle\prod_{j=1}^{n}d_j$ by $P_i$. Claim $\frac{1}{d_1}+\frac{1}{d_2}+\cdots+\frac{1}{d_n}=1$. Proof: Consider the "density" of each progression. More rigorously, define $f_i(x)$ as a function which is equal to $1$ if and only if $x\in S_i$, and is zero otherwise. Let $L_i(x)=\frac{f_i(1)+f_i(2)+\cdots+f_i(x)}{x}$, and note that $$\lim_{x\to\infty}L_1(x)+L_2(x)+\cdots+L_n(x)=1.$$However, $\lim_{x\to\infty}L_i(x)=\frac{1}{d_i}$. Thus, $\frac{1}{d_1}+\frac{1}{d_2}+\cdots+\frac{1}{d_n}=1$ as desired. Notice that this is equivalent to $\frac{P_1+P_2+\cdots+P_n}{d_1d_2\cdots d_n}=1$. Claim: Let $q^a$ ($q$ is prime) be the highest power of $q$ which is a factor of $k$. Then, $P_1,P_2,\ldots,P_n$ are all divisible by $q^a$. Proof: Let $d_i$ be a common difference such that $q^a\mid d_i$ (there could be more than one but the choice of $d_i$ is arbitrary). If $q^a\mid P_i$, then clearly all of $P_1,P_2,\ldots,P_n$ are divisible by $q^a$ since the highest power of $q$ dividing $P_i$ is the minimum out of all of $P_1,P_2,\ldots,P_n$. Otherwise, for the sake of contradiction assume that $q^a\nmid P_i$. Notice that, since $\frac{P_1+P_2+\cdots+P_n}{d_1d_2\cdots d_n}=1$, $P_1+P_2+\cdots+P_n\equiv 0\pmod{q^a}$, so there exists $P_j$ ($j\neq i$) such that $q^a\nmid P_j$. Let $\nu_q(d_j)=x$, so that $x\le a$. Then, $\nu_q(d_1d_2\cdots d_n)\ge a+x$. As a result, $\nu_q(P_j)=\nu_q(d_1d_2\cdots d_n)-\nu_q(d_j)\ge a$. This means that $q^a$ does divide $P_j$, which contradicts its existence. Thus, our initial assumption was false, and $q^a$ also divides $P_i$. This proves the claim. Applying the previous claim on all primes dividing $k$, it is evident that each of $P_1,P_2,\ldots,P_n$ is divisible by $k$. Since all of the common differences divide $k$, every multiple of $k$ must belong to the same progression $S_b$. Thus, the only $P_i$ such that $P_i\in S_i$ is $P_b$. This finishes the problem.

Observe that for large values of $N$, there are $\varepsilon + N/d_i$ members of $S_i$ in $\{1,2,\dots,N\}$ for $\varepsilon \in [-M,M]$ for some fixed $M$. Hence by taking large enough $N$ we see that \[\sum_i \frac{1}{d_i} = 1,\]and so each $S_i$ is a complete residue class. In particular, this means that $d_i$ is the denominator of \[\sum_{j\ne i} \frac{1}{d_j} = 1-\frac{1}{d_i},\]which in turn divides \[\frac{1}{d_i}\prod_i d_j = \prod_{j\ne i} d_j.\]Then the question is whether $\prod_j d_j$ is included in $S_i$. Exactly one $S_i$ satisfies that property, so done.

Basically the same solution as those above! The main observation is as follows: Claim: $d_i \mid \frac{1}{d_i}\prod_{j=1}^n d_j$ for all $i$. Proof: Assume on the contrary that $v_p(d_i)>v_p(\frac{1}{d_i}\prod_{j=1}^n d_j)$ for some prime $p$. Then, considering the density of the arithmetic progressions yields $$\frac{1}{d_1}+\frac{1}{d_2}+...+\frac{1}{d_n}=1$$which is not possible given that $v_p(d_i)>\max_{1\leq j \leq n, j \neq i} v_p(d_j)$. \(\square\) Now, due to the claim, we have that $$\frac{1}{d_i}\prod_{j=1}^n d_j \in S_i \Leftrightarrow \prod_{j=1}^n d_j \in S_i$$for any $i$. Since there exists exactly one index $i$ such that $\prod_{j=1}^n d_j \in S_i$, we conclude that there must exist exactly one index $i$ such that $\frac{1}{d_i}\prod_{j=1}^n d_j \in S_i$ as well, as desired. \(\blacksquare\) Comment: After reading the problem, it is natural to wonder the reason behind the presence of the term $\frac{1}{d_i}$ in front of $\prod_{j=1}^n d_j$. It is easy to find that the problem also holds without the $\frac{1}{d_i}$ term, and that is because $d_i \mid \prod_{j=1}^n d_j$ for all $i$. This motivates one to come up with the claim, which basically finishes the problem.

Note that the following equality holds, because, density! $$\frac{1}{d_1}+\cdots+\frac{1}{d_n}=1$$So $\sum_{i}\prod_{j\neq i}d_j=d_1\cdots d_n$ and reducing this mod $d_i$ we have that $\prod_{j\neq i}d_j$ is divisible by $d_i$ for each $i$. Consider index $i$ such that $a_i=\prod_{j\neq i}d_j$ is minimal. Let $a_i\in S_m$ and since every term larger than $a_i$ and divisible by $d_i$ is in the sequence but all other $a_j$ are divisible by $d_i$ we have that for those that are not in the same arithmetic progression as $a_i$ are smaller than it, but since $a_i$ is smallest possible, we get a contradiction. So every $a_j$ is in the same progression meaning there exists exactly one fixed point!

Let $a_i$ denote the first element of $S_i$. We claim $a_i\leq \frac{1}{d_i}\prod_{j=1}^n d_j$. For contradiction, assume $a_i> \frac{1}{d_i}\prod_{j=1}^n d_j$. Therefore, if $k\leq \frac{1}{d_i}\prod_{j=1}^n d_j$ then $k\in S_j$ for $j\neq i$. Therefore, for all $m$ such that $m\equiv k\pmod{\frac{1}{d_i}\prod_{j=1}^n d_j}$, $m$ is in $S_j$. Therefore, all positive integers are in some sequence that is not $S_i$. Therefore, $S_i$ is empty, which is a contradiction since the empty set is not an arithmetic progression. We will now show there is one $i$ that satisfies $\frac{1}{d_i}\prod_{j=1}^n d_j \in S_i$. We will first show existence. Consider the number $\sum_{i=1}^n \frac{1}{d_i}\prod_{j=1}^n d_j$. Let $S_k$ be the sequence that this number is in. Then, $$a_k\equiv \sum_{i=1}^n \frac{1}{d_i}\prod_{j=1}^n d_j \equiv \frac{1}{d_k}\prod_{j=1}^n d_j \pmod{d_k}.$$Since we have established that $a_k\leq \frac{1}{d_k}\prod_{j=1}^n d_j \pmod{d_k}$, we know that $\frac{1}{d_k}\prod_{j=1}^n d_j \in S_k$. We will now show uniqueness. There is only one $S_k$ such that $\sum_{i=1}^n \frac{1}{d_i}\prod_{j=1}^n d_j\in S_k$. If $\sum_{i=1}^n \frac{1}{d_i}\prod_{j=1}^n d_j\not\in S_m$, then $$a_m\not\equiv \sum_{i=1}^n \frac{1}{d_i}\prod_{j=1}^n d_j\equiv \frac{1}{d_m}\prod_{j=1}^n d_j,$$so $\frac{1}{d_m}\prod_{j=1}^n d_j\not\in S_m$. Therefore $k$ is the unique value of $i$ that satisfies this condition.

Let $a_i$ be the smallest element in $S_i$. For the sake of contradiction, assume $a_i>d_i$. Then in the interval $[1,d_1d_2\ldots d_n]$ there are at most $$\sum_{i=1}^n \left(\frac{1}{d_i} \prod_{j=1}^n d_j\right)-1$$numbers that are in $\bigcup_{i=1}^n S_i$. But for $C>\max a_i$, there are exactly $\sum_{i=1}^n \left(\frac{1}{d_i} \prod_{j=1}^n d_j\right)$ numbers in $[C+1,C+d_1d_2\ldots d_n]$ that are in $\bigcup_{i=1}^n S_i$, a contradiction because both are meant to be $d_1d_2\ldots d_n$. Then consider the number $\sum_{i=1}^n \left(\frac{1}{d_i} \prod_{j=1}^n d_j\right)$ - let $S_k$ be the unique arithmetic progression that contains it. Then since $$\sum_{i=1}^n \left(\frac{1}{d_i} \prod_{j=1}^n d_j\right)\equiv \frac{1}{d_k} \prod_{j=1}^n d_j\pmod{d_k}$$we know that $S_k$ contains $ \frac{1}{d_k} \prod_{j=1}^n d_j$. Conversely, if some $S_l$ contains $\frac{1}{d_l} \prod_{j=1}^n d_j$ for $l\neq k$ then it also contains $\sum_{l=1}^n \left(\frac{1}{d_i} \prod_{j=1}^n d_j\right)$, a contradiction. Thus, exactly one $S_k$ contains it.

Claim: We have $\sum_{i=1}^n \frac{1}{d_i} = 1$. Proof. We use generating functions. Let $S_i$ have smallest element $a_i$. Then the generating function for the numbers in $\mathbb{Z}_{> 0}$ is \[ \frac{x}{1-x} = \sum_{i=1}^n \frac{x^{a_i}}{1-x^{d_i}}. \]Multiplying both sides by $1-x$ and evaluating at $x=1$ yields the desired result. Multiplying both sides of the claim by $\prod d_i$ and taking mod $d_i$ returns $d_i^2 \mid d_1 \cdot \dots \cdot d_n$ for each $i$. Claim: At most one index satisfies the desired property. Proof. Suppose two indices $i$ and $j$ satisfy the desired property. Then it follows that both $S_i$ and $S_j$ contain numbers all divisible by $d_i$ and $d_j$, respectively, so sufficiently large multiples of $d_id_j$ are in both sets, a contradiction. Claim: At least one index satisfies the desired property. Proof. Let $j$ denote the unique index for which $\prod d_i$ is in $S_j$. Then $S_j$ has all elements divisible by $d_j$. This means that $\tfrac{1}{d_j} \cdot \prod d_i$ is in $S_j$ by the first claim, as desired. We conclude by the prior two claims.

Define an index $i$ such that $\frac{1}{d_i}\prod_{j=1}^n d_j \in S_i$ to be good and define $\frac{1}{d_i}\prod_{j=1}^n d_j$ to be the value of an index $i$ Lemma: $\sum_{i} \tfrac{1}{d_i} = 1$ and therefore $d_i^2 \mid d_1d_2 \cdots d_n$ for all $i$ Proof. Take the closed interval $[M, M+d_1d_2 \cdots d_n]$ and note that $\tfrac{1}{d_i}$ of the numbers in this interval must be in $S_i$, so the first part readily follows. Now multiplying the equation by $d_1d_2 \cdots d_n$ and taking $\pmod{d_i}$ gives the second part. Upper Bound: There exists at most one good index. Proof. FTSOC assume there are at least two good indices, $i$ and $j$. Note that if $\tfrac{1}{d_i} \cdot \prod_{j=1}^n d_j$ is in $S_i$, then since the value of $i$ is divisible by $d_i$ and $S_i$ forms a residue set $\pmod{d_i}$, all elements in $S_i$ are divisible by $d_i$. The same is true for $S_j$ as well, so a sufficiently large multiple of $d_id_j$ must be in both $S_i$ and $S_j$ which is a contradiction. Lower Bound: There exists at least one good index. Proof. Let $d_1d_2 \cdots d_n \in S_j$ for the unique index $j$. Note that implies all elements of $S_j$ must be multiples of $d_j$. Now, assume the value of $j$ is in $S_i$ with $i \neq j$. Since the value of $j$ is a multiple of $d_i$, all elements of $S_i$ are multiples of $d_i$. Taking a sufficiently large multiple of $d_id_j$ gives the desired contradiction then, finishing the problem.

Nice Problem from Rohan G Sir’s Handout reaganchoi wrote: The set of positive integers is partitioned into $n$ disjoint infinite arithmetic progressions $S_1, S_2, \ldots, S_n$ with common differences $d_1, d_2, \ldots, d_n$, respectively. Prove that there exists exactly one index $1\leq i \leq n$ such that\[ \frac{1}{d_i}\prod_{j=1}^n d_j \in S_i.\]