2008-06-05 [長年日記]
■3を法として
「３の倍数と３の付く数字の時だけアホになります」という男がいたとして、１から10^n（10のn乗）まで数字を数えた場合、アホになった回数Aを求める数式を一般化して示すことはできますか。
http://q.hatena.ne.jp/1212415938
http://q.hatena.ne.jp/1212415938#a832150
数字を並び替えましょう。{0,6,9, 1,4,7, 2,5,8}
はい。3で割った時の余りで、3つのグループが作れます。
n=1の時。1つ数字を選んだ時に3の倍数である確率は1/3。そうでない確率は2/3。
n= 2の時。1つ数字を選んだ時に3の倍数である確率は1/3で、そうでない確率は2/3。もう一つ選んだ時。前者からさらに3の倍数になる確率は1/9で、そうでない確率は2/9。後者(1つ数字を選んだ時に3の倍数でないケース)を、{1,4,7}と{2,5,8}に分けます。{1,4,7}からもう一つ数字を選んで3の倍数になる確率は1/3で、そうでない確率は2/3。1桁目が{1,4,7}は1/3なので、結局3の倍数になる確率は1/9で、そうでない確率は2/9。{2,5,8}でも同じ議論。結局3の倍数になる確率は1/9+1/9+1/9=1/3。そうでない確率は、2/9+2/9+2/9= 2/3。
n=3以降も同様の議論になり、nに依らず、3の倍数である確率は1/3で、3の倍数でない確率は2/3。
が冗長。
n-1桁までの数を3で割った余りは0,1,2のいずれか。(n=1 でも 0 とみなすことで有効)
これに{0,6,9, 1,4,7, 2,5,8}を1つ加えてn桁の数にするわけだけど、そのうちのどれか3つを加えれば3の倍数にできる。その他の6つは3の倍数にならない。
なので、3の倍数は全体の1/3だけある、と言える。(n=1でも有効なので帰納法が効く)
以上。