Project Euler/112

Problem Statement

Analysis

This problem asks for the least positive integer $ N $ such that the proportion of "bouncy" numbers up to $ N $ is exactly 99%.

A number is bouncy if it is neither increasing (digits non-decreasing left-to-right, e.g., 13448) nor decreasing (digits non-increasing left-to-right, e.g., 99740).

Let $ B(N) $ be the count of bouncy numbers $ \le N $, and $ NB(N) $ be the count of non-bouncy numbers $ \le N $.

The condition is $ \frac{B(N)}{N} = 0.99 $.

Since $ B(N) = N - NB(N) $, the condition becomes:

$ \frac{N - NB(N)}{N} = 0.99 \implies 1 - \frac{NB(N)}{N} = 0.99 \implies \frac{NB(N)}{N} = 0.01 $

This means we seek the smallest $ N $ such that $ NB(N) = \frac{N}{100} $.

A key consequence is that $ N $ must be a multiple of 100.

Non-bouncy numbers are either increasing or decreasing.

Let $ I(N) $ be the count of increasing numbers $ \le N $ and $ D(N) $ be the count of decreasing numbers $ \le N $.

Numbers with all identical digits (e.g., 555) are both increasing and decreasing; let their count be $ F(N) $.

By inclusion-exclusion:

$ NB(N) = I(N) + D(N) - F(N) $

While calculating $ I(N), D(N), F(N) $ for arbitrary $ N $ typically requires Digit Dynamic Programming, analytical formulas exist for $ N=10^k-1 $:

$ |I(10^k-1)| = \binom{k+9}{9} - 1 $

$ |D(10^k-1)| = \binom{k+10}{10} - 1 - k $

$ |F(10^k-1)| = 9k $

$ |NB(10^k-1)| = \binom{k+9}{9} + \binom{k+10}{10} - 10k - 2 $

These formulas show that the proportion of non-bouncy numbers drops below 1.3% for $ k=6 $ ($ N=999,999 $) and below 0.4% for $ k=7 $ ($ N=9,999,999 $), indicating $ N $ is likely greater than $ 10^6 $.

The computational strategy is:

1. Implement functions (likely using Digit DP) to compute $ NB(N) $ accurately for any $ N $.

2. Search for the target $ N $ by checking multiples of 100, starting from an estimated lower bound (e.g., $ N \approx 100 \times NB(10^6-1) \approx 1.3 \times 10^6 $).

3. The first $ N $ found such that $ NB(N) = N/100 $ is the solution.

Solution

Link to solution: https://git.charlesreid1.com/cs/euler/src/branch/master/java/Problem112.java