Consider a set A of 100, 000 arbitrary integers. Prove that there is some subset of 22 integers that end in the same last three digits.

Question

Consider a set A of 100, 000 arbitrary integers. Prove that there is some subset of 22 integers that end in the same last three digits.

I'm new to this principle and need help on this problem.

Answer 1

If each of the 1000 combinations of final three digits occured at most 21 times, the total number of integers in $A$ would be at most $21\cdot 1000=21000$. The problem statement seems to be very wasteful as 22 could be replaced with 100.