Problem 113: Non-bouncy Numbers

Mathematical Development

Theorem 1 (Counting increasing numbers). The number of positive increasing integers with at most $n$ digits is

Proof. An increasing number with at most $n$ digits corresponds bijectively to a non-decreasing sequence $(d_1, d_2, \ldots, d_n) \in \{0, 1, \ldots, 9\}^n$, where leading zeros represent shorter numbers. The number of such non-decreasing sequences is the number of multisets of size $n$ drawn from an alphabet of size 10. By the stars-and-bars theorem, this equals

This count includes the all-zeros sequence $(0, 0, \ldots, 0)$, which represents the integer 0, not a positive integer. Subtracting this single case yields $I(n) = \binom{n+9}{9} - 1$. $\blacksquare$

Theorem 2 (Counting decreasing numbers). The number of positive decreasing integers with at most $n$ digits is

Proof. A decreasing number of exactly $k$ digits is a non-increasing sequence $(d_1, \ldots, d_k) \in \{0, \ldots, 9\}^k$ with $d_1 \geq d_2 \geq \cdots \geq d_k$ and $d_1 \geq 1$. By reversal, the count of non-increasing sequences of length $k$ from $\{0, \ldots, 9\}$ equals the count of non-decreasing sequences, which is $\binom{k+9}{9}$. Exactly one of these (the all-zeros sequence) has $d_1 = 0$, so the count with $d_1 \geq 1$ is $\binom{k+9}{9} - 1$.

Summing over all lengths $k = 1, 2, \ldots, n$:

By the hockey-stick (Christmas stocking) identity,

Therefore $D(n) = \binom{n+10}{10} - 1 - n$. $\blacksquare$

Lemma 1 (Overlap: numbers both increasing and decreasing). The number of positive integers with at most $n$ digits that are simultaneously increasing and decreasing is $9n$.

Proof. A number is both increasing and decreasing if and only if all its digits are identical, i.e., it is a repdigit. For each digit length $k \in \{1, 2, \ldots, n\}$, there are exactly 9 positive repdigits: $\underbrace{dd \cdots d}_k$ for $d \in \{1, 2, \ldots, 9\}$. The total is $9n$. $\blacksquare$

Theorem 3 (Non-bouncy count by inclusion-exclusion). The number of non-bouncy positive integers below $10^n$ is

Proof. By inclusion-exclusion, the non-bouncy count equals $I(n) + D(n) - \text{Overlap}(n)$. Substituting:

$\blacksquare$

Corollary 2 (Asymptotic non-bouncy fraction). The fraction of non-bouncy numbers below $10^n$ satisfies

Proof. The leading term of $\binom{n+10}{10}$ is $n^{10}/10!$, which is polynomial in $n$. Since polynomial growth is dominated by exponential growth, the ratio tends to 0. $\blacksquare$

Editorial

We enumerate the admissible parameter range, discard candidates that violate the derived bounds or arithmetic constraints, and update the final set or total whenever a candidate passes the acceptance test.

Pseudocode

    inc = Binomial(n + 9, 9)
    dec = Binomial(n + 10, 10)
    Return inc + dec - 10 * n - 2

    result = 1
    For i from 0 to k - 1:
        result = result * (n - i) / (i + 1)
    Return result

answer = NonBouncyBelow(100)

Complexity Analysis

• Time. $O(1)$ arithmetic operations: computing $\binom{109}{9}$ requires 9 multiplications and 9 divisions, and $\binom{110}{10}$ requires 10 of each. With big-integer arithmetic on numbers of $O(n)$ digits, each operation costs $O(n \log n)$ via FFT-based multiplication, giving $O(n \log n)$ total. For $n = 100$, this is negligible.
• Space. $O(1)$: a constant number of big integers, each with $O(n)$ digits.

Answer

#include <bits/stdc++.h>
using namespace std;
typedef __int128 lll;

long long binom(int n, int k) {
    lll result = 1;
    for (int i = 0; i < k; i++)
        result = result * (n - i) / (i + 1);
    return (long long)result;
}

int main() {
    int n = 100;
    long long inc = binom(n + 9, 9) - 1;
    long long dec = binom(n + 10, 10) - 1 - n;
    long long overlap = 9LL * n;
    cout << inc + dec - overlap << endl;
    return 0;
}

from math import comb


def solve():
    n = 100
    inc = comb(n + 9, 9) - 1
    dec = comb(n + 10, 10) - 1 - n
    overlap = 9 * n
    print(inc + dec - overlap)


solve()