Maths Olympiad Prep

Library / Saudi Arabian IMO Booklet /6 of 26

Saudi Arabian IMO Booklet

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Saudi Arabia

Prove there exist infinitely many positive integers divisible by 20212021 and each of them containing the same number of digits 0,1,…,90, 1, \ldots, 9.

Solution

Let k=2021k = 2021. We want to construct infinitely many positive integers divisible by kk such that in their decimal representation, each digit 0,1,…,90, 1, \ldots, 9 appears the same number of times.

Let nn be a positive integer. Consider the number NN whose decimal representation consists of nn copies of each digit 0,1,…,90, 1, \ldots, 9 (in any order, but for definiteness, let us take the number MnM_n formed by writing 0,1,2,…,90, 1, 2, \ldots, 9 in order, nn times, i.e., 01234567890123456789…01234567890123456789\ldots repeated nn times, for a total of 10n10n digits).

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

There are (10nn,n,…,n)\binom{10n}{n, n, \ldots, n} such numbers (the multinomial coefficient), so for each nn, the set SnS_n of numbers with nn copies of each digit is finite but very large.

Now, k=2021k = 2021 is fixed. For each nn, consider the set SnS_n modulo kk. Since ∣Sn∣|S_n| grows rapidly with nn, and there are only kk possible residues modulo kk, by the pigeonhole principle, for sufficiently large nn, there must exist at least one number in SnS_n divisible by kk.

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

Therefore, there exist infinitely many positive integers divisible by 20212021 and each of them contains the same number of digits 0,1,…,90, 1, \ldots, 9.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.