|
uchinyan |
|
スモークマンさん、weaponさんへ：
スモークマンさん、お仕事ご苦労さまです。 もう既に議論が進んでしまいましたが、一応、スモークマンさんの問題を考えてみましたので、 どちらもあまりスマートではありませんが、ご参考までに。 問題1 nを正の整数とする。このときnの倍数であり、桁数がn+1 を超えず、かつ33....300....0の形で表される整数がある ことを示せ。 数字 d が m 個並んでいるのを d...(m)...d と書くことにします。 今、3 が m 個、0 が k 個並んでいる場合、問題の整数 c は 3...(m)...30...(k)...0 で、m + k <= n+1 です。 ただし、m >= 1, k >= 1 と思われます。このとき、 c = 3...(m)...30...(k)...0 = 10^k * 3...(m)...3 = 2^k * 5^k * 3...(m)...3 に注意します。 さて、一般に正の整数 n は、n = 2^a * 5^b * N、ただし N は 2 も 5 も素因数にもたない、と書けるので、 n | c となるには、a <= k, b <= k, N | 3...(m)...3、が必要十分です。 ・a = b = 0 の場合 もし 3...(m)...3 が N 以下の異なる m1, m2, N >= m1 > m2 に対して N で割った余りが等しいとすると、 3...(m1)...3 - 3...(m2)...3 = 3...(m1 - m2)...30...(m2)...0 は N の倍数のハズで、N は 2 も 5 も素因数に含まないので、3...(m1 - m2)...3 は N で割り切れることになります。 もし 3...(m)...3 が N 以下の異なる m に対して N で割った余りがすべて異なるとすると、その中には 0 になるものがあるはずです。 いずれにしても、N 以下の適当な m に対して、N | 3...(m)...3 が成立します。 この m に対して、a = b = 0 なので、n = N となり、n >= m なので、k = 1 として題意を満たします。 ・a not= 0 又は b not= 0 の場合 a <= k, b <= k の条件より、k を a, b の大きい方に取ります。 n = 2^a * 5^b * N より、 n+1 - k - N = 2^a * 5^b * N + 1 - k - N = (2^a * 5^b - 1) * N + 1 - k >= 2^a * 5^b - 1 + 1 - k = 2^a * 5^b - k 明らかに 2^a > a, 5^b > b、及び k = a or b なので、 > a * b - k = a * (b - 1) or (a - 1) * b >= 0 つまり、n+1 - k >= N です。 N に関する条件 N | 3...(m)...3 は、a = b = 0 の場合と同じなので、n+1 - k >= N >= m となる m をとることができます。 したがって、題意を満たします。 以上で証明は終わりです。 問題2 白と黒の球が100個ずつ一列に並んでいますが、左端と右端 は黒の球です。左端から連続したいくつか（全部ではありません） の球を選んで、白と黒の数が等しいようにできることを示せ。 左端から順番に球を取っていくことを考えます。 そして、どこまで取っていっても白黒が同数にならない、と仮定します。すると．．． 左端は黒なので、二番目は黒でなければなりません。つまり、二つの球は、黒黒です。 三番目は白でも黒でもOKですが、取った三つの球の色は黒の方が多くなります。 四番目は、三番目が黒ならば白でも黒でもOKですが、三番目が白ならば黒でなければなりません。 この場合の四つの球の色も黒の方が多くなっています。 以降も同じで、左端から n 個取ったときの球の色は黒の方が多くなっていなければなりません。 何故なら、もし同数ならば最初の仮定に違反します。 もし白の方が多かったら最初は黒の方が多かったので、どこかで同数にならなければなりませんが、これも仮定に違反します。 となると、左端から199個球を取ったとき、199個の球は黒の方が多いことになりますが、200個目、右端、も黒なので、 200個の球は黒の方が多いことになります。これは最初の「白と黒の球が100個ずつ一列に並んでいます」という条件に矛盾します。 そこで、どこかで白と黒の数が等しいようにできることになります。 |
|
ネコの住む家
12月31日（土） 21:36:38
MAIL:uchi@sco.bekkoame.ne.jp 26448 |