今回の記事はEGMO2018本選の第３問です。問題は公式サイトから確認してください。
できた並びに対して、どのような評価を計算して使用するか？これにすべてがかかってきます。
結論からいいますと、この評価で計算します。本番(270分以内)で思いついたらすごい。
選手の並びαが与えられたとき、
1 ≦ i , j ≦ n であるi,jに対しαi,jは
・CiがCjより前に並んでいるなら0
・CiがCjより後ろに並んでいるなら2i-1
とし、1 ≦ i < j ≦ n であるi,j全体で考えたαi,jの総和をf(α)とする。
1 ≦ i , j ≦ n であるi,jに対しαi,jは
・CiがCjより前に並んでいるなら0
・CiがCjより後ろに並んでいるなら2i-1
とし、1 ≦ i < j ≦ n であるi,j全体で考えたαi,jの総和をf(α)とする。
このf(α)が、αに対して可能なすべての料理長の指示において減少することを示せば(a)を解くことができ、
またこの関数の値から(b)の最大値を絞り込むこともできるようになります。
ということで料理長の指示で並びが変わると減少することを示しましょう。
並びαに対して料理長が指定した番号kによって、Ckは前のk人を抜かして割り込めた場合を考え、このときにできた並びをβとする。
CkがCiを抜かしたとき、
i < k ならばαi,k = 0,βi,k=2i-1 となる。
i > k ならばαk,i = 2k-1,βk,i=0 となるため抜いた相手によらない変化量となる。
またCkがCiを抜かしていないときはαi,k=βi,kである。
CkがCiを抜かしたとき、
i < k ならばαi,k = 0,βi,k=2i-1 となる。
i > k ならばαk,i = 2k-1,βk,i=0 となるため抜いた相手によらない変化量となる。
またCkがCiを抜かしていないときはαi,k=βi,kである。
ということで、前後関係が変わる、抜かれた選手と抜いた選手の関係であるもののみを比較することになります。するとf(β)が最大となる条件が比較的容易に見えてきます。
したがって、i < kであるような選手Ciを可能な限り抜いたときがf(β)の最大になるが、
i < k であるような選手はi-1人しかいないので、最低でも1人はj > k をみたす選手Cjを抜いてしまう。これを考えると
f(α)-f(β) < αk+1,k – (β1,k + … + βk-1,k)
=2k-1 – (20+ … + 2k-2)
=2k-1 – (2k-1 – 1)(2-1) = 1
i < k であるような選手はi-1人しかいないので、最低でも1人はj > k をみたす選手Cjを抜いてしまう。これを考えると
f(α)-f(β) < αk+1,k – (β1,k + … + βk-1,k)
=2k-1 – (20+ … + 2k-2)
=2k-1 – (2k-1 – 1)(2-1) = 1
すなわち、料理長が何らかの指示をすると並びαによる評価f(α)は1以上小さくなり、また評価は負の値にならないので、手順は無限回行われないということがいえる。□
これで(a)が示せました。これだけならもっと簡単な評価もありそうですが、
こんな面倒そうな式は(b)を見越して用意しています。
実は(b)の解はf(α)がとりうる最大値に等しいのです。ということでまずは上限の絞り込みから。
1 ≦ i < j ≦ n においてαi,j ≠ 0 であるような並びは
すなわち i < j ならばCiがCjよりも後ろに並んでいるということで
並び「Cn, Cn-1, … ,C1」のときの評価である。
この並びをγとおくとその値は
sum{i=2 .. n} ( sum{j=1 .. i-1} γj,i)
= sum{i=2 .. n}(sum{j=1 .. i-1} 2j-1)
= sum{i=2 .. n}(2i-1-1) = 2n-2-(n-1) = 2n-n-1
となり、すなわち料理長ができる手順の回数はこの値を超えないことがわかる。
すなわち i < j ならばCiがCjよりも後ろに並んでいるということで
並び「Cn, Cn-1, … ,C1」のときの評価である。
この並びをγとおくとその値は
sum{i=2 .. n} ( sum{j=1 .. i-1} γj,i)
= sum{i=2 .. n}(sum{j=1 .. i-1} 2j-1)
= sum{i=2 .. n}(2i-1-1) = 2n-2-(n-1) = 2n-n-1
となり、すなわち料理長ができる手順の回数はこの値を超えないことがわかる。
これで上限がわかりました。次は下限です。こちらはその回数だけの操作をするものをみつける作業になります。
一連の操作Pnを、次のように帰納的に定義する。
・最初に選手を「Cn, Cn-1, … ,C1」と並べる。
・n=1は以上で終了。n ≧ 2 では以下の操作をする。
・最初に選手を「Cn, Cn-1, … ,C1」と並べる。
・n=1は以上で終了。n ≧ 2 では以下の操作をする。
- 先頭を除くn-1人に対し操作Pn-1を施し、
並びを「Cn, C1, C2, … ,Cn-1」とする。 - 順番に番号1,2, … ,n-1を指定し、
並びを「Cn-1, Cn-2,… C1, Cn」とする。 - 末尾を除くn-1人に対し操作Pn-1を施し、
並びを「C1, … ,Cn-1,Cn」とする。
Cnを除くn-1人に対してサブの操作を考える、というよくありそうな手法です。この手順による回数を計算しましょう。
このPnで実行する手順の回数をanとすると、料理長はanユーロ得られることになる。
まずP1では並べるだけで何もしないのでa1=0である。
n ≧ 2のときはまず操作Pn-1を施した後にn-1人指定し、さらにPn-1を施すので
an = 2an-1+n-1がわかる。
これを変形するとan +n+1= 2(an-1+n)となり、
a1+1+1=2と合わせてan +n+1 = 2nが導かれ、
したがってan= 2n-n-1がわかる。
まずP1では並べるだけで何もしないのでa1=0である。
n ≧ 2のときはまず操作Pn-1を施した後にn-1人指定し、さらにPn-1を施すので
an = 2an-1+n-1がわかる。
これを変形するとan +n+1= 2(an-1+n)となり、
a1+1+1=2と合わせてan +n+1 = 2nが導かれ、
したがってan= 2n-n-1がわかる。
ということで、この手順はf(α)の最高値と一致し、上限と下限が一致しました。
したがって2n-n-1ユーロを得られる手順が存在し、
2n-n-1ユーロを超えて得られることはできないことが証明されたため、
料理長が得られる最大の金額は2n-n-1ユーロであるとわかる。
2n-n-1ユーロを超えて得られることはできないことが証明されたため、
料理長が得られる最大の金額は2n-n-1ユーロであるとわかる。