n+2個の整数には、和か差が2nの倍数になる2つの整数がある

最近OKwaveでいろいろ回答してるんだけど、昨日こんな問題が質問としてあがっていました。

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

例えば、n=4の場合、適当に「12,23,34,45,56,67」と6個の数字を選んだとき、「45+67=112」のように和か差が8で割り切れるものが存在する、ということです。

数学で、こういう「存在する」系の問題の解法には、大きく分けると「具体的に条件を満たすものを作る」方法と「理論的に考えて導き出す」方法があります。後者の場合、「どこにあるかはわからないけど、確かに存在する」という感じで、ちょっと不思議な証明になります。普通の科学の場合、「おばけはどこにいるかわからないけど、確かに存在する」とかいっても「はぁ？」と言われて終わりですが、数学の場合は、そもそもいろんなものの存在を仮定しているから、「理論的に考えて存在を示す」ことが可能になります。

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

ポイントは、「2n+4個のものがあって、2n種類しかないなら、必ず同じものが存在する」という点です。数学ではこのような法則を「鳩ノ巣原理」といったりします。鳩ノ巣原理とは、「n個の鳩ノ巣にn+1羽のハトがいるとすると、どこかの巣に2羽以上のハトがいる」という当たり前の法則なのですが、大事なのは「どこにいるかはわからないけど、2羽以上いる鳩ノ巣が存在している」と言える点です。特に学校では習わない事柄ですが、数学オリンピックなどでは、鳩ノ巣原理の考え方を使う問題がよく出題されています。