【数セミ】エレガントな解答をもとむ【2011．2】

**１３２人目の素数さん** · 2011/01/16(日) 14:03:02

みんなで議論して問題を解きましょう。

ちなみに私は今は問２を解いています。まだ解けてません。

**１３２人目の素数さん** · 2016/07/12(火) 22:24:51.79

７月号の問１、図的にこういう感じで考えた。送った解答は式に起こしたもので、
図には言及していない。

(1)
XY平面上にAの要素をX座標、Bの要素をY座標として、すべての組み合わ
せについて点を打つと、長方形の範囲の（等間隔とは限らないが縦横は
揃っている）格子点状に散らばった|A|×|B|個の点群となる。この図に
傾き-1の斜め線を引けば、その線上の点についてはX,Y座標の合計値が
等しい。つまり|A+B|は、各点から傾き-1の線を引き、重複するものは除
いて、何本残るかを数えればわかる。ところが点群の右端または下端の
各点（これを集合Pとする）はそれぞれ明らかに異なる斜め線上に乗って
いる（不等式で厳密に証明できる）ので、斜め線の本数はPの要素数である
|A|+|B|-1以上。

(2)
・・・・
・・・・
・・・・
・・ＸＹ
・・ＺＷ

等号が成り立っている場合、各点から引いた斜め線は集合Pのいずれかの
点を通る。何となく正方格子状じゃないと駄目では？とわかるが、例えば
こう証明する。右下の4点(X,Y,Z,W)に注目すると、この4点のうち左上の
点(X)から引いた斜め線は集合Pのいずれかの点を通らねばならないが、
その線はすぐ右の点(Y)の下、すぐ下の点(Z)の右を通るため、候補は右下
の点(W)しかない（これも式で証明可）。つまり右下の点が傾き-1の線上に
あるため、4点は正方形を成している。この論理を1段ずつ上に向かって繰り
返すと、全点群の右端2列が正方格子状、左に向かって繰り返すと全点群の
下2行が正方格子状にあることがわかる。右端2列と上端2行が正方格子だから、
全体も正方格子であることが必要。つまり、AとBは等差数列から成り、かつ
その公差が等しくなければならない。

**１３２人目の素数さん** · 2016/07/12(火) 22:33:13.36

訂正
×右端2列と上端2行が正方格子だから、
○右端2列と下端2行が正方格子だから、