3

2019ISL-A5 (便乗)

204
0

とりあさんが面白い解法を紹介していたので( これ )私は普通の解法を紹介します.

ISL2019-A5

x1,x2,...,xnは相異なる実数である.
1inji1xixjxixj={0, if n is even; 1, if n is odd. 
を証明せよ.

対称的な恒等式なので帰納法かラグランジュ補完を使えば出来そうだと思いました. なのでとりあえずラグランジュ補完の式を書いてみると...(fを高々n1次の多項式として)
f(x)=i=1nf(xi)jixxjxixj
なんかどうやっても完全に同じ式にすることは出来なさそう...(ちなみに公式解答にあるよう, 一部の係数のみ取り出すなど上手くやればこの方針でも出来ますが私は諦めました.)

すると帰納法が考えられます. ひとまずこの方針で考えていきます.
帰納法のステップを考えやすくするためにまずは示すべき式の左辺をF(x1,...,xn)とします. n=1のときは空積は1なのでF(x1)=1. n=2のときはF(x1,x2)=1x1x2x1x2+1x1x2x2x1=0 なのでやはり問題ないですね.
次は帰納法のステップを作れるか考えてみます. このために「n=kの時が正しいならばn=k+1の時も正しい」を示さないと行けないわけですが, 十分条件的なノリで「n=k+1の時正しいならばn=kの時も正しい」が言えるかを考えてみました. (これが上手くいかないとn=kの時とn=k+1の時の関係を見いだすのが難しいことになり, 少し帰納法の方針は渋そうという気分になるので) まあやれることは少なくて特殊値を代入してF(x1,x2,...,xk+1)からF(x1,...,xk)の形を作るぐらいしかありません. そこで式がきれいになりそうな値を探すとxk+1=1のときF(x1,...,xk,1)=1F(x1,...,xk)となることがわかります. なのでもう少し帰納法の方針を粘って探してみます. 帰納法の仮定からいくつかの特殊値を求めてそこから上手い具合に(n次関数はn+1個の点が分かれば一意に定まる的な定理を使って)示せないか, という感じです.

ここでこの問題を思い出してみましょう.

IMO2021-2

任意の実数x1,...,xnに対して, 不等式
i=1nj=1n|xixj|i=1nj=1n|xi+xj|
が成り立つことを示せ.

この問題は平行移動して式を簡単にして帰納法を回すのです.
と言うわけで差の部分が共通しているので平行移動が上手くいかないかと考えます.F(x1a,x2a,...,xna)を計算すると,
F(x1a,x2a,...,xna)=1inji1(xia)(xja)xixj
となります, この右辺はaに関する高々2n2次関数です. ここで方針を再確認します.

そこで式がきれいになりそうな値を探すとxk+1=1のときF(x1,...,xk,1)=1F(x1,...,xk)となることがわかります. なのでもう少し帰納法の方針を粘って探してみます. 帰納法の仮定からいくつかの特殊値を求めてそこから上手い具合に(n次関数はn+1個の点が分かれば一意に定まる的な定理を使って)示せないか, という感じです.

するとa=xi1のとき左辺に帰納法の仮定が使えそうです. これによって(xi達は相異なるので)n個の特殊値が分かりました. あとn1個特殊値が求まればよいですね. そこで似たような代入を探すと(1で上手くいくなら+1も試すかというノリでやったのですが)a=xi+1のときも上手く約分されて帰納法の仮定が適用できることが分かります. よってaの特殊値が2n個求まってめでたしめでたし...

と言いたいところですがxi1=xj+1が成立しているとこの議論は回りません. 従ってxi達が十分離れていることを仮定してその後に一致の定理みたいな議論で任意のxiで恒等式になっていることを言ってあげればよいでしょう.
これでこの問題を完全に解くことが出来ました.

感想
帰納法はすごい

投稿日:202239
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

整数が好きです

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中