Problem 1729

1. Restate the Problem in Terms of Hyperrectangles:
We are given arithmetic progressions $P_1, P_2, \ldots, P_s$ of integers such that:
- Each integer belongs to at least one progression.
- Each progression contains a number that does not belong to any other progression.

We need to prove that the number of progressions $s$ is at least $1 + \sum_{i=1}^k \alpha_i (p_i - 1)$, where $n = \text{lcm}(r_1, r_2, \ldots, r_s)$ and $n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$.

2. Transform the Problem into a Geometric Setting:
Consider the numbers $0, 1, \ldots, n-1$ as points in a hyperrectangle. Each point can be represented by coordinates in a space defined by the prime factors of $n$. Specifically, for each prime $p_i$, we have $\alpha_i$ intervals $[0, p_i - 1]$.

3. Define the Bijection:
Each number $x$ in the range $0$ to $n-1$ can be uniquely represented by its residues modulo $p_i$ and their powers. This representation forms a bijection between the numbers and the points in the hyperrectangle.

4. Characterize the Progressions:
Each progression $P$ with ratio $r = p_1^{b_1} p_2^{b_2} \cdots p_k^{b_k}$ (where $0 \leq b_i \leq \alpha_i$) can be seen as a subset of the hyperrectangle. The coordinates corresponding to the first $b_i$ intervals for each $p_i$ are fixed, while the remaining $\alpha_i - b_i$ coordinates are free.

5. Induction Hypothesis:
We will use induction on the sum $\sum_{i=1}^k \alpha_i$. For the base case where all $\alpha_i = 0$, the statement is trivially true since $s \geq 1$.

6. Induction Step:
Assume the statement holds for any hyperrectangle with $\sum_{i=1}^k \alpha_i' < \sum_{i=1}^k \alpha_i$. We need to prove it for $\sum_{i=1}^k \alpha_i$.

7. Divide the Hyperrectangle:
Choose an interval corresponding to $p_1$ and divide the hyperrectangle into two smaller hyperrectangles:
- One using intervals $[0, n_1 - 1]$ and the rest unchanged.
- The other using intervals $[0, n_2], \ldots, [0, n_k]$ and a dummy first coordinate.

8. Covering the Sub-Hyperrectangles:
Each progression in the original hyperrectangle can be split into progressions covering the sub-hyperrectangles. Ensure that each sub-hyperrectangle is covered by progressions that satisfy the conditions.

9. Count the Progressions:
Let $x_1$ be the number of progressions in the first sub-hyperrectangle that do not use the interval $[0, n_1 - 1]$, and $x_2$ be those that do. Similarly, let $x_3$ and $x_4$ be the corresponding counts for the second sub-hyperrectangle. The total number of progressions is $x_1 + x_2 + x_3 + x_4 - x_5$, where $x_5$ accounts for double-counted progressions.

10. Apply Induction:
Use the induction hypothesis on the sub-hyperrectangles to show that:
$$x_1 + x_2 \geq 1 + \sum_{i \in S_1} n_i' \quad \text{and} \quad x_3 + x_4 - x_5 \geq 1 + \sum_{i \in S_2 \setminus S_1} n_i'$$
Combining these, we get:
$$x_1 + x_2 + x_3 + x_4 - x_5 \geq 1 + \sum_{i=1}^k n_i$$

11. Conclusion:
Therefore, the number of progressions $s$ is at least $1 + \sum_{i=1}^k \alpha_i (p_i - 1)$.

$\blacksquare$

The final answer is $\boxed{ s \geq 1 + \sum_{i=1}^k \alpha_i (p_i - 1) }$