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. zzzaxis
    May 25, 2011 at 8:55 am

    absolutely beautiful..but need a higher concept

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: