|
uchinyan |
|
#25121：どうかなー (^^; 帰納的に可能なのかな？
一応、私の考えた証明を書いておきますが、私の証明では、残念ながら、ちょっと無理のような気がしますね。 (#25112のお金を集める問題の証明) n = 1 は、500円玉を持っている人から始めればいいので、明らか。 n-1 以下で、正しいと仮定します。 500円玉を持っている人を適当に一人選んでその人から開始するとします。その人を 1 と番号をつけておきます。 もし、これで最後までうまくいけば、問題なしです。 うまくいかなかった場合、1000円札を持っていておつりが払えなくなる最初の人を k+1 番目の人とします。 すると、1 〜 k では受付さんの持っている500円玉は 0 個以上で、k でちょうど 0 個になっています。 このとき、1 〜 k の人は、500円玉を持っている人と1000円札を持っている人とが同数です。 そうでないと、k でちょうど 0 個になりません。 そこで、k >= 2 で、この 1 〜 k の人を除いた残りの人、k+1, ..., 2n-1, 2n は、2n 人より少なく、 500円玉を持っている人と1000円札を持っている人とが同数になっています。 したがって、残りの人に帰納法の仮定が適用できて、残りの人には、必ず、受付さんの徴収は成功します。 この場合の開始する人を A とします。 すると、k+1 の一つ前、2n か A (A が 2n の場合)、では、受付さんの500円玉は 1 個以上です。 さて、1 〜 k の人を戻して 2n 人の場合、この A から新たに徴収を開始します。 すると、A 〜 2n までは除いた場合と同じで問題なく、1 〜 k はそもそも問題なく、 k+1 の番でも受付さんは 1 個以上の500円玉を持っているので問題なく、後は、除いた場合と同じで問題なく、すべてうまくいきます。 (証明終) この証明では、うまくいかなかった場合、及びその 1 〜 k の特定ができそうにないので、開始する人を特定するのは無理そうですね。 他のうまい証明があればいいのですが．．． |
|
ネコの住む家
5月20日（金） 17:31:21
MAIL:uchi@sco.bekkoame.ne.jp 25124 |