ヨーロッパ女子数学オリンピック 2018 問3

今回の記事はこちらの問題。EGMO2018本選の第3問です。

C1, … ,Cnをn人のEGMO選手とする。コンテストの後、彼女たちは次のルールに基づいてレストランの前に一列に並ぶ:

  • 料理長は最初に選手の並び順を指定する。
  • 料理長は1分おきに1 ≦ i ≦ nをみたすiを選ぶ。
    • 選手Ciより前にi人以上の選手がいるとき、選手Ciは1ユーロを料理長に支払い、直前のi人を抜かして割り込む。
    • 選手Ciよりも前にいる選手がi人未満であるとき、レストランが開きこの手順が終了する。

(a)料理長がいかなる選択をしても、この手順が無限回行われることはないことを示せ。
(b)各nについて、料理長が得られる最大の金額を求めよ。

できた並びに対して、どのような評価を計算して使用するか?これにすべてがかかってきます。

結論からいいますと、この評価で計算します。本番(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(α)とする。

このf(α)が、αに対して可能なすべての料理長の指示において減少することを示せば(a)を解くことができ、
またこの関数の値から(b)の最大値を絞り込むこともできるようになります。
ということで料理長の指示で並びが変わると減少することを示しましょう。

並びαに対して料理長が指定した番号kによって、Ckは前のk人を抜かして割り込めた場合を考え、このときにできた並びをβとする。
CkがCiを抜かしたとき、
i < k ならばαi,k = 0,βi,k=2i-1 となる。
i > k ならばαk,i = 2k-1k,i=0 となるため抜いた相手によらない変化量となる。
またCkがCiを抜かしていないときはαi,ki,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

すなわち、料理長が何らかの指示をすると並びαによる評価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
となり、すなわち料理長ができる手順の回数はこの値を超えないことがわかる。

これで上限がわかりました。次は下限です。こちらはその回数だけの操作をするものをみつける作業になります。

一連の操作Pnを、次のように帰納的に定義する。
・最初に選手を「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がわかる。

ということで、この手順はf(α)の最高値と一致し、上限と下限が一致しました。

したがって2n-n-1ユーロを得られる手順が存在し、
2n-n-1ユーロを超えて得られることはできないことが証明されたため、
料理長が得られる最大の金額は2n-n-1ユーロであるとわかる。
スポンサーリンク

シェアする

  • このエントリーをはてなブックマークに追加

フォローする

スポンサーリンク