山分けの問題

こういうタイトルでいいのかどうかわからないけれど、こういう問題す。

二人の盗賊が宝石の山の宝を盗み出した。追っ手が迫ってるので、 素早く納得いくように分けたい。秤など使わないで、平等に分ける方法はあるか?

答えとしては以下のようになります。

1)盗賊Aが宝を均等と思われるところで二つの山に分ける。

2)盗賊Bがその山のうち特だと思われるほうを先に選ぶ。

ここまでは有名。 この問題をn人に拡張できるのか?というのが最近考えています。

これが結構難題。

たぶん答えはあるんですが(ググるとそれらしきものにヒットするしね~) 解答を見たら負けということで。

もし話し合いというのを許すなら、4人の場合は次のようにすればよいでしょう。 1)A、BとC、Dのグループにわける。 2)A、B連合は相談して山を二つに分ける。 3)C、D連合は相談してどちらかの山を先に選ぶ。 4)あとは、それぞれの山を二人で先ほどのように分ければよい。 しかし話し合いをしているヒマすらないという場合も考えられますし、 そもそも決裂してしまったら意味がない。しかも3人の場合はどうするんだ? とか考えると、もっとよいやり方があるのかなぁ・・と 1)Aが3つに分ける。 2)Bが1つの山を選ぶ 3)Cがさらに1つの山を選ぶ。もし、B、Cが別の山を選べば、それで確定。 4)B、Cが同じ山を選んだとすれば、Aは残りの山のどちらかから1つ選ぶ。 5)残った2つの山を1つにまとめ、Bが再配分。先にCが選び、残りをBとする。 これでいいような気がするけど、ちょっと問題があるんですよねぇ。 100の宝石を分けるとき、Aが1,49,50と分けたとします。 B、Cが二人とも50を選ぶことはありません。Bが選んだあとCも50を選ぶとすると、Aは49を選ぶことになり、その結果B、Cは51を二人で分け合うことになるからです。これは損です。 よって、Cは49を選ぶしかない。つまり、このケースではBの選択権が強すぎて、 Cはどう転んでも最大利益の50を選ぶ権利がありません。 じゃぁ、B、Cが同じのを選択したときはCに権利があるとすると、 今度はCの選択権が強すぎてBはどう転んでも50を選べない。 よってこの方法では手詰まりです。 なんかもっとうまい方法はないですかねぇ?じゃんけんすれば一発という解答はなしの方向でw

Posted by issei

カテゴリ: 数学

コメント一覧

と、ここまで書いていい方法を思いついた。今からベッドで検証しま~
Isami

1. BとCが相談して2つの山を選ぶ 2. 残った山は A のもの 3. B と C の山を1つにまとめて B と C で山分け でどうでしょう?
kawamaco

kawamocoさんのでは1でBとCの意見が割れた場合が困ると思います。 私の解答。 1. Aが山を3つに分ける 2. BとCが欲しい山を同時に選ぶ 3. BとCで欲しい山が異なる場合、それぞれ欲しい山を取り、Aが残りの山を取って終了。 4. BとCで欲しい山が同じの場合。それぞれ取りたくない山を同時に選ぶ。 5. 取りたくない山が同じ場合、取りたくない山はAのもの。残りの山を合わせてBとCの間で山分け。 6. 取りたくない山が別の場合、BとCが最初に選んだ山はAのもの、BとCは互いにが選んだ取りたくない方の山をとる。 この方法では選択権を持ってるBおよびCに優劣はつきません。
ふたつき

ごめんなさい、名前間違えました。 kawamaco さんでした。
ふたつき

むー。上の私の方法は3人ではできるけど、n人には拡張難しいかな...。 うまく対称性持たせて人数を減らすのと、山を分ける操作をする人への公平性を確保するのがうまく両立するのか。
ふたつき

3人の場合の奴もまだダメでした。 Aの立場とB,Cの立場を比較して有利・不利がないこと示せていない。ということは、山を最初に分ける人を決めるとこでモメるのでこれはダメ。
ふたつき