Solve this Pigeonhole Principle with regards to Divisors and Remainders

Question

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?

Answer 1

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$.

Answer 2

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.