|
uchinyan |
|
スモークマンさんの問題：その２
＞問題 ＞どのようなn個の整数の組み合わせでも、その中から、合計が18で割り切れるような18個の数を選ぶことができる。 ＞そのようなnの最小値をみつけてください。 答えは、35 だと思います。以下、全然スマートではないのですが、ちょっと面白いと思う証明です。 [証明] 問題を、次のように一般化します。 ＞問題(m) ＞どのような n 個の整数の組み合わせでも、その中から、合計が m で割り切れるような m 個の数を選ぶことができる。 ＞そのような n の最小値をみつけてください。 m で割り切れるかどうかがポイントなので、整数としては、m で割った余り、0 〜 m-1 で考えればいいです。 さて、まず、m = 2 の場合を考えます。 n = 2 では、題意を満たさない組み合わせとして (0, 1) が取れるので、n >= 3 です。 n = 3 の場合は、(0,0,0), (0,0,1), (0,1,1), (1,1,1) なので、題意を満たすことが分かります。 したがって、n = 3 です。 次に、m = 3 の場合です。 同様にして、(0,0,1,1), n = 4 が題意を満たさないので、n >= 5 で、n = 5 で実際に一つずつしらみつぶしに具体的に調べてみると、 題意を満たすことが分かります。 (ちょっと追加) 0, 1, 2 のどれかが三つある場合は明らか。それ以外の場合は、 (0,0,1,1,2), (0,0,1,2,2), (0,1,1,2,2) しかないですが、いずれも題意を満たします。 (追加終了) したがって、n = 5 です。 さらに、m = 9 の場合を考えます。 (0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1), n = 16 は題意を満たさないので、n >= 17 です。そこで、n = 17 を考えます。 m = 9 = 3 * 3 に注目します。 17 > 5 なので、合計が 3 で割り切れるような 3 個の整数を取ってくることができます。このとき、残りは 17 - 3 = 14 個です。 14 > 5 なので、同様にして、合計が 3 で割り切れるような 3 個の整数を取ってくることができます。残りは 14 - 3 = 11 個です。 これを繰り返して、合計が 3 で割り切れるような 3 個の整数の組を 5 組まで取ってくることができます。 さて、この 5 組には、それぞれの組の 3 個の整数の和という整数が一つずつ対応しています。 つまり、5 個の整数があることになります。 そこで、この 5 個の整数について考えると、合計が 3 で割り切れるような 3 個の整数を取ってくることができます。 この新たな 3 個の和は、3 の倍数ですが、それぞれが元々 3 の倍数だったので、3 * 3 = 9 の倍数になります。 また、最後の和に寄与する整数の個数は、各組に 3 個ずつだったので、3 * 3 = 9 個です。 つまり、n = 17 のとき、合計が 9 で割り切れるような 9 個の整数を取ってくることができました。 さて、いよいよ、m = 18 = 2 * 9 です。 今までの議論からほとんど明らかですが、n = 2 * (18 - 1) = 34 では題意を満たさない例が作れ、n >= 35 です。 n = 35 の場合は、合計が 9 で割り切れるような 9 個の整数の組を 3 組まで取ってくることができます。 この 3 組には、それぞれの組の 9 個の整数の和という整数が一つずつ、都合、3 個の整数が対応しています。 そこで、この 3 個の整数について考えると、合計が 2 で割り切れるような 2 個の整数を取ってくることができます。 この新たな 2 個の和は、2 の倍数ですが、それぞれが元々 9 の倍数だったので、9 * 2 = 18 の倍数になります。 また、最後の和に寄与する整数の個数は、各組に 9 個ずつだったので、9 * 2 = 18 個です。 つまり、n = 35 のとき、合計が 18 で割り切れるような 18 個の整数を取ってくることができました。 そこで、題意を満たす最小の n は、35 になります。 [証明終] この解法が面白いと思うのは、m が合成数の場合、その因数の場合に問題を帰着できる点です。 また、今までの値から、n = 2m-1 ではないか、と予想できます。 したがって、もし、m = p、ただし p は素数、に対して、n = 2m-1 = 2p-1 がいえれば、 すべての m に対して、帰納法によって、n = 2m-1 が証明できそうです。 残念ながら、今のところ、m = p の場合の証明はできていません。 また、全くスマートでない点も問題ですが．．． |
|
ネコの住む家
9月30日（金） 14:57:51
MAIL:uchi@sco.bekkoame.ne.jp 25907 |