0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ well the statement is wrong if you take base 1000 ;) $\endgroup$ – Dominic Michaelis Apr 6 '13 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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