前回の記事は19個の相異なる整数の中の4つの整数についてでしたが、これが15個の相異なる整数の中の4つの数ならどうでしょう？

前回も発想的には非常に難しかったけど、今回はさらに難しいですね～


単発の問題だと何も思わない所ですが、2問連続で解くと、自分的には鳩の巣原理をとことん追い込んだ非常にインパクトのある良問に見えてきます。


是非とも、前回の問題を見た後に、見てほしい問題ですね。

前回の記事はこちら
「19個の相異なる2桁の整数の中の4個の数」


難問中難易度☆☆☆☆

【問題】
15個の相異なる2桁の整数が与えられたとき、必ずその中にある4個の数$ \small a,b,c,d $が$ \small a + b = c + d $をみたすことを示せ。

前回の問題での解法は19個だからこそできる解法で、15個の場合では使えません。

もっと条件を制限するための情報を導かないといけない、これをどう考えるか。


【証明】
15個の相異なる2桁の整数が与えられたときについて背理法で示す。

15個の整数の中の任意の4整数$ \small a,b,c,d $において、
$$ a-c = d-b $$
は常に成立しないと仮定する。


任意の4整数について、$ \small a-c = d-b $は成立しないので、$ \small a-c = d-b $が成立するのは3整数のとき、すなわち任意の3整数$ \small i , j , k ( i > j > k ) $において
$$ i - j = j - k \ \cdots (1)$$
のときのみである。


ここで、$ \small j $を固定し、$ \small i,k $が動くようなイメージをする。

そのとき、$ \small i \neq i' , k \neq k' $なる$ \small i' , k' $についても、
$$ i' - j = j - k' \ \cdots (2)$$
となったとすると、$ \small (1),(2) $より、異なる4整数$ \small i , i' , k , k' $において
$$ i - i' = k' - k $$
となってしまい、これは矛盾することから、$ \small j $を固定したとき、$ \small i - j = j - k $となるような$ \small i , k $の組は高々1組である。


これは、すなわち15個の整数の中の数から$ \small j $を固定し、残りの14個の整数の中の任意の数$ \small x $としたとき、$ \small x - j $の値は、すべて異なるか、2つの同数を除いて他はすべて異なるかどちらかである。

これを事実$ \small (A) $とする。


また、$ \small i > j > k $なので、15個の整数の中で、$ \small j $が最大値と最小値をとることはない。

よって、$ \small i - j = j - k $となる$ \small ( i , j , k ) $の組み合わせは最大で13通りしかない。


ここで、15個の数の中から2数$ \small i,k $を選ぶ方法は$ \small _{ 15 }C_{ 2 } = 105 $通りである。

この中で$ \small i - j = j - k $となる$ \small ( i , j , k ) $が最大で13通りあるので、$ \small i - j \neq j - k $となるのは最低でも92通りである。


よって、事実$ \small (A) $より、15個の数の中から2数$ \small i,k $を選んだときの$ \small i - k $の値は最低でも92種類あるが、実際、2桁の2数の差は1から89の89種類しかないので、これは矛盾する。

よって、当初の仮定が否定された。

したがって題意は示されたことになる。


ちなみに、この問題はエピローグがありまして、どうやら、14個の時までは題意が成立するけど、13個の時は成立しないようです。

これらの証明は僕にはできていません。

できたら、また紹介します。