Question

State and prove a generalized version of pigeonhole principle and use it to prove the following statement: If 22 numbers are selected at random, at least 4 of them will have the same remainder when divided by 7.

Answer 1

Solution:

THE GENERALIZED PIGEONHOLE PRINCIPLE: If N objects are placed into k boxes, then there is at least one box containing at least ⌈N/k⌉ objects.

Proof:

The proof goes by contradiction: Suppose the claim is false, then each box must have strictly less than ⌈N/k⌉ objects, i.e., at most ⌈N/k⌉−1 objects (the greatest integer strictly less than n is n−1)

Now, then since there are k boxes and each box has objects ≤⌈N/k⌉−1, the total number of objects from all the boxes is ≤k(⌈N/k⌉−1)<k⋅N/k=N (we use ⌈x⌉−1<x) which gives us a contradiction since the total number of objects from all the boxes cannot be strictly less than N(since N is the total number of objects from all the boxes).

Notice the one single < in the chain of inequalities in the penultimate step which makes the overall inequality strict, i.e, gives us N<N.

Now if we select 22 numbers at random then N=4.

If we divide a number by 7 then the possible remainders are : {0,1,2,3,4,5,6}.

So, there are 7 possible remainders. Here, k=7.

We have, N=22 and k=7. Using the Pigeonhole Principle, at least

of them will have the same remainder.