2017年JJMO本選2問目の解答、解説

組み合わせ論と整数分野の複合問題です。

問題(改)

Nを2以上の整数とする。
黒板に相異なるN個の正の整数が書かれていおり、そのうちどの異なる2つの数の和も素べきであるとき、Nとしてあり得る最大値を求めよ。
ただし、素べきとは素数pと非負実数nを用いてp^nと表せられる整数のことである。

考え方

素べきとはすなわち、ある素数で割り切れたらその素数以外では割り切れないような数のことです。

1,2,3のどのふたつをとっても和が素べきであり、さらにもう一つ増やそうとすると、6を加えることができます。
とりあえず、最大個数は4と見ておき、具体的な議論に移ります。

しかし、pとなる値が混在していると超難解で見通しが立たないので、黒板の数からpが揃っているような部分を抜き出して考えます。

Nが十分大きいとき、黒板に書いた数から、x+yがpの倍数となるようなx,yを選ぶことができるようなpはp=2のみです。

これがx-yなら鳩ノ巣原理よりどのようなpでも成り立つのですが、和となると話は別です。

これにより、素べきという広い値から、2べきという狭い値に議論を写すことができます。

これらを踏まえて、解答を作っていきます。

解答

N=4のとき、黒板に1,2,3,6を書き込むことで、相異なる2つの和は3,4,5,7,8,9となり、条件を満たす。

N≧5のとき、条件を満たすように黒板に数を書き込む方法が存在しないことを、背理法を用いて示す。
条件を満たすように5個の正の整数を黒板に書き込む事ができると仮定し、矛盾を導く。

拡張した鳩の巣原理より、5つの整数のうち、偶奇が一致する3つ組が存在する。
また、そのような3つの組について、どの2つを選んでもその和は偶数のため、条件よりこれは2べきである。
すなわち、3つの数をそれぞれx<y<zとすると、非負整数a,b,cが存在し、
x+y=2^a
x+z=2^b
y+z=2^c
となる。
x<y<zより、a<b<cである。
連立方程式として、xの値を求めると、
x=(2^a+2^b-2^c)/2となるが、1<a<b<cおよび2進法の原理より、2^a+2^b<2^cとなり、これはxが正の整数であることに矛盾。

よって、仮定は間違っており、N≧5のとき、条件を満たすような書き込み方は存在せず、答えはN=4...(答)

感想

素べきの説明はありますが、あらかじめ素べきに触れている人じゃないと難しそうに感じました。

途中で解いた連立方程式に関連して、正n角形の各頂点にn個の実数を並べ、さらに各辺には両端の頂点に割り当てられた数の和を対応させる場合を考えます。

nが奇数であれば、各辺に割り当てられた数から、各頂点に割り当てられた数を一意に逆算できます。

nが偶数であれば、各辺に割り当てられた数について条件がつき、さらに各頂点に割り当てられた数は、(+定数)だけの自由度が生じます。

今回はn=3で、一意復元性があるのでうまくいきました。