Pigeonhole question - divisibility by chosen number

183 Views Asked by At

This question should be solved with pigeonhole principle.

Let $a,n \in \mathbb N$ such that $a$ is a number whose digits are only $3$'s and $0$'s, and $n$ is an unspecified natural number.

Show that there is some number $a$ such that $a$ is divisible by $n$.

1

There are 1 best solutions below

3
On BEST ANSWER

Hint: the pigeonholes are the $n$ possible remainders upon division by $n$. Now you just need to choose appropriate pigeons, and demonstrate that a collision will get you the desired property.