Maths Olympiad Prep

Library / /7 of 27

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., 0123456789012345678901234567890123456789\ldots repeated nn times, for a total of 10n10n digits).

Let SS be the set of all such numbers MnM_n for n1n \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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.