|
uchinyan |
|
はい，こんにちは。さて，今回の問題は．．．
これは単純ですがなかなか面白い問題だと思います。こんな感じで。 (解法1) いい加減ぽいですが結局は正しい答えになる解法です。 1 〜 77777 の 77777 個の整数のうち 11111 個が 7 の倍数です。そしてこれらの 7 の倍数は周期 7 で均等に並んでいます。 一方で，1 〜 6 のカードは 5 枚ずつあるのでこれらから作られる 5 桁の整数の各桁の数字は 1 〜 6 を自由に取れます。 そこで個数は 6 * 6 * 6 * 6 * 6 個で，7 の倍数の出現の仕方は周期 7 で均等に出現する 1 〜 77777 の一部なので， おおよそ，11111 * (6 * 6 * 6 * 6 * 6)/77777 = (6 * 6 * 6 * 6 * 6)/7 = 1110 余り 6 個，程度です。 もちろん個数は整数なので，1110 個 又は 1111 個ですが，題意を満たす 7 の倍数を 77777 から引いても題意を満たし， しかもその二つが等しいことはあり得ないので，個数は偶数のはずで，1110 個，になります。 (解法2) 漸化式ぽい解法です。 まず，1 〜 6 のカードは 5 枚ずつあるのでこれらから作られる 5 桁の整数の各桁の数字は 1 〜 6 を自由に取れます。 これらのうちの 7 の倍数の個数を 5 桁なので A5 個とします。 この 5 桁の数を 5 桁目 * 10000 と残りの下 4 桁に分けます。すると， 10000/7 = 1428 余り 4，20000/7 = 2857 余り 1，30000/7 = 4285 余り 5， 40000/7 = 5714 余り 2，50000/7 = 7142 余り 6，60000/7 = 8571 余り 3，なので， 下 4 桁のうち 7 の倍数でないものとうまく組み合わせれば下 4 桁 1 個に対し 1 個ずつ 5 桁で 7 の倍数を作れます。 つまり，A5 = 下 4 桁のうち 7 の倍数でないものの個数，です。 そこで，下 4 桁のうち 7 の倍数を A4 個とすれば， A5 + A4 = 下 4 桁のうち 7 の倍数でないものの個数 + A4 = 下 4 桁全部の個数 = 6 * 6 * 6 * 6 下 4 桁についても，4 桁目 * 1000 と残りの下 3 桁，に分けて同様に考え，さらに，下 3 桁，下 2 桁，と繰り返すと， A4 + A3 = 6 + 6 + 6，A3 + A2 = 6 * 6，A2 + A1= 6，です。 そこで，A1 = 0 なので， A2 = 6 - A0 = 6， A3 = 6 * 6 - A2 = 36 - 6 = 30， A4 = 6 * 6 * 6 - A3 = 216 - 30 = 186， A5 = 6 * 6 * 6 * 6 - A4 = 1296 - 186 = 1110， つまり，求める個数は 1110 個になります。 (解法3) いわゆる包除の原理を用いる解法です。 まず，1 〜 6 のカードは 5 枚ずつあるのでこれらから作られる 5 桁の整数の各桁の数字は 1 〜 6 を自由に取れます。 ここで，もし下 1 桁に 7 を使うことができたら，上位 4 桁をうまく決めて必ず 7 の倍数を作れます。 そして，この場合の 7 の倍数の個数は上位 4 桁の個数と同じで，6 * 6 * 6 * 6 個，です。 しかし，実際には下 1 桁に 7 は使えないのでこれを除きます。これは上位 4 桁が 7 の倍数となる場合です。 これを求めるのに，先ほどと同様に，上位 4 桁の下 1 桁に 7 が使えれば， 同様にして，上位 3 桁の個数 6 * 6 * 6 個で，これを引きます。 ところがやはり 7 は使えないのでその分，上位 3 桁が 7 の倍数の個数，を足します。 これも同様に上位 3 桁の下 1 桁に 7 が使えれば，上位 2 桁の個数 6 * 6 個でこれを足すわけですが， やはり 7 を使えないので，上位 2 桁が 7 の倍数の個数 = 6 個，を引きます。 少しややこしいですが，結局， 求める個数 = 6 * 6 * 6 * 6 - 6 * 6 * 6 + 6 * 6 - 6 = 1296 - 216 + 36 - 6 = 1110 個 になります。 (解法1)は，端数の処理が少しあいまいな気もしますが，7 の倍数の出現の規則性と個数が偶数より，大丈夫でしょう。 (解法2)と(解法3)は，見かけは違いますが実は等価で，(解法2)の式をまとめて書けば(解法3)と同じです。 7 を追加して考える(解法3)の工夫は面白いのですが少し難しいかな。ややこしいし。 個人的には(解法2)の方が考えやすいですが，漸化式ぽい考え方に慣れていないと辛いのでしょうか。 |
|
ネコの住む家
7月17日（金） 13:52:28
43501 |