今日も8時間睡眠
8時8分888文字。何それ?

(証明訂正)n+2個の整数には、和か差が2nの倍数になる2つの整数がある

今朝、次の問題をブログでとりあげました。

nが正整数の時、n+2個の正整数を任意に選ぶ。選んだ中に差、あるいは和が2nで割り切れる2つの整数が存在することを示せ。
教えてください 【OKWave】

この問題に対し、僕は次のような回答を書きました

n+2個の数に対し、そのまま2nで割った余りと、-1倍して2nで割った余りを考えます(余りは、0以上2n未満になるようにします)。すると、余りは全部で2n+4個できますが、全部で2n種類しかないので、必ず同じものが存在します。この余りに対して、元の正の整数を考えると、和か差が2nの倍数になります。

これに対し、複数の読者の方から「この証明はn+1個でも成り立つように見えるが、『n=2で、1,2,4と選ぶ』が反例になるので、n+1個では成り立たない」という指摘をいただきました。僕も解いた(気になってた)時は「n+1個でも成り立つじゃん、変な問題だな」と思ってたんですが、変なのは僕の頭の方でした。

「必ず同じ余りが存在する」のは正しいのですが、その余りに対応する正整数が異なるとは限りません。なので、最後の部分がおかしいです。上の反例の場合、2nで割った余りは「1,2,0」、-1倍して2nで割った余りは「3,2,0」。同じ余りはありますが、元の数字も同じです。これはダメです。

そこで、次のように証明を書き直しました。

【訂正後】
n+2個の整数に対し、2nで割った余りを考える(余りは0以上2n未満)。これらの余りとnとの差を考えると、差は0からnまでのn+1種類の値しかとらないので、n+2個の余りの中には「nとの差」が一致するものが存在する。

「nとの差」が一致する余りを2つ選ぶ。これらが「共にn未満」か「共にn以上」なら、元の正整数の差は2nの倍数(2nで割った余りが、共にn-r、共にn+rの形だから)。「片方がn未満、もう片方がn以上」なら、元の数の和は2nの倍数(余りが、n-rとn+rの形だから)。よって、題意を満たす2つの整数が存在する。(証明終)

ご迷惑をおかけいたしました。ご指摘いただいた方々、ありがとうございました。

共有:
広告
日付の近い記事
関連しない記事(ランダム)
姉妹サイトなど