Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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.