世界のナベアツはそれほどアホにならない

序文

数え続ける世界のナベアツbot が$ 300000 $に達し、ここから$ 100000 $回アホになり続けるフェーズが始まりました。

極限

世界のナベアツが$ 1 $から$ N $まで数える時、その中でアホになった回数の割合の$ N \rightarrow \infty $の極限は$ 1 $であることが知られています。

自然数$ k $に対し、数直線$ [0, 1) $を$ \frac{1}{{10}^k} $ごとに区切り、$ n $番目の区切りを「世界のナベアツが$ n $を数えるときにアホになる」時にだけ赤く塗ることにします。このとき、赤く塗られた点の集合を$ S_k $とし、その極限

$$ S \stackrel{\mathrm{def}}{=} \left\{ x \mid \exists k_0 \in \mathbb{N}, \forall k_1 \in \mathbb{N}, k_1 \geq k_0 \Longrightarrow x \in S_{k_1} \right\} $$

を考えると、この補集合$ [0, 1) \setminus S $の測度は$ 0 $になります。

この意味で、世界のナベアツは「ほとんど至る所アホ」であるといえます。

実際の挙動

「ほとんど至る所アホ」というと、だんだんアホの割合が増えていき、最後はずっとアホになるようなイメージを持ちそうですが、実際はそうではありません。

$ 1 $から$ N $までの自然数からなる数直線のランダムな一点に降り立って周りを見渡すと、以下のどちらかの景色が見えるはずです。

• $ 12{\color{red}3}456789 $のように、長いアホゾーンの途中にいる
• $ 124456789 $のように、およそ$ 3 $回に$ 1 $回の割合でアホになっている

$ N $を増やすと、前者に入る確率が増えることで、「極限が$ 1 $になる」が実現されます。

では、実際にどのように確率が増えていくのか、その様子を見ていきましょう。

解析

$ 1 $桁

十の位以上を固定して、一の位が$ 0 $～$ 9 $の$ 10 $個の連続する$ 0 $または自然数を考えたとき、世界のナベアツがアホになるタイミングは次の$ 4 $パターンがあります。

十の位以上に$ 3 $が含まれる場合はパターン$ \text{1D} $、それ以外の場合は最初の数(一の位が$ 0 $の数)を$ 3 $で割った余りに応じてパターン$ \text{1A}, \text{1B}, \text{1C} $のどれかになります。

ここから、非自明な事実が得られます:

実際の漫才では$ \text{1A}, \text{1B}, \text{1C}, \text{1D} $の順に$ 1 $回ずつ実行され、最後に$ 40 $を言って終了します。

しかしここで止まるわけにはいきません。$ 40 $の先に進みましょう。

$ 2 $桁

百の位以上を固定した$ 100 $個の数について考えます。$ 1 $桁の場合と同様、$ 4 $通りのパターンが存在します。

$ 3 $で割った余りの違いが最後の$ 1 $桁で吸収されるので、全てのマスが薄い赤($ 40\% $アホ)か赤($ 100\% $アホ)になります。

$ 3 $桁

下$ 3 $桁で考えるとこうなります。

上の図と全く同じ構成です。あとは$ 3 $の色が少しずつ混ざって色が濃くなっていくだけです。

オーダーの評価

$ 10 $の冪乗のとき

パターン$ (n+1)\text{A} $の$ 3 $でないマスに現れる色の濃さ(パターン$ n\text{A} $の平均の濃さ)を$ a_n $とします。このとき、$ n \geq 1 $であれば次が成り立ちます:

$$ a_1 = 0.4, a_{n+1} = 0.1 \cdot 9 \cdot a_n + 0.1 $$

これは正確に解くことができます。

導出は読者への演習問題としますが、

$$ a_n = 1 - \frac{2}{3} \cdot {0.9}^n $$

と求められます。これに$ {10}^n $を掛けると

$$ {10}^n a_n = {10}^n - \frac{2}{3} \cdot 9^n = {10}^n - 2 \cdot 3^{2n-1} $$

となります。これは$ 0 $から$ {10}^n - 1 $まで数えたときにアホになる回数です。

$ 0 $が$ 3 $の倍数であり、$ {10}^n $が$ 3 $の倍数でないことに注意すれば、$ 1 $から$ {10}^n $まで数えたとき、

$$ {10}^n - 2 \cdot 3^{2n-1} - 1 $$

回アホになることがわかり、これは文献[1]の結果と一致します。

それ以外のとき

$ 0 $から$ N - 1 $まで数えたときのアホになる数の割合を$ f(N) $とおき、これを上と下から押さえます。

定義

• $ N $の$ 10 $進表記を$ d_n d_{n-1} \cdots d_1 d_0 $とする。
• $ N_1 = {10}^n, N_2 = N - {10}^n $とする。
• $ 0 $から$ N_1 - 1 $まで数えたときのアホになる数の割合を$ p $とする。
• $ N_1 $から$ N $まで数えたときのアホになる数の割合を$ q $とする。

このとき、以下が成り立つ:

上限

$ q < 1, N_2 < 9 \times {10}^n = 9 N_1 $であるから、

$$ f(N) = \frac{N_1 a_n + N_2 q}{N_1 + N_2} < \frac{N_1 a_n + N_2 \cdot 1}{N_1 + N_2} < \frac{N_1 a_n + 9 N_1}{N_1 + 9 N_1} < \frac{a_n + 9}{10} = 1 - \frac{1}{15} \cdot {0.9}^n $$

下限

\begin{align*} Nf(N) &\geq \sum_{k=1}^{n} d_n a_n {10}^n \\ &= \sum_{k=1}^{n} d_n \left(1 - \frac{2}{3} \cdot {0.9}^n\right) {10}^n \\ &= \sum_{k=1}^{n} \left(d_n {10}^n - d_n \cdot \frac{2}{3} \cdot 9^n \right) \\ &\geq (N - 9) - \sum_{k=1}^{n} d_n \cdot \frac{2}{3} \cdot 9^n \\ &\geq (N - 9) - \sum_{k=1}^{n} 6 \cdot 9^n \\ &> (N - 9) - \sum_{k=-\infty}^{n} 6 \cdot 9^n \\ &= (N - 9) - 6 \cdot 9^n \cdot \frac{9}{8} \\ &> N - 6 \cdot 9^n \end{align*}

$$ \therefore f(N) > 1 - \frac{6 \cdot 9^n}{N} \geq 1 - \frac{6 \cdot 9^n}{{10}^n} = 1 - 6 \cdot {0.9}^n $$

評価

$ n \leq \log_{10}(N) < n + 1 $であることから$ f(N) $はある正の実数$ A, B $を用いて

$$ 1 - A \cdot {0.9}^{\log_{10}{N}} < f(N) < 1 - B \cdot {0.9}^{\log_{10}{N}} $$

と書ける。ここで

$$ {0.9}^{\log_{10}{N}} = {0.9}^{\frac{\log_{0.9}{N}}{\log_{0.9}{10}}} = \left({0.9}^{\log_{0.9}{N}}\right)^\frac{1}{\log_{0.9}{10}} = N^\frac{1}{\log_{0.9}{10}} = N^{\log_{10}{0.9}} = N^{-\log_{10}{\frac{10}{9}}} $$

と変形できるので、

$$ 1 - f(N) \in \Theta\left(N^{-\log_{10}{\frac{10}{9}}}\right) = \Theta\left(N^{-0.045757\cdots}\right) = \Theta\left(\frac{1}{\sqrt[21.854\cdots]{N}}\right) $$

が成り立つ。

$ \sqrt{\phantom{N}} $の左上にこんな大きい無理数が乗ってるのは初めて見ました。