---
title: 「プログラマのための論理パズル」(1)甘いもの好き
tags: []
categories: ["Programming", "Algorithm", "Puzzles"]
date: 2011-05-23T16:05:58Z
updated: 2011-05-23T16:58:02Z
---

### ウォームアップ問題

まずはウォームアップ問題を簡単に書く。

ケーキが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` … ①

となる。

<a href='/./upload/00027/cake1.png'><img src='/./upload/00027/cake1.png' /></a>
<a href='/./upload/00028/cake2.png'><img src='/./upload/00028/cake2.png' /></a>

先に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

こんな感じ。高校数学みたいっすな。


----

面白かったらぽちって↓

<a href="http://www.amazon.co.jp/exec/obidos/ASIN/4274067556/ikam-22/ref=nosim/" name="amazletlink" target="_blank"><img src="http://ecx.images-amazon.com/images/I/51Dh-xfpqXL._SL160_.jpg" alt="プログラマのための論理パズル 難題を突破する論理思考トレーニング" style="border: none;" /></a>