2025年JMO本選1問目をオマージュした自作問題の紹介

色々解法があると思いますが、今回は組み合わせ論と不等式の関わりを紹介するために、組み合わせ論的意味を考える解法を紹介します。

実を言うと、テンパって誤読して解いただけなんですが、元の問題よりも難しく、結構面白い問題だと思います。

問題

nを2以上の整数とする。2n個の実数a₁,a₂,…,a_(2n)が、任意の1≦i<j≦2nなる整数i,jについて|ai-aj|≧1を満たすとき、

(a₁-a₂)²+(a₂-a₃)²+…+(a_(2n-1)-a_(2n))²+
(a_(2n)-a₁)²

としてあり得る最小値を求めよ。

考え方

まずは数直線上でa₁,a₂,...,a_(2n)を並べて、単調増加な並び替えとして見てみると、条件はそれらによって切り取られる区間が全て1以上であると言い換えられます。

最小化すべき値を考えると、これらの区間は全て1である場合のみ考えればよく、もっというと絶対的な位置も最小化すべき値に関係ないので、a₁,a₂,...,a_(2n)は1,2,...,2nの並び替えと考えてよいです。

ここで、あくまで予想ですが、最適な場合になるかな？という両極端な事例を比較して、どちらがより最適か考えてみます。

(1)ちびちびパターン
1,3,5,…,2n-1,2n,2n-2,2n-4,…,4,2,(1)と、戻るときも含めて、全ての隣辺の差が小さめ(これが隣辺の差が最小な場合かはまだ分からない)

(2)最後に一気パターン
1,2,3,…,2n,(1)と、途中まで1ずつで、最後にまとめて戻る

(1)の場合は、2²×(n-1)+1²+2²×(n-1)+1²=8n-6

(2)の場合は、1²×(2n-1)+n²=n²+2n-1であり、
(2)-(1)=(n-2)(n-3)≧0より(1)の方が最適であると分かります。

メタいですが、わざわざ変数の数が偶数であると制限されているので、それをうまく利用した(1)が最適かなとは思ってしまいます。

ここで、私は不等式が大の苦手で、さらに脳内が組み合わせ論的解釈に毒されているので、それを使って解いていきます(？)

(a-b)²とは、aとbの間にある整数から整数にかけての長さ1の区間(以後、単位線分と呼ぶ。)
はa-b個あり、そこから、1つまたは2つを選ぶ方法の個数です。
ただし、2つ選ぶ場合は順序を区別するものとします。

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

解答

最小化すべき値をSとする。
数列akが1,3,5,…,2n-1,2n,2n-2,2n-4,…,4,2となる場合、
S=2²×(n-1)+1²+2²×(n-1)+1²=8n-6
となる。
上記の場合が最適であることを示す。


数直線上でa₁,a₂,...,a_(2n)を並べて、単調増加な並び替えとして見てみると、条件はそれらによって切り取られる区間が全て1以上であると言い換えられる。

最小化すべき値を考えると、これらの区間は全て1である場合のみ考えればよく、さらに、絶対的な位置も最小化すべき値に関係ないので、a₁,a₂,...,a_(2n)か1,2,...,2nの並び替えである場合のみ考えればよい。


また、(a-b)²とは、
aとbの間にある整数から整数にかけての長さ1の区間(以後、単位線分と呼ぶ)はa-b個あり、それらから1つまたは2つを選ぶ方法の個数である。
ただし、2つ選ぶ場合は順序を区別するものとする。

そのため、数列akを順路と解釈すると、Sとは、

数直線上の1,2,…,2nを1回ずつ経由して元の頂点に戻る順路についての、
各移動に対して、1つまたは2つの単位線分の組であり、「その移動で、選んだ格子線分をすべて同時に飛び越す」ようなものの個数の総和

といえる。
また、上記の個数は、格子線分を先に選んでから移動を選ぶことで、

数直線上の1,2,…,2nを1回ずつ経由して元の頂点に戻る順路についての、
1つまたは2つの単位線分の組に対して、「選んだ格子線分をすべて同時に飛び越す移動の回数」の総和

と言い換えられる。

ここで、単位線分を1つのみ選んだ場合、それを飛び越す回数は2回以上である。
また、連続する2つの格子線分の組を選んだ場合、それを全て飛び越す回数は1回以上である。

よって格子線分を選ぶ順序を考えると、S≧2×(2n-1)+1×(2n-2)×2=8n-6となり、題意は示された。

よって、Sとしてあり得る最小値は
S=8n-6…(答)

感想

1,3,5,…,2n-1,2n,2n-2,2n-4,…,4,2の場合は、
1つの単位線分を飛び越す回数はちょうど2回、連続する2つの格子線分を全て飛び越す回数はちょうど1回、それ以外の選び方では飛び越し切れないようになっています。

代数と組み合わせ論の複合はよく聞きますが、その中でも不等式はあまり聞かない気がします。

もしこの問題の純粋な不等式的証明が思いついたら教えてください！