インテジャーズ

INTEGERS

数、特に整数に関する記事。

IMO1986 Problem 3

国際数学オリンピックで次のような問題が出題されました(出題文は変更)。

正五角形の各頂点に整数を一つずつ割りあてる。五つの整数の和は正であるとする。連続する三頂点に割り当てられた整数x, y, zについて、yが負である場合はx, y, zをそれぞれx+y, -y, z+yに書き換える操作を行う。五つの頂点に割り当てられた整数のうち、一つでも負の数があればこの操作を繰り返し行う(二つ以上負の数があるときはどれか一つを選んで操作を行う)。有限回の操作で頂点に割り当てられた全ての数が零以上となるだろうか?

f:id:integers:20171106145125p:plain:w400

-4に操作

f:id:integers:20171106145135p:plain:w400

-2に操作

f:id:integers:20171106145141p:plain:w400

-7に操作

f:id:integers:20171106145147p:plain:w400

-2に操作

f:id:integers:20171106145153p:plain:w400

-5に操作

f:id:integers:20171106145204p:plain:w400

-3に操作

f:id:integers:20171106145209p:plain:w400

六回の操作で全ての数が零以上になった!

解答

非負整数値関数 f(x_1, \dots x_5)

\displaystyle \color{white}{f(x_1, \dots, x_5):=\frac{1}{2}\sum_{i=1}^5(x_{i-1}-x_{i+1})^2}

と定義する(x_{-1}=x_5, x_6=1)。正五角形の五つの頂点に割り当てられた整数を反時計回りにx_1, x_2, x_3, x_4, x_5とし、x_1+x_2+x_3+x_4+x_5 > 0とする。もし、x_3 < 0であれば

\displaystyle \color{white}{f(x_1, \dots, x_5)-f(x_1, x_2+x_3, -x_3, x_4+x_3, x_5)=-x_3(x_1+x_2+x_3+x_4+x_5) > 0}

となって、x_3に対して操作を行った後の五つの頂点に割り当てられた整数に対する関数 fの値は真に減少する。操作を行う負の整数がx_3以外であっても同様なので、操作は有限回で必ず終わる。

上記例では関数値は190 \to 158 \to 142 \to 86 \to 70 \to 30 \to 6と推移している。

ちなみに同じ年の第一問もこのブログで紹介されています。
integers.hatenablog.com