ウォームアップ問題
まずはウォームアップ問題を簡単に書く。
ケーキが2つあって、Aさんはケーキを好きな大きさで2つに切る。Bさんは切られたケーキのどっちかを先に選べる権利を1個目のケーキで使うか2個目のケーキで使うかの選択権がある。1個目のケーキを先に選んだ場合、2個目は後に選ばないといけない。Aさんは1個目の選択が終わった後に2個目のケーキを切る。
Aさん、Bさんともに自分ができるだけ大きいケーキを食べたいと思っている。
Aさんが食べるケーキを最大にするにはどういう戦略をとればいいか。そのときAさんが食べることができるケーキは何個か?
【解答】
1個目のケーキをfと1-fに切り分ける。ここでfは大きい部分で、1/2 <= f <= 1を満たす（f=1といのはもう片方が無視できるくらい小さく切った場合)。
先にAさんが選ぶ場合、大きい方を選ぶのでfを取ることになる。2個目のケーキではBさんが大きい方をとるので、Bさんの取り分が最少になるように1/2できる。Aさんの食べるケーキをp個とすると、
p = f + 1/2 … ①
となる。
先にBさんが選ぶ場合、小さい方が残るので1-fを取ることになる。2個目はケーキでAさんは大きい方を取れるのでできるだけ大きく切る。Bさんの分は無視できるほど小さくなる。このときのAさんのケーキは
p = (1-f) + 1 = 2 - f … ②
となる。
①と②が同じ場合、Bさんがどっちを選んでもAさんは最大個のケーキを食べることができる。
つまり、f = 3/4で切ると、p = 5/4個食べることができる。
本題
では本題。
ウォームアップ問題同様に
- ケーキが3個になった場合
- ケーキが7個になった場合
どうすれば良いか？ついでにAさんはBさんよりどのくらい多く食べることができるか。
ここでAさんが先に選べる権利は1回だけで、残りはBさんが先に選べるとする。
【makingの解】
ケーキ3個の場合、同じようにfと1-fに切り分ける。
最初にAさんが選ぶ場合、残り2個はBさんが先に選ぶのでずっと半分に切る。
最初にBさんが選ぶ場合、残り2個の状況はウォームアップ問題と同じになるのでf'=3/4で2個目を切ればのこり5/4個ゲットできる。
ということで
p = f + 1/2 + 1/2 = (1-f) + 5/4
を解けばOK。
最初にf = 5/8できれば、p = 13/8個食べることができる。
あとは帰納的に解ける。
n個のケーキ
最初にAさんが選ぶ場合、残り(n-1)個はBさんが先に選ぶのでずっと半分に切る。
最初にBさんが選ぶ場合、残り(n-1)個の状況はケーキが(n-1)個のときと同じになる。
ケーキがn個のときのAさんの食べることができる最大の個数をp(n)とすると
p(n) = f + (n-1)*1/2 = (1-f) + p(n-1)
p(2) = 5/4
を解けば良い。
p(n) = (n+1)*1/4 + p(n-1)*1/2
f = (3-n)*1/4 + p(n-1)*1/2
AさんがBさんより多く食べることができる個数をm(n)とすると
m(n) = p(n) - (n - p(n)) = 2*p(n) - n
Clojureで解いてみる(分数が使えるので)
;; n < 2の場合は考えない。。
(defn p [n]
(if (> n 2)
(+ (/ (+ n 1) 4) (/ (p (- n 1)) 2))
5/4))
;; 何度も使うのでメモ化
(def p (memoize p))
(defn f [n] (+ (/ (- 3 n) 4) (/ (p n) 2)))
;; 表示
(doseq [i (range 2 8)]
(let [f (f i) p (p i)]
(printf "n=%d,f=%6s,p=%7s,m=%4s%n" i f p (- (* 2 p) i))))
実行結果
n=2,f= 3/4,p= 5/4,m= 1/2
n=3,f= 5/8,p= 13/8,m= 1/4
n=4,f= 9/16,p= 33/16,m= 1/8
n=5,f= 17/32,p= 81/32,m=1/16
n=6,f= 33/64,p= 193/64,m=1/32
n=7,f=65/128,p=449/128,m=1/64
こんな感じ。高校数学みたいっすな。
面白かったらぽちって↓
