|
uchinyan |
|
#27971の続き
よりナイーブな方法です。 見た目すごい式が並びますが、実は、 9 * 99 = 9 * (100 - 1) 0900 -009 ---- 0891 9 * 99 * 9999 = 891 * (10000 - 1) 08910000 -0000891 -------- 08909109 9 * 99 * 9999 * 99999999 = 8909109 * (100000000 - 1) 0890910900000000 -000000008909109 ---------------- 0890910891090891 などを、一般化しただけです。 #27954の問題の拡張 のよりナイーブな証明 a(n) = 9 * 99 * 9999 * 99999999 * 9999999999999999 * ... * 99…(2^n 個)…99 とします。 99…(2^n 個)…99 = 10^(2^n) - 1 なので、次の漸化式がいえます。 a(n) = a(n-1) * 99…(2^n) 個)…99 = a(n-1) * (10^(2^n) - 1) = a(n-1) * 10^(2^n) - a(n-1) ここで、一般に、n >= 0 で a(n) は 2^(n+1) - 1 桁で、a(n) の下一桁は 0 ではありません。 下一桁に関しては明らか。 桁数に関しては、a(0) = 9 は明らか。 一般の a(n) は、a(n-1) が 2^n - 1 桁とすると、 a(n-1) * 10^(2^n) が (2^n - 1) + 2^n = 2^(n+1) - 1 桁なので、漸化式より明らかです。 さてこのときに、a(n) の各桁を考えてみます。a(n) の i 桁を a(n,i) と書くことにします。 i は、0 から始まるので、0 <= i <= 2^(n+1) - 2 に注意します。 すると、a(n) は、定義より、 a(n) = 10^(2^(n+1) - 2) * a(n,2^(n+1) - 2) + ... + 10^(2^n + 1) * a(n,2^n + 1) + 10^(2^n) * a(n,2^n) + 10^(2^n - 1) * a(n,2^n - 1) + 10^(2^n - 2) * a(n,2^n - 2) + ... + 10^1 * a(n,1) + 10^0 * a(n,0) 一方で漸化式より、 a(n) = 10^(2^(n+1) - 2) * a(n-1,2^n - 2) + ... + 10^(2^n + 1) * a(n,1) + 10^(2^n) * a(n-1,0) - 10^(2^n - 2) * a(n-1,2^n - 2) - ... - 10^1 * a(n-1,1) - 10^0 * a(n-1,0) = 10^(2^(n+1) - 2) * a(n-1,2^n - 2) + ... + 10^(2^n + 1) * a(n,1) + 10^(2^n) * (a(n-1,0) - 1) + 10^(2^n) - 10^(2^n - 2) * a(n-1,2^n - 2) - ... - 10^1 * a(n-1,1) - 10^0 * a(n-1,0) = 10^(2^(n+1) - 2) * a(n-1,2^n - 2) + ... + 10^(2^n + 1) * a(n,1) + 10^(2^n) * (a(n-1,0) - 1) + 10^(2^n - 1) * 9 + 10^(2^n - 1) - 10^(2^n - 2) * a(n-1,2^n - 2) - ... - 10^1 * a(n-1,1) - 10^0 * a(n-1,0) = 10^(2^(n+1) - 2) * a(n-1,2^n - 2) + ... + 10^(2^n + 1) * a(n,1) + 10^(2^n) * (a(n-1,0) - 1) + 10^(2^n - 1) * 9 + 10^(2^n - 2) * (9 - a(n-1,2^n - 2)) + 10^(2^n - 2) - 10^(2^n - 3) * a(n-1,2^n - 3) - ... - 10^1 * a(n-1,1) - 10^0 * a(n-1,0) = 10^(2^(n+1) - 2) * a(n-1,2^n - 2) + ... + 10^(2^n + 1) * a(n,1) + 10^(2^n) * (a(n-1,0) - 1) + 10^(2^n - 1) * 9 + 10^(2^n - 2) * (9 - a(n-1,2^n - 2)) + 10^(2^n - 3) * (9 - a(n-1,2^n - 3)) + ... + 10^1 * (9 - a(n-1,1)) + 10^0 * (10 - a(n-1,0)) ここで、a(n-1,0) が 0 ではないことが効いています。 そこで、 a(n,2^(n+1) - 2) = a(n-1,2^n - 2) a(n,2^(n+1) - 3) = a(n-1,2^n - 3) ... a(n,2^n + 1) = a(n-1,1) a(n.2^n) = a(n-1.0) - 1 a(n,2^n - 1) = 9 a(n,2^n - 2) = 9 - a(n-1,2^n - 2) a(n,2^n - 3) = 9 - a(n-1,2^n - 3) ... a(n.1) = 9 - a(n-1,1) a(n,0) = 10 - a(n-1,0) となるので、各桁の和を s(n) とすると、 s(n) = a(n,2^(n+1) - 2) + a(n,2^(n+1) - 3) + ... + a(n.2^n + 1) + a(n,2^n) + a(n,2^n - 1) + a(n,2^n - 2) + a(n,2^n - 3) + ... + a(n,1) + a(n,0) = a(n-1,2^n - 2) + a(n-1,2^n - 3) + ... + a(n-1,1) + (a(n-1.0) - 1) + 9 + (9 - a(n-1,2^n - 2)) + (9 - a(n-1,2^n - 3)) + ... + (9 - a(n-1,1)) + (10 - a(n-1,0)) = 9 + 9 * (2^n - 1) = 9 * 2^n となります。 |
|
ネコの住む家
7月28日（金） 23:48:08
MAIL:uchi@sco.bekkoame.ne.jp 27972 |