>アホになった回数Aを求める数式を一般化して示すことはできますか
できます。
3の倍数、3の付く数、重複するものを弾く
この3つを考えればOKです。
(10^n)-(((9^n)*2/3)+1)
アホにならない回数は位に3を用いない数の個数(9^n)の2/3に最後の10^n分の1回を加えた回数になります。
よってそれを数の個数10^nから引いて求めます。
もしマジメに10^nを数える代わりに0をアホになりながら数えるならば、式から+1が削除できます。
この式全体を(10^n)で割ってn→∞にすると0に収束します。つまり大きな数になると、実はほとんどアホになりっぱなしになってしまう、ということがわかります。
ダミーURL
可能だと言えば可能でしょうね。
漸化式を表現するのは可能ですから。
f(n)=10^n以下の正整数の内3を含む数字の個数
g(N,M)=10^n以下の正整数の内3を含まず3で割った余りがmの数字の個数
とすれば
アホになる数(n+1)=10^n+9f(n)+3(g(n,0)+g(n,1)+g(n,2))
となりますから。
A 3の倍数でも3が付く数でもない
B 3の倍数だが3は付かない
C 3が付く
0~10^n (n>=1) で、A の個数を A_n、B,C についてもそれぞれ B_n, C_n とする。
ここで、A_n+1, B_n+1, C_n+1 を、A_n, B_n, C_n で表現したい(漸化式を作りたいということ)。
n→n+1 で、左側に1つ数を追加するイメージで捉えてみる。
C については桁数が増えてもCに属する。A、B に属する数は左に3が付いたときにCに属するようになる。
C_n+1 = 10×C_n + A_n + B_n
B について。0,6,9 がついたらまたBに属する。1,2,4,5,7,8 がついたらAに属する。(3 がついたらCに属するのは上で書いた)
A_n+1 = ? + 6×B_n
B_n+1 = ? + 3×B_n
Aについて。0,6,9 がついたらまたAに属する。
残りの6個の数字は、3で割った余りが1と2の場合で場合分けになる。
余りが1の場合、2,5,8 が来るとBに属するようになる。1,4,7ならAのまま。
余りが2の場合、1,4,7 が来るとBに属するようになる。2,5,8ならAのまま。
場合分けはしたものの対称的に半分の確率でAになったりBになったりする。
結果として、9通りの数字について、3通りでBに属するようになり、6通りでまたAに属する。
A_n+1 = 6×A_n + 6×B_n
B_n+1 = 3×A_n + 3×B_n
A_n+1 = 6×A_n + 6×B_n
B_n+1 = 3×A_n + 3×B_n
C_n+1 = 10×C_n + A_n + B_n
となるので、A_n+1 + B_n+1 + C_n+1 = 10 × (A_n + B_n + C_n) は大丈夫そう。
ここで、、
A_n+1 = 6×(A_n + B_n) ..(*1)
B_n+1 = 3×(A_n + B_n) ..(*2)
の2式を足すと
(A_n+1 + B_n+1) = 9×(A_n + B_n)
初項は、
A_1 = 6
B_1 = 3
C_1 = 1
で、A_1 + B_1 = 9 なので、単純に、
A_n + B_n = 9^n
になる
(*1)(*2)の関係と初項から、A_n = 2×B_n が保たれることがわかる
A_n : B_n = 2 : 1 なので、A_n = 2/3×(A_n + B_n) = 2/3×9^n
求めたいのは1から10^nの範囲で「Aに属していない数の個数」なので、0を取り除くことを考慮して、
n = 2 の場合、
3,6,9,12,13,15,18,21,23,24,27,30,31,32,33,34,35,36,37,38,39,42,43,45,48,51,53,54,57,60,63,66,69,72,73,75,78,81,83,86,89,92,93,96,99
となり、数えてみると45。
10^2-1-2/3×9^2=100-1-81×2/3=99-54=45
n=3 の検算は誰か……
答えが分かったら、見通しがすっきりしました。
0~10^n - 1 までの数を調べることになりますが、まず、3が含まれている数を省いて考えることができます。
調べるのは、{0,1,2,4,5,6,7,8,9}の9つの数字をn個並べたものです。
9^n個ありますが、問題はこの中に3の倍数がいくつ含まれているか? ということです。
(これは前の回答により、1/3 であることが分かっています)
「3の倍数は、全部の桁を足した数も3の倍数になる」という性質があります。
数字を並び替えましょう。
{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。
{0,1,2,4,5,6,7,8,9}の9つの数字をn個並べたパターンは 9^n 個あって、その中で3の倍数は1/3を占めています。
10^n - 9^n が、3が含まれる数。
9^n × 1/3 が、それ以外に残っている3の倍数。
したがって、
(10^n - 9^n) + (9^n × 1/3) = 10^n - 9^n + 1/3 × 9^n = 10^n - (1 - 1/3) × 9^n = 10^n - 2/3 × 9^n
が答え。(0 を省くためにはさらに -1)
n=7まで計算してみました。といってもプログラムでですが。
n | 実際の値 | |
---|---|---|
1 | 3 | 3 |
2 | 45 | 45 |
3 | 513 | 513 |
4 | 5625 | 5625 |
5 | 60633 | 60633 |
6 | 645705 | 645705 |
7 | 6811353 | 6811353 |
実際の値は以下のコードを用いて導きました(pythonです
n=2 #n。値を入力
i=1
z=0
m=0
a_m=0
p=0
while i <= 10**n:
\t while m <= n:
\t\t a_m=i/10**m-i/10**(m+1)*10
\t\t if i%3 ==0 or a_m==3:
\t\t\t p=1
\t\t m=m+1
\t if p==1:
\t\t z=z+1
\t p=0
\t m=0
¥t i=i+1
print "when you count 1 to",10**n,", aho=" ,z,"."
URLはミラーです
コメント(1件)