0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ How many possible remainders are there? Once you know this, this becomes a standard pigeonhole problem $\endgroup$ – Don Thousand Apr 3 at 19:32
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.