Kvant Math Problem 310

An $n$-digit number is a sequence of digits $d_1d_2\ldots d_n$ where $d_1 \in {1,\dots,9}$ and $d_i \in {0,\dots,9}$ for $i \ge 2$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m00s
Source on kvant.digital

Problem

Prove that among $n$-digit numbers there are more than $8^n$ such numbers whose decimal representation contains no block of digits (in particular, no digit) occurring twice in a row.

G. A. Gurevich

Exploration

An $n$-digit number is a sequence of digits $d_1d_2\ldots d_n$ where $d_1 \in {1,\dots,9}$ and $d_i \in {0,\dots,9}$ for $i \ge 2$. The condition forbids any adjacent repetition, so $d_i \ne d_{i+1}$ for all $i$.

The structure suggests a step-by-step construction: choose $d_1$, then choose each $d_{i+1}$ from all digits except $d_i$. This yields a product-type count. The main point to confirm is that no hidden dependence reduces the number of choices beyond the immediate predecessor constraint.

The resulting count appears to be $9 \cdot 9^{n-1} = 9^n$, which already exceeds $8^n$ for all $n \ge 1$. The only delicate point is ensuring that this counting is exact and that no leading-zero restriction alters the uniform $9$ choices per step.

Problem Understanding

This is a Type B problem: prove that the number of $n$-digit numbers whose decimal representation has no two consecutive equal digits is greater than $8^n$.

The core difficulty is to correctly enumerate all admissible digit sequences under the adjacency constraint and compare the resulting count with $8^n$.

The natural expectation is that each position after the first has exactly $9$ independent choices, while the first digit has $9$ choices, giving $9^n$ total valid numbers, which exceeds $8^n$ for all positive integers $n$.

Proof Architecture

The proof proceeds by interpreting valid $n$-digit numbers as sequences of digits satisfying a local restriction.

The first lemma states that the number of choices for the first digit is $9$, since it must lie in ${1,\dots,9}$.

The second lemma states that for each $i \ge 2$, once $d_{i-1}$ is fixed, the digit $d_i$ has exactly $9$ admissible choices in ${0,\dots,9}$.

The third lemma states that these choices are independent in the sense that any admissible sequence is produced uniquely by this stepwise construction, yielding a product formula for the total count.

The final step compares $9^n$ and $8^n$.

The most delicate point is justifying that no further global constraints exist beyond adjacency, ensuring the multiplicative structure is valid.

Solution

An $n$-digit number is a sequence $d_1d_2\ldots d_n$ where $d_1 \in {1,2,\dots,9}$ and $d_i \in {0,1,\dots,9}$ for $2 \le i \le n$. The condition of the problem requires that $d_i \ne d_{i+1}$ for every $i \in {1,2,\dots,n-1}$.

The first digit $d_1$ can be chosen in exactly $9$ ways, since it may be any digit from $1$ to $9$.

Assume $d_i$ has been chosen for some $i \in {1,\dots,n-1}$. The digit $d_{i+1}$ may be any digit from ${0,1,\dots,9}$ except $d_i$, so there are exactly $10-1=9$ possible choices for $d_{i+1}$.

Proceeding inductively, every admissible sequence is constructed uniquely by this procedure, since each digit is determined step-by-step without any additional restriction beyond the adjacency condition. Hence the total number of such $n$-digit numbers equals

$$9 \cdot 9^{n-1} = 9^n.$$

For every integer $n \ge 1$, comparison of powers gives $9^n > 8^n$, since $9 > 8$ and exponentiation preserves strict inequality for positive exponents.

Therefore, among all $n$-digit numbers, the number whose decimal representation contains no block of identical consecutive digits is greater than $8^n$.

This completes the proof. ∎

Verification of Key Steps

The crucial point is the claim that at each step there are exactly $9$ valid choices. This depends only on excluding the immediately preceding digit, and no further digit restrictions appear in the statement, so no additional constraints can reduce the available set.

Another delicate point is the product structure. Each admissible sequence corresponds uniquely to a sequence of choices: the first digit is chosen from ${1,\dots,9}$, and each subsequent digit is chosen from the complement of the previous digit. This correspondence is bijective since reconstruction from choices is deterministic.

Finally, the comparison $9^n > 8^n$ follows from monotonicity of exponentiation for bases greater than $1$, applied directly to $9 > 8$.

Alternative Approaches

One alternative is to construct an explicit injection from the set of all binary strings of length $n$ to the set of admissible digit sequences. For example, one may encode $0$ as “keep a fixed allowed digit different from the previous one” and $1$ as “switch to another fixed alternative,” ensuring at least $8^n$ distinct constructions. However, this approach introduces unnecessary encoding choices and does not exploit the exact uniform $9$-branching structure of the digit process, making the direct counting argument both shorter and structurally transparent.