IMO Shortlist 2010 problem C7

  Avg: 0.0
  Avg: 9.0
Dodao/la: arhiva
June 23, 2013
Let P_1, \ldots , P_s be arithmetic progressions of integers, the following conditions being satisfied:

(i) each integer belongs to at least one of them;
(ii) each progression contains a number which does not belong to other progressions.

Denote by n the least common multiple of the ratios of these progressions; let n=p_1^{\alpha_1} \cdots p_k^{\alpha_k} its prime factorization.

Prove that s \geq 1 + \sum^k_{i=1} \alpha_i (p_i - 1).

Proposed by Dierk Schleicher, Germany
Source: Međunarodna matematička olimpijada, shortlist 2010