用務員ぢょんたが日々勝手なことを書き綴っています。

2006年06月24日

ケーキ分割 

42_1.jpg

ひとつのケーキを、ゆずり合う気持ちのない二人(仮にA子、B子)で分ける場合、お互いが納得のいくように切るにはどうしたらいいか。はかりで重さを量ればいいってものでもない。その価値観は、乗っているイチゴの色や大きさだったり、クリームの量だったりもする。(ナイフに着いたクリームの事まで考慮するとより複雑になるので無視することにする)

よく出てくる話なので、すぐに答えられる人も多いと思うが、片方に「どちらも同じ価値」と思えるように二等分してもらう。そしてもうひとりが好きなほうを選ぶというものである。
これなら確かにどちらからも不満は出ないだろう。では、それが3人だったらどうだろう。

まず、A子にとって「これが全体の1/3の価値だよーん」という納得できる部分を切り出してもらう。(この時点でA子は自分が切り出した1/3でもいいし、残りの2/3の半分でもいいはず)

他の2人がそれを見て、どちらも「そうだね1/3だね」あるいは「それって1/3以下の価値しかないし」といったら話は早い。それをA子が取って、残りをB子とC子で前述の2分割の方法で分ければよい。

B子が「それって1/3以上の価値があるよ」、C子が「1/3以下の価値しかないね」といった場合は、B子がそれを取って、残りを同じく2分割の方法で分ければ不満は残らない。

厄介なのはB子もC子も「A子が切り出した部分は1/3以上の価値があるし〜」とぬかした時で、その場合もうひとりに(例えばB子に)その切り出した部分を、B子にとって1/3の価値になるように好きなだけ削ってもらう。(削った分は2/3のほうに添える)その削られた1/3をみてC子が「1/3以下になったじゃん」といったら、それをB子に、残りを2分割法でA子とC子に。「まだ大きいってば」とおっしゃった場合は、それをC子に、残りをA子とB子で分ける。これで解決である。ヒントは「ひとりが納得のいく一切れ」を見つけることにある。これで3人ともまんべんなく太ることができよう。

さらに4人5人と数が増えても、複雑にはなるが同じ方法で分割できる。「価値をお互い納得のいくように均等に分ける」世の中では、ケーキ分割問題(cake cutting problems)というアルゴリズムの一大分野となっており、いまだに国際会議で論文発表が行われているそうだ。

てきとーに切って、ジャンケンで勝った順に取ればいいのでは?という意見もあるが、それではだれかしらに不満が残る。もっとも「残りもので結構です。先にお取りください」と素直に言えるのが理想なんですけど、なかなかねぇ。
posted by ぢょんた at 00:00| Comment(0) | TrackBack(0) | 算数(かず)
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

この記事へのトラックバックURL
http://blog.sakura.ne.jp/tb/33517477

この記事へのトラックバック