Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|cite|improve this question

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

share|cite|improve this answer
well the statement is wrong if you take base 1000 ;) – Dominic Michaelis Apr 6 '13 at 16:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.