QRコード
QRCODE
アクセスカウンタ
読者登録
メールアドレスを入力して登録する事で、このブログの新着エントリーをメールでお届けいたします。 解除は→こちら
現在の読者数 56人
東進の先生のブログ 安河内哲也先生             今井宏先生                    吉野敬介先生                金谷俊一郎先生                    林修先生                       大岩秀樹先生
沖田一希先生            
    

2010年04月25日

ちなみに3人の場合

前日のつづきです。


問題

AとBとCの3人で1つのケーキを切り分けたい。誰からも文句のでないように切るにはどうしたらよいか。ただし、3人の価値観は同じとは限らないものとする。


本当はケーキ分割問題のルールをきちんと定義しておいた方がいいんだけど、面白くないので省略(笑)。





まず、AとBで2等分する(その方法は前日のブログ)。
(このとき、A,Bは自分の価値観で2分の1以上のケーキをもっていることになる)

そのあと、A,Bそれぞれが自分の価値観で自分の持ち分を3等分する。そして、CがAの3切れの中からひとつ、Bの3切れの中からひとつ好きなものを選ぶ(AとBは各自の分の残った2切れをもらう)。


これで、3人のもっているケーキは自分の価値観で3人とも3分の1以上になります。 



これを繰り返せばn人でもケーキを分けることができます。この方法は、successive pair algorithmと呼ばれています。
出典はこの本です。このあとが難しくなるので興味ある人はぜひ。







  
Posted by 志田 晶 at 14:36TrackBack(0)