|
問題3908(友人問)
100以下の相違なる正の整数16個の中には、相違なる4つの数a,b,c,dであって、
a+b=c+d となるようなものが存在することを示せ。
解答
・わたしの
再考^2...
15C2=7*15=105
ここにもう1個の数を持って来たとき新たにできる数は...明らかに16種類だが...
16C2=8*15=120
120-105=15 種類しか増えないのだから...
16-15=1
少なくとも１組は同じ和になっているはず...
でいいのかなぁ...^^;?
・友人からのもの...
16個の整数を小さい順に a(1)<a(2)<...<a(16) とする。
これらのうちの2つのペアの差を考える。
そのようなペアは16C2=120通りある。
ペア(a(i), a(j)) と書いたとき、a(i)>a(j) となるようなものとする。
異なるペア (a(i1), a(i2)), (a(i3,), a(i4)) があり、a(i1)-a(i2)=a(i3)-a(i4) をみたすとき、
a(i2)=a(i3) でなければ、(a,b,c,d)=(a(i1), a(i4), a(i2), a(i3)) は問題の条件を満たす。
整数 a であって、ペア (a(i1), a), (a, a(i2)) ...(＊) について a(i1)-a=a-a(i2) (つまり a(i1)+a(i2)=2a) をみたすとき、a は悪い数、(＊) を a による悪いペアということにする。
悪い整数 a について、a による悪いペアが２組以上存在すると証明は完結する。なぜなら、(a(i1), a), (a, a(i2)) と (a(i3),a), (a, a(i4)) がいずれも悪いペアなら a(i1)+a(i2)=2a=a(i3)+a(i4) となるからである。
以降、どの a(i) についても、a(i) による悪いペアは高々1つと仮定しよう。
このとき、悪いペアは高々16個なので、悪いペアでないペアは少なくとも 120-16=104個ある。
一方、2つの数の差は 1以上99以下である。
よって、鳩の巣原理により差の等しい2つのペアが存在する。
すると、a(i1)-a(i2)=a(i3)-a(i4) なる (a(i1), a(i2), a(i3), a(i4)) が得られ、これが問題の条件を満たす。
*う〜ん...わけわかめ...^^;...?
|
コメント（1）
