|
uchinyan |
|
はい，こんにちは。今年も宜しくお願い致します。さて，今回の問題は．．．
今日はいろいろあって仕事をお休みしました。そこで時間があったので，いろいろと検討してみました (^^; 少し長くなりますがご勘弁を。 (解法1) 最初に思いついた解法です。 0, 2 は偶数，9 は奇数なので，各位の数字の和が奇数になる場合は，9 が 1 個，3 個，5 個となる場合です。 9 が 1 個の場合：9 の桁を選ぶのに 6C1 = 6 通り，残りの 5 桁は 0 又は 2 なので 2^5 = 32 通り，そこで，6 * 32 = 192 個。 9 が 3 個の場合：9 の桁を選ぶのに 6C3 = 20 通り，残りの 3 桁は 0 又は 2 なので 2^3 = 8 通り，そこで，20 * 8 = 160 個。 9 が 5 個の場合：9 の桁を選ぶのに 6C5 = 6 通り，残りの 1 桁は 0 又は 2 なので 2^1 = 2 通り，そこで，6 * 2 = 12 個。 以上ですべてなので，192 + 160 + 12 = 364 個。 (解法1)の n 桁への拡張 n 桁だったらどうなるのだろう，と，素朴に思いました。 明らかに自然に拡張できて，A = ��[kは1以上n以下の奇数]{nCk * 2^(n-k)} ですね。 さて，この和をどうやって求めるかですが．．． ここで，各位の数字の和が偶数の場合の B = ��[kは0以上n以下の偶数]{nCk * 2^(n-k)} を考えると， A + B = ��[k=0,n]{nCk * 2^(n-k)} = (1 + 2)^n = 3^n B - A = ��[k=0,n]{nCk * (-1)^k * 2^(n-k)} = ((-1) + 2)^n = 1 そこで，A = (3^n - 1)/2，b = (3^n + 1)/2 になります。 確かに，n = 6 で A = (3^6 - 1)/2 = 728/2 = 364 になります。 このきれいな結果は何かあるな，と思ったので，その後，少し検討してみました。 まず，一般化なら漸化式だろう，というのが(解法2)です。 (解法2) n 桁以下の数であって，各位の数字の和が奇数となる数の個数を a(n) 個，偶数となる個数を b(n) 個，とすると， (n+1) 桁以下の場合は，(n+1) 桁目は 0，2 又は 9 なので(n 桁以下の場合も含んでいるのに注意)， a(n+1) = ((n+1) 桁目が 0 又は 2 で n 桁以下の和が奇数) + ((n+1) 桁目が 9 で n 桁以下の和が偶数) = 2 * a(n) + b(n) b(n+1) = ((n+1) 桁目が 9 で n 桁以下の和が奇数) + ((n+1) 桁目が 0 又は 2 で n 桁以下の和が偶数) = a(n) + 2 * b(n) a(1) = 1, b(1) = 2 a(2) = 2 * a(1) + b(1) = 2 * 1 + 2 = 4, b(2) = a(1) + 2 * b(1) = 1 + 2 * 2 = 1 + 4 = 5 a(3) = 2 * a(2) + b(2) = 2 * 4 + 5 = 13, b(3) = a(2) + 2 * b(2) = 4 + 2 * 5 = 4 + 10 = 14 a(4) = 2 * a(3) + b(3) = 2 * 13 + 14 = 40, b(4) = a(3) + 2 * b(3) = 13 + 2 * 14 = 13 + 28 = 41 a(5) = 2 * a(4) + b(4) = 2 * 40 + 41 = 121, b(5) = a(4) + 2 * b(4) = 40 + 2 * 41 = 40 + 82 = 122 a(6) = 2 * a(5) + b(5) = 2 * 121 + 122 = 364, b(6) = a(5) + 2 * b(5) = 121 + 2 * 122 = 121 + 244 = 365 そこで，答えは 364 個，です。 (解法2)の一般解 a(n+1) = 2 * a(n) + b(n) b(n+1) = a(n) + 2 * b(n) a(1) = 1, b(1) = 2 を解きます。 a(n+1) + b(n+1) = 3 * (a(n) + b(n)) = ... = 3^n * (a(1) + b(1)) = 3^n * (1 + 2) = 3^(n+1) a(n+1) - b(n+1) = a(n) - b(n) = ... = a(1) - b(1) = 1 - 2 = -1 a(n+1) = (3^(n+1) - 1)/2, b(n+1) = (3^(n+1) + 1)/2 a(n) = (3^n - 1)/2, b(n) = (3^n + 1)/2 確かに，(解法1)の n 桁の場合と一致します。 (解法3) (解法2)がヒントになっていますが，少し見方を変えて考えてみます。 一般に，n 桁以下ではなく，ちょうど n 桁の場合，n が 2 以上ならば，次のことがいえます。 n 桁目は 2 又は 9 なので， (ちょうど n 桁の各位の数字の和が奇数となる数の個数) = (n 桁目が 2 で (n-1) 桁以下の数字の和が奇数となる数の個数) + (n 桁目が 9 で (n-1) 桁以下の数字の和が偶数となる数の個数) = ((n-1) 桁以下の数字の和が奇数となる数の個数) + ((n-1) 桁以下の数字の和が偶数となる数の個数) = ((n-1) 桁以下の数の個数) = 3^(n-1) (ちょうど n 桁の各位の数字の和が偶数となる数の個数) = (n 桁目が 2 で (n-1) 桁以下の数字の和が偶数となる数の個数) + (n 桁目が 9 で (n-1) 桁以下の数字の和が奇数となる数の個数) = ((n-1) 桁以下の数字の和が偶数となる数の個数) + ((n-1) 桁以下の数字の和が奇数となる数の個数) = ((n-1) 桁以下の数の個数) = 3^(n-1) なので，結局， (ちょうど n 桁の各位の数字の和が奇数となる数の個数) = (ちょうど n 桁の各位の数字の和が偶数となる数の個数) = 3^(n-1) ただしこれは，2 桁以上の場合です。 1 桁，n = 1，の場合は 0 があるので特別で，奇数の場合が 1 個，偶数の場合が 2 個で，偶数の場合が 1 個多くなります。 そこで，n 桁以下は全体で 3^n 個，これから特別な 0 を考慮して， (n 桁以下の各位の数字の和が奇数となる数の個数) = (3^n - 1)/2 (n 桁以下の各位の数字の和が偶数となる数の個数) = (n 桁以下の各位の数字の和が奇数となる数の個数) + 1 = (3^n + 1)/2 今回の問題では，n = 6 として，(3^6 - 1)/2 = 728/2 = 364 個，になります。 なお，多少回りくどいですが， (n 桁以下の各位の数字の和が奇数となる数の個数) = ��[k=1,n](ちょうど k 桁の各位の数字の和が奇数となる数の個数) = ��[k=1,n]{3^(k-1)} = (3^n - 1)/(3 - 1) = (3^n - 1)/2 としてもいいですね。 |
|
ネコの住む家
1月8日（木） 12:07:47
MAIL:uchi@sco.bekkoame.ne.jp 33604 |