|
uchinyan |
|
はい，こんにちは。さて，今回の問題は．．．
う〜む，結構考えてしまいました。こんな感じで。 (解法1) 状況を探るためにも，とにかく地道にやってみました。 各桁の数字が 1 〜 4 で和が 10 になるので， まず，和が 10 になる 1 〜 4 のパターンを順序を無視して調べ，それらを一列に並べれば求める整数になります。 例えば，10 = 1 + 2 + 3 + 4 なので，パターンとしては 1 2 3 4，これを並べて 1234, 1243, 1324, ... などの 4! = 24 個，などです。 これを実行すると，次のようになります。「->」のあるのが意味のあるパターンで，「->」の右がそのパターンおける整数の個数です。 1 1 1 1 1 1 1 1 1 1 -> 10!/10! = 1 1 1 1 1 1 1 1 1 2 -> 9!/8! = 9 1 1 1 1 1 1 1 3 -> 8!/7! = 8 1 1 1 1 1 1 4 -> 7!/6! = 7 1 1 1 1 1 1 2 2 -> 8!/6!2! = 28 1 1 1 1 1 5 1 1 1 1 1 2 3 -> 7!/5! = 42 1 1 1 1 6 1 1 1 1 2 4 -> 6!/4! = 30 1 1 1 1 2 2 2 -> 7!/4!3! = 35 1 1 1 1 3 3 -> 6!/4!2! = 15 1 1 1 7 1 1 1 2 2 3 -> 6!/3!2! = 60 1 1 1 3 4 -> 5!/3! = 20 1 1 8 1 1 2 2 4 -> 5!/2!2! = 30 1 1 2 2 2 2 -> 6!/2!4! = 15 1 1 2 3 3 -> 5!/2!2! = 30 1 1 4 4 -> 4!/2!2! = 6 1 9 1 2 2 2 3 -> 5!/3! = 20 1 2 3 4 -> 4! = 24 1 3 3 3 -> 4!/3! = 4 2 8 2 2 2 4 -> 4!/3! = 4 2 2 2 2 2 -> 5!5! = 1 2 2 3 3 -> 4!/2!2! = 6 2 4 4 -> 3!/2! = 3 3 7 3 3 4 -> 3!/2! = 3 そこで，整数の総数は，「->」の右端の数を足せばいいので， 1 + 9 + 8 + 7 + 28 + 42 + 30 + 35 + 15 + 60 + 20 + 30 + 15 + 30 + 6 + 20 + 24 + 4 + 4 + 1 + 6 + 3 + 3 = 401 個 になります。 (解法2) (解法1)の途中で気付いたのですが， 例えば，1 1 1 7 には，1 1 1 2 5 の中間パターンがありますが，5 は既に 2 3 とパターン分けされており，和が 5 の場合に還元されます。 他の場合も同様で，これは和に関して漸化式が作れることを意味しています。 そこで，和が n の場合を a(n) 個とすると， a(1) は，明らかに 1 だけで，a(1) = 1 です。 a(2) は，2 = 1 + 1 = 2 より， 最上位桁の数字が 1 で残りの桁の数字の和が 1 の場合の a(1) と 2 自体で， a(2) = a(1) + 1 = 1 + 1 = 2，です。 a(3) は，3 = 1 + 2 = 2 + 1 = 3 より， 最上位桁の数字が 1 で残りの桁の数字の和が 2 の場合，最上位桁の数字が 2 で残りの桁の数字の和が 1 の場合，3 自体で， a(3) = a(2) + a(1) + 1 = 2 + 1 + 1 = 4，です。 a(4) は，4 = 1 + 3 = 2 + 2 = 3 + 1 = 4 より， 最上位桁の数字が 1 で残りの桁の数字の和が 3 の場合，最上位桁の数字が 2 で残りの桁の数字の和が 2 の場合， 最上位桁の数字が 3 で残りの桁の数字の和が 1 の場合，4 自体で， a(4) = a(3) + a(2) + a(1) + 1 = 4 + 2 + 1 + 1 = 8，です。 n >= 5 の場合は，n = 1 + (n-1) = 2 + (n-2) = 3 + (n-3) = 4 + (n-4) より， 最上位桁の数字が 1 で残りの桁の数字の和が n-1 の場合，最上位桁の数字が 2 で残りの桁の数字の和が n-2 の場合， 最上位桁の数字が 3 で残りの桁の数字の和が n-3 の場合，最上位桁の数字が 4 で残りの桁の数字の和が n-4 の場合で， a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) になります。この問題では，a(10) を求めるので， a(5) = a(4) + a(3) + a(2) + a(1) = 8 + 4 + 2 + 1 = 15 a(6) = a(5) + a(4) + a(3) + a(2) = 15 + 8 + 4 + 2 = 29 a(7) = a(6) + a(5) + a(4) + a(3) = 29 + 15 + 8 + 4 = 56 a(8) = a(7) + a(6) + a(5) + a(4) = 56 + 29 + 15 + 8 = 108 a(9) = a(8) + a(7) + a(6) + a(5) = 108 + 56 + 29 + 15 = 208 a(10) = a(9) + a(8) + a(7) + a(6) = 208 + 108 + 56 + 29 = 401 そこで，401 個，になります。 なお，単に計算の便宜ですが，n >= 6 以上は， a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) = a(n-1) * 2 - a(n-5) と変形して計算した方が楽かもしれませんね。 |
|
ネコの住む家
11月10日（木） 13:35:10
38563 |