前日のつづきです。
問題
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と呼ばれています。
出典はこの本です。このあとが難しくなるので興味ある人はぜひ。