N人ウイロー問題

プログラムは何の関係もありませんが。
「二人でケーキを分ける際に、お互いから文句が出ない切り分け方は?」という有名な問題があります。
有名な問題なのでご存知と思いますが、AとBの二人がいるとき、Aが半分に切り分け、Bがその二つから好きな方を選べばよいのです。 Aが自分で公平に分けたため、どちらでも文句を言えないわけです。
それでは、Nを3以上の自然数とした場合、N人で文句が出ないよう切り分けるにはどうすればいいでしょうか(情報工学的表記)?
ちなみに条件として、「各人が出来るだけ大きな量を得ようとすると、必ずN等分になる」「各人は自分自身の得しか考えない(共謀しない)」といった前提があります。 どんな順番で切って、どんな順番でういろうを選べば公平になるか、軽く考えてみてください。

この問題に特定の名前は付いていないので、N人でういろうを切り分ける「N人ウイロー問題」と名付けました。
アルベルト・F・ウイロー(1954-)みたいな数学者は存在しないのであしからず。



解答の前に、考察途中に考えた誤答を紹介します。 A、B、Cの三人で選ぶと仮定した場合、
【3人ウイロー問題の誤った解】
・Aが3分の1を切り分ける
・Bがその余りから2分の1を切り分ける
・Cが二人によって分けられた3つから一つ選ぶ
・Bが残りの二つから一つ選ぶ
・Aが余りを受け取る

この方法は一見すると公平になるように見えます。
しかし、一つ大きな問題があるのです。
以下のような場合。

Aが綺麗に3分の1に分けた場合。120°に見えない?モニタの映りが悪いんじゃないですか?

ってオイ!Bが露骨に適当に切り分けやがった!!

Cはこれ幸いとばかりにでかい部分を持って行きました。

そしてBは綺麗に分割された部分を持って行きました。きれいに分割したのに、哀れA。
Bはどんな分け方をしてももらえる量はほとんど決まってしまっているため、等分に分ける必要がないのです。
「各人が出来るだけ大きな量を得ようとすると、必ずN等分になる」という点にそぐわなくなっています。


さて、解答編です。 といっても僕一人の頭で考えたものなので、どこかに穴があるかもしれません。答えを思いついた方はどうぞ突っ込みどころを探してください。

【N人ウイロー問題の解】
1.AがういろうをN等分する
2.Bがその中から最も小さいものを選び、Aに与える
3.Bがその残りのういろうをN-1等分する
4.Cがその中から最も小さいものを選び、Bに与える
~以下ういろうが無くなるまでループ~

不公平な分け方をすると自身の不利益に直結するため、全員が平等に分けることになります。 冒頭の解法との共通点は、「自分が分けて他人が選ぶ」ということですね。

何度もういろうを切り分けた場合、ういろうが細切れになってしまうという問題点がありますが、 最初にAが平等に切っていればその作業を省略することは可能なので、実際はそれほど問題にならないことでしょう。