# Solve this Pigeonhole Principle with regards to Divisors and Remainders

What is the smallest number n such that if any n natural numbers are chosen at random, at least 4 among them give the same remainder when divided by 7?

• How many possible remainders are there? Once you know this, this becomes a standard pigeonhole problem – Don Thousand Apr 3 at 19:32

Let us consider the worst case : We have $$21$$ numbers , and every residue appears exactly $$3$$ times. This shows that $$21$$ numbers are not enough.

However $$22$$ are sufficient because not every residue can appear less than $$4$$ times because then the sum would be at most $$21$$.

The reverse of:

if there are more than nk items to place in n containers ( equiprobably simply for the reverse to work), there is at least 1 containing k+1 items

is :

if there is a container with at least k+1 items, where items have been distributed equiprobably, Then there are at least nk+1 items

This reverse comes in handy $$4=k+1\implies k=3$$, and therefore with $$n=7$$ there are $$3(7)+1=22$$ items in the least case to guarantee it.