Exercise 1102Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026
A multiple of $n$ from $0$s and $1$s
#pigeonhole#multiples#digits
Statement
Show that for any positive integer coprime to , there exists a multiple of whose decimal representation uses only the digits and .
Hint
Consider the numbers and their residues mod .
Show solutionHide solution
Solution
Sequence. Consider for .
Pigeonhole. numbers and residues mod : two have the same residue, say with .
Difference. , which is a multiple of and uses only s and s.
Conclusion. A multiple with the required form exists.