|
uchinyan |
|
はい，こんにちは。さて，今回の問題は．．．
うーむ，分かってしまえば簡単なのですが，少し考え込んでしまいました (^^; 後で皆さんの解法と比較することもあるので，気付いた三つほどの解法を書いておきます。 (解法1) 直接数える方法です。最初に思い付きました。前々回の子どもがイスに座る問題がヒントになりました。 含まれる 3 の個数に注目します。 ・3 がない場合 1，2 だけで 6 桁の数を作るので，2^6 = 64 通り。 ・3 が 1 つだけある場合 1，2 だけで 5 桁の数を作り，両端も含めた 6 箇所の数字の間の 1 箇所に 3 を挟めばいいので，2^5 * 6C1 = 32 * 6 = 192 通り。 ・3 が 2 つだけある場合 1，2 だけで 4 桁の数を作り，両端も含めた 5 箇所の数字の間の 2 箇所に 3 を挟めばいいので，2^4 * 5C2 = 16 * 10 = 160 通り。 ・3 が 3 つだけある場合 1，2 だけで 3 桁の数を作り，両端も含めた 4 箇所の数字の間の 3 箇所に 3 を挟めばいいので，2^3 * 4C3 = 8 * 4 = 32 通り。 ・3 が 4 つ以上ある場合 4 つの 3 の間に少なくとも 1 つずつ 1 又は 2 を挟まないといけないので，7 桁になってしまい，不可能です。 結局，以上を加えて， 64 + 192 + 160 + 32 = 448 通り (解法2) 漸化式を使う方法です。この方が簡単かな。 そういえば，ちょっと違いますが，一昨年の京大入試で似たような問題があったなぁ，列車の色分け問題，と思い出しました。 n 桁の数の最高位の桁，n 桁目，の数字が 1 の場合を a(n) 通り，2 の場合を b(n) 通り，3 の場合を c(n) 通り，とします。 これに n+1 桁目の数字を追加して，n+1 桁の数を作ります。 n+1 桁の数字が 1 の場合：n 桁の数字は何でもいいので a(n+1) = a(n) + b(n) + c(n) n+1 桁の数字が 2 の場合：n 桁の数字は何でもいいので b(n+1) = a(n) + b(n) + c(n) n+1 桁の数字が 3 の場合：n 桁の数字は 1 又は 2 でないといけないので c(n+1) = a(n) + b(n) ただし，明らかに，a(1) = b(1) = c(1) = 1 です。 さて，求めるものは，a(6) + b(6) + c(6) です。 後は，順次求めていけばいいのですが，次のような表を作るのがいいでしょう。 最高位桁の数字が１：1, 3, 8, 22, 60, 164, ... <----- a(n) 最高位桁の数字が２：1, 3, 8, 22, 60, 164, ... <----- b(n) 最高位桁の数字が３：1, 2, 6, 16, 44, 120, ... <----- c(n) 題意の数の場合の数：3, 8,22, 60,164, 448, ... <----- a(n) + b(n) + c(n) したがって，448 通りになります。 算数としては，漸化式をうまく言葉で説明して，上記の表を作ればいいでしょう。 (解法3) やはり，漸化式を使う方法です。ただし，(解法2)と異なり，直接に，題意の数の場合の数を扱います。 n 桁の数の場合の数を f(n) とします。すると，最高位の桁，n 桁目，の数字に関して， n 桁の数の n 桁目の数字が 1 の場合：n-1 桁目の数字は何でもいいので，f(n-1) 通りです。 n 桁の数の n 桁目の数字が 2 の場合：n-1 桁目の数字は何でもいいので，f(n-1) 通りです。 n 桁の数の n 桁目の数字が 3 の場合：n-1 桁目の数字は 1 又は 2 でないといけません。 このとき，n-2 桁目の数字は何でもいいので，f(n-2) + f(n-2) = 2 * f(n-2) 通りです。 以上なので， f(n) = f(n-1) + f(n-1) + 2 * f(n-2) = 2 * (f(n-1) + f(n-2)) です。ただし，実際に調べて，f(1) = 3，f(2) = 3^2 - 1 = 8 です。 (f(2) は，33 だけを除けばいいです。) 後は，f(6) を求めればいいので，順次計算して， f(3) = 2 * (f(2) + f(1)) = 2 * (8 + 3) = 2 * 11 = 22 f(4) = 2 * (f(3) + f(2)) = 2 * (22 + 8) = 2 * 30 = 60 f(5) = 2 * (f(4) + f(3)) = 2 * (60 + 22) = 2 * 82 = 164 f(6) = 2 * (f(5) + f(4)) = 2 * (164 + 60) = 2 * 224 = 448 したがって，448 通りになります。 これから掲示板を読もうと思いますが，今日は何やら忙しく，読み終わるのには少しかかるかもしれません．．． |
|
ネコの住む家
1月25日（木） 13:48:57
MAIL:uchi@sco.bekkoame.ne.jp 29232 |