国際数学オリンピックで次のような問題が出題されました(出題文は変更)。
正五角形の各頂点に整数を一つずつ割りあてる。五つの整数の和は正であるとする。連続する三頂点に割り当てられた整数
について、
が負である場合は
をそれぞれ
に書き換える操作を行う。五つの頂点に割り当てられた整数のうち、一つでも負の数があればこの操作を繰り返し行う(二つ以上負の数があるときはどれか一つを選んで操作を行う)。有限回の操作で頂点に割り当てられた全ての数が零以上となるだろうか?
例
![f:id:integers:20171106145125p:plain:w400 f:id:integers:20171106145125p:plain:w400](https://cdn-ak.f.st-hatena.com/images/fotolife/i/integers/20171106/20171106145125.png)
に操作
![f:id:integers:20171106145135p:plain:w400 f:id:integers:20171106145135p:plain:w400](https://cdn-ak.f.st-hatena.com/images/fotolife/i/integers/20171106/20171106145135.png)
に操作
![f:id:integers:20171106145141p:plain:w400 f:id:integers:20171106145141p:plain:w400](https://cdn-ak.f.st-hatena.com/images/fotolife/i/integers/20171106/20171106145141.png)
に操作
![f:id:integers:20171106145147p:plain:w400 f:id:integers:20171106145147p:plain:w400](https://cdn-ak.f.st-hatena.com/images/fotolife/i/integers/20171106/20171106145147.png)
に操作
![f:id:integers:20171106145153p:plain:w400 f:id:integers:20171106145153p:plain:w400](https://cdn-ak.f.st-hatena.com/images/fotolife/i/integers/20171106/20171106145153.png)
に操作
![f:id:integers:20171106145204p:plain:w400 f:id:integers:20171106145204p:plain:w400](https://cdn-ak.f.st-hatena.com/images/fotolife/i/integers/20171106/20171106145204.png)
に操作
![f:id:integers:20171106145209p:plain:w400 f:id:integers:20171106145209p:plain:w400](https://cdn-ak.f.st-hatena.com/images/fotolife/i/integers/20171106/20171106145209.png)
六回の操作で全ての数が零以上になった!
解答
非負整数値関数 を
と定義する()。正五角形の五つの頂点に割り当てられた整数を反時計回りに
とし、
とする。もし、
であれば
となって、に対して操作を行った後の五つの頂点に割り当てられた整数に対する関数
の値は真に減少する。操作を行う負の整数が
以外であっても同様なので、操作は有限回で必ず終わる。
上記例では関数値はと推移している。
ちなみに同じ年の第一問もこのブログで紹介されています。
integers.hatenablog.com