教えてください

質問

nが正整数の時、n+2個の正整数を任意に選ぶ。選んだ中に差、あるいは和が2nで割り切れる２つの整数が存在することを示せ。
という問題です。よろしくお願いします。

回答No.4

nakaken88

（回答2を書いた者ですが、証明が間違っていたので、再投稿させていただきます。）

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つの整数が存在する。（証明終）

回答No.3

akinomyoga

n+2 個の整数を a_i (i=1, …, n+2) とします。背理法で行きます。示したい事の否定は:

仮定: a_i + a_j ≡ 0 または a_i - a_j ≡0 (mod 2n) なる組 (a_i, a_j) (i≠j) は存在しない…(H1)

になります。H1 を仮定すると矛盾が生じることを示します。証明の概要の例を以下に示します。細部については自分で考えてみて下さい。

(証明)
以降の合同式は mod 2n とする。
(H1) より a_i ≢ a_j, a_i ≢ -a_j (i≠j) である。
また、a_i ≢ 0, n の時、a_i ≢ - a_i である。
よって、±a_i (i=1, …, n+2) は、a_k ≡ -a_k ≡ 0 or n となる重複 r 個(r≦2)を除いて、mod 2n の下で相異なる。mod 2n で相異なる値の数を数えると、(n+2)×2 - r ≧ 2n+2 個になるが、mod 2n の下では相異なる数は最大でも 0～2n-1 の 2n 通りしかないので矛盾する。よって、仮定(H1)は棄却され、

必ず a_i + a_j ≡ 0 または a_i - a_j ≡0 (mod 2n) なる組 (a_i, a_j) (i≠j) が存在する■

回答No.2

nakaken88

ここでは、整数aを整数b(≠0)で割った余りとは、a=bm+r(mは整数、rは0以上b未満の整数)を満たすrを指すことにします。

選んだn+2個の正整数を、それぞれ2nで割った余りを考えます。また、元のn+2個の正整数に、それぞれ-1をかけて2nで割った余りもあわせて考えます。このとき、計算される余りは、2n+4個になります。一方、余りになりえる数字は、0から2n-1までの2n種類しかありません。よって、計算した余りの中に、同じ数字のものがあります。その2つの余りについて、対応する元の正整数を考えると、「差が2nで割り切れる」（2nで割った余りがともに等しい時）か、「和が2nで割り切れる」（片方を2nで割った余りともう片方に-1をかけて2で割った余りとが等しい時）が成り立ちます。よって、題意が示されました。

回答No.1

178-tall

「正整数」は、零を排除してるのだろう…けど。

　n = 3
　n+2 個 = 5 個 の任意正整数 = {1, 1, 1, 1, 1}

選んだ中に差、あるいは和が 2n = 6 で割り切れる２つの整数が存在するの？

1-1=0 は 6 で割り切れる…ということ？