Skip to main content
OlympiadHQ

Browse · MathNet

Print

Saudi Arabian IMO Booklet

Saudi Arabia counting and probability

Problem

Prove there exist infinitely many positive integers divisible by and each of them containing the same number of digits .
Solution
Let . We want to construct infinitely many positive integers divisible by such that in their decimal representation, each digit appears the same number of times.

Let be a positive integer. Consider the number whose decimal representation consists of copies of each digit (in any order, but for definiteness, let us take the number formed by writing in order, times, i.e., repeated times, for a total of digits).

Let be the set of all such numbers for (note that may have leading zeros, but we can permute the digits to avoid this, or simply consider all numbers with copies of each digit).

There are such numbers (the multinomial coefficient), so for each , the set of numbers with copies of each digit is finite but very large.

Now, is fixed. For each , consider the set modulo . Since grows rapidly with , and there are only possible residues modulo , by the pigeonhole principle, for sufficiently large , there must exist at least one number in divisible by .

More precisely, for each , there exists at least one number with copies of each digit that is divisible by . Since can be taken arbitrarily large, there are infinitely many such numbers.

Therefore, there exist infinitely many positive integers divisible by and each of them contains the same number of digits .

Techniques

Pigeonhole principleModular Arithmetic