Dominating Numbers

A dominating number is a positive integer that has more than half of its digits equal.

For example, $2022$ is a dominating number because three of its four digits are equal to $2$. But $2021$ is not a dominating number.

Let $D(N)$ be how many dominating numbers are less than $10^N$.
For example, $D(4) = 603$ and $D(10) = 21893256$.

Find $D(2022)$. Give your answer modulo $1\,000\,000\,007$.

The problem asks to find the number of dominating numbers less than $10^{2022}$, modulo $1,000,000,007$. Here, a dominating number is a number where more than half of the digits are the same.

First, let’s analyze how many dominating numbers there are with exactly $N$ digits. Let’s denote such number as $M(N)$. Let’s consider the general dominating number $X = d_1 d_2 … d_i … d_N$ where $1 \leq i \leq N$.

The number of these dominating numbers can be counted for each dominant digit. For $1 \leq dominant digit \leq 9$, there will $(\frac{N}{2}+1…N)$ choices for the indexes of the $i$-th digit. But for $dominant digit = 0$ (zero cannot lead the number), there will $(\frac{N}{2}+1…N-1)$ choices for the indexes of the $i$-th digit. Besides, the rest of the non-dominant digits will have $10^{N-i}$ possibilities for $i$-th indexes.

The prefix is a bit different though; we cannot select the leading zero, that means we have 9 possibilities for the $d_1$ position. However, the remaining digits have 10 possibilities so the total number of combinations will be $9*10^{N-1}$.

So summing those counts for the dominant and non-dominant we have:
$$
M(N) = \sum_{i=\frac{N}{2}+1}^{N} [10 \cdot {N \choose i} 10^{N-i}] – \sum_{i=\frac{N}{2}+1}^{N-1} [{N \choose i} 10^{N-i}] – 9*10^{N-1}
$$

The dominating numbers less than $10^{2022}$ include dominating numbers with any number of digits from 1 to 2022. So for the given problem:

$$
D(2022) = \sum_{N=1}^{2022} M(N) \pmod {1\,000\,000\,007}
$$

By calculating the sum as per the modular arithmetic rules, you can get the desired output. This kind of complex computation should be done programmatically in a software that is capable of handling large numbers and modular arithmetic. Also, a process of memoization is suggested to optimize the code.

More Answers: