ナベアツ方程式

ナベアツ方程式（ナベアツほうていしき）は、世界のナベアツが1から10ⁿまで数えたときにアホになる回数を算出する数式である。

概要

世界のナベアツは、数字を1から数えていくとき、3の倍数および3のつく数の時にアホになる。ナベアツ方程式は、アホになる回数を算出するものである。

世界のナベアツが1から10ⁿまで数えたときにアホになる回数は、nが1以上の整数の時、

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

と表される。これがナベアツ方程式である。

なお、この方程式はnが1以上の整数の時にしか使えないため、「1から100まで数えたときにアホになる回数」は計算できるが、「1から40まで数えたときにアホになる回数」は計算できない。

証明

0以上(10ⁿ - 1)以下の整数のうち「3」を含まない整数は、3以外の9種類の文字をn個並べる順列と等しいため、9ⁿ個である。これらを3で割った余りで分類し、以下のように表すことにする。（n=3の場合を例として示す）

余り0	$X_n$ 個	（例: 057, 945）
余り1	$Y_n$ 個	（例: 058, 946）
余り2	$Z_n$ 個	（例: 059, 947）

ここで、 $X_n + Y_n + Z_n = 9^n$ を満たしている必要がある。

このとき、「0以上(10ⁿ - 1)以下の整数」のうち、3の倍数および3のつく数の個数は $10^n - (Y_n + Z_n)$ である。

ただし求めたいナベアツ方程式は「1から10ⁿまで」のため、3の倍数である0を除外して $10^n - (Y_n + Z_n) - 1$ となる。

n=0のとき

0以上0以下の整数（つまり「0」だけ）のうち「3」を含まないもの（やっぱり「0」だけ）を3で割った余りで分類すると、以下の通りになる。

余り0	$X_0 = 1$ 個	（「0」だけ）
余り1	$Y_0 = 0$ 個	（なし）
余り2	$Z_0 = 0$ 個	（なし）

n≧1のとき

さて、0以上(10^(n-1) - 1)以下の整数のうち「3」を含まないものの右端に、「3」を含まない1桁の数字を付け加えて、0以上(10ⁿ - 1)以下の「3」を含まない整数を作る。

この数を3で割った余りは以下のようになる。（n=4の場合を例として示す）

	余り0 （0, 6, 9）	余り1 （1, 4, 7）	余り2 （2, 5, 8）
余り0 （例: 057, 945） $X_{n-1}$ 個	余り0 （例: 0570, 9456） $3X_{n-1}$ 個	余り1 （例: 0571, 9457） $3X_{n-1}$ 個	余り2 （例: 0572, 9458） $3X_{n-1}$ 個
余り1 （例: 058, 946） $Y_{n-1}$ 個	余り1 （例: 0580, 9466） $3Y_{n-1}$ 個	余り2 （例: 0581, 9467） $3Y_{n-1}$ 個	余り0 （例: 0582, 9468） $3Y_{n-1}$ 個
余り2 （例: 059, 947） $Z_{n-1}$ 個	余り2 （例: 0590, 9476） $3Z_{n-1}$ 個	余り0 （例: 0591, 9477） $3Z_{n-1}$ 個	余り1 （例: 0592, 9478） $3Z_{n-1}$ 個

これをまとめると、0以上(10ⁿ - 1)以下の整数のうち「3」を含まないものを3で割った余りで分類した個数は、以下の通りとなる。

余り0	$X_n = 3(X_{n-1} + Y_{n-1} + Z_{n-1})$ 個
余り1	$Y_n = 3(X_{n-1} + Y_{n-1} + Z_{n-1})$ 個
余り2	$Z_n = 3(X_{n-1} + Y_{n-1} + Z_{n-1})$ 個

以上より、 $n \ge 1$ に対して $X_n = Y_n = Z_n$ が示された。さらに $X_0 = 1, Y_0 = Z_0 = 0$ より以下の漸化式が得られる。

${\displaystyle X_n = \begin{cases} 3 & (n = 1) \\ 3^2 X_{n-1} & (n \ge 2) \end{cases} }$

これを解くと、 $X_n = Y_n = Z_n = 3^{2n-1}$ が得られる。これは $X_n + Y_n + Z_n = 3 \cdot 3^{2n-1} = 3^{2n} = 9^n$ を満たしており、3を含まない0以上(10ⁿ - 1)以下の整数全体を取り尽くしていることが確認できる。