Home > Algebra, Combinatorics, Probability, Problem Solving > Arithmetic progressions which cover the positive integers

## Arithmetic progressions which cover the positive integers

Suppose we have a family (finite or infinite) of arithmetic progressions of ratios $r_i, i \geq 1$, and suppose that their union is $\Bbb{N}=\{0,1,2,...\}$. Prove that $\sum_{ n \geq 1}\displaystyle \frac{1}{r_i} \geq 1$.

Proof: The coolest proof of this fact uses a unusual argument. First note that the probability that a positive integer belongs to the $i$-th progression  is $1/r_i$. Heuristically, this is obvious. If we want to be rigorous we can prove that $\displaystyle \lim_{ k \to \infty} \frac{ \# \{ n \leq k\text{ is in the }i\text{-th progression}\}}{k}=\frac{1}{r_i}$. Now, the probability that a positive integer is a positive integer is equal to $1$. Denote by $A_n$ the event that a number is in the $n$-th progression. Then we have that $1=P(\displaystyle\bigcup_{n \geq 1} A_n)\leq \sum_{n \geq 1}P(A_n)=\sum_{n \geq 1}\frac{1}{r_i}$ which is exactly what we wanted to prove.

( I’ve heard about this solution from Mihai Chis.)

Advertisements
1. May 25, 2011 at 8:55 am

absolutely beautiful..but need a higher concept

1. No trackbacks yet.