2006年01月09日

【回答225ではありません】自分のボーナスを当てるには

問題編は一息ついたときの小ネタ【問題225】を参照ください。

この問題は、ケンブリッジ大学のコンウェイ(John Horton Conway)という有名な数学者が考えた問題です。知らなかったんですが、パソコン黎明期に流行ったライフゲーム(方眼の一つのマスを生物に見立てて、隣接するマスの状態で死んだり生まれたりする条件で全体の繁殖状況を考察するシミュレーションで、うまく「生物」を配置すると幾何学模様が綺麗に広がっていきます)、あれも彼が考案したものだそうです。

ところで、回答の方なのですが、参考した書籍にはこの問題が解けるとしか載っておらず、私は斜め見をして既存の帰納法を使った問題(例えば、黒い帽子をかぶった三人の男がいて・・というのが最も有名だと思われます)を応用して解けば良いとタカをくくっていたのですが、実際回答を書くのに解いていったら、相当に複雑で、最後まで解けませんでした。

それで問題として出しておきながら大変恐縮なんですが、この回答はまだ出来上がっていません。(どなたか解いていただけると嬉しかったりする状況です)

考え方としてはこうです。
(1)この問題は必ず解けます。コンウェイはこれが10人ではなくn人の場合でも(つまり何人であっても)成立し、最大n回質問されるまでに必ず自分の額の金額を当てる人が出る、と言い切っています。

(2)問題としてはメタパズルで、このように説明することになると思われます。
まず一人の場合に成立することを示し、次に二人の場合に成立することを示します。社員が二人のときには、二人目は一人目が答えられなかったという事実を新しい情報としてもらうことで自分の額の金額を当てることができます。これを10人の場合まで広げていきます。


途中までやった内容だけでもUPしようと思ったんですが、かえって混乱させてしまうかもしれないと思い、やめました。(一般化するのが難しいです)
ということでこの問題の回答は、すいません、うまく説明できるまで更新しません。(そのうちこっそり回答が書いてある書籍を探し出してUPしているかも)

うまく説明できる方、いらっしゃいましたら是非コメントをください。そのうちにキャロルの骨付き肉問題のように回答を募集するようになるかもしれません。



知り合いの天才肌の人に訊いてみる
posted by fakerholic at 00:23| Comment(12) | TrackBack(0) | 頭の体操クイズネタ回答集 | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
2人の場合すら分かりません…
仮に社員Aが10万円、社員Bが11万円で、
ホワイトボードに21万円、23万円と書かれていたとして、
Aが答えられなかったことからBが得る、新しい情報とは何でしょう?
Bが11万だろうが13万だろうがAは答えられない気がします。
それだけでも分かる方教えてください。
とりあえず2人の場合の答えが分かれば満足です。
質問のくせに長くてすいません。
Posted by ずん at 2006年01月09日 02:37
「順番に訊いていく」が一定の規則性
(例えば,金額の高い順など)
を持っているということであれば
解けそうですが・・・.
Posted by JIN at 2006年01月09日 18:30
社員が金額の多い順番は分かっている、というのも考えたのですが、
Aが16万、Bが11万、ホワイトボードが27万、29万となるときっとダメですよね。
ルールは単純なのにすごい問題です。自分の頭の固さが情けない。
Posted by ずん at 2006年01月09日 21:33
考え方を変えてみました。
Aが答えられなかったことからBが情報を得るということは、
Aが答えられる場合があるという事です(ホワイトボードの一方の金額がBの金額より小さい場合以外にも)。
ここでゲームの主旨を、Aが一発で自分の金額を当てられるか、というものにしてみます。
ここで、AとBの金額に関連性はないので、Bの金額を足すことに意味はありません(Bは答えないので)。
つまり、社長がAの金額と適当な数字をボードに書いて、Aが自分の金額を当てるゲームをしているのです。
絶対答えられませんね…。
必ず答えられるとは限らない、という結論になってしまいました。
この問題が頭から離れなくなってしまいました。
Posted by ずん at 2006年01月10日 12:47
金額がそれぞれ違うというのは重要ですね。
ただ、やはり条件が足りない気が・・・
Posted by 太郎 at 2006年01月10日 15:47
例えばそれぞれAからJまで1万円から10万円のボーナスだとして、合計55万円。
黒板には49から58までの10個数字が書いてあるとしたとき、
Aは54(他の9人の総計)を見て55か56か57か58が合計だと思い、(0がないとすれば)、56では2がだぶり、57では3が、58では4がだぶるので55が正解で、自分のボーナスは1万円だと分かってしまいます。

10人目までは分かってはいけないわけですから、これではいけません。すると、それぞれのボーナス額と、白版に書いてある数字(あるいはそのうちの一つ)に何らかの特殊性がないといけないということになりそうです。

…例えばフィボナッチ数とか。
Posted by 橘 at 2006年01月10日 22:28
ずんさんの,「Aが16万、Bが11万、ホワイトボードが27万、29万」のときも質問の回数を限定しないと分かるかも・・・.

<説明>
AがBの11を見て・・・
自分(A)は少なくとも12以上.
合計は23以上.
両方とも23以上ゆえ分からない.

BがAの16と,答えを聞いて・・・
自分(B)は少なくとも15以下だが・・・
ここで,Aが分からないといっていることから,
○自分(B)が14以上と仮定・・それを見てAは自分(A)は15以上と推測・・合計が29以上・・分かるはず
○自分(B)が13と仮定・・・・それを見てAは自分(A)を14以上と推測・・合計が27以上・・分からない
○よって,自分(B)は13以下である.
よって,合計は29以下である.
両方とも29以下であるため分からない.

Aはその答えを聞いて・・・
Bは自分(B)を13以下であると把握した上で分からないと判断した(○の思考は推定可能).
つまり,自分(A)は14以上である.
ここで,Bが分からない場合とは・・・
○自分(A)が15or14と仮定・それを見てBは自分(B)は13以下だから合計は28以下・・分かる
○自分(A)が16と仮定・・・・それを見てBは自分(B)が13以下だから合計は29以下・・分からない
○よって,自分(A)の数字は16以上である.
よって,合計は27以上である.
両方とも27以上であるため分からない.

Bはその答えを聞いて・・・
Aは自分(A)を16以上であると把握した上で分からないと判断した(○の思考は推定可能).
Aが自分(A)を16以上と把握していて分からない場合.
自分(B)が13or12と仮定・・・それを見てAは自分(A)が16以上だから合計は28以上・・分かる
自分(B)が11と仮定すると・・・それを見てAは自分(A)が16以上だから合計は27以上・・分からない
よって,自分(B)の数字は11以下である.
よって,合計は27以下である.
27以下は一つしかないので合計は27
よって,自分は11.

間違っているかもしれませんが・・・.
長文で失礼しました.
Posted by JIN at 2006年01月11日 12:46
<追記>
上の例だと,
AとBは,互いの大小関係を教えられなくても,
推測できますね.
Posted by JIN at 2006年01月11日 13:11
えっとぉ。遅いですがコメントします。

例えば、

ボーナス
A:10円
B:0円

ホワイトボード
@10円
A30円

だとしたらどうですか??
(こんな会社は入りたくないですが、わかりやすくって事で)
質問も1回で済むはずです。

1人目がわからなくて、2人目は必ずわかる。
と、言う前提であれば、それに沿った値を作ってあげる。
と、言うことで考えてみました。
(黒い帽子をかぶった三人の男がいて・・・もそうだったかと思います。)

きっとこれは、どんなボーナスの金額、ホワイトボードの値でもできるのではなくて、たまたまそれがわかるような金額、ホワイトボードの値だったんではないでしょうか?

では、上記の例は??

まず、Bは最初の段階ではわかることができません。
このときのBの選択肢は
@0円
A20円
のどちらかです。

では、Aに質問をして見ます。
Aは当然わかるわけはないです。
このときAの取る選択肢としては、
@10円
A30円
のどちらかです。

しかし、Bはこの解答をきいて、新たな情報を得ました。
それはなにか??
Aの20円ではないと言うことです。
もし、自分が20円なら、Aは迷わず「10円」と答えるでしょう。

と、言うわけでBは自分のボーナスが0円と言う悲惨な事実を知ることができました。

と、言う考えで2人はできるかと思います。

間違ってるんじゃないか??と、いう方がいらっしゃいましたら、教えてください。
Posted by きゅうぴぃ at 2006年02月02日 11:04
だいぶ遅いけどコメントします

2人の場合の
「仮に社員Aが10万円、社員Bが11万円で、
ホワイトボードに21万円、23万円と書かれていたとする」を流用します。

@社員Aがトータル23万だと考えて
 23−11(Bの金額)=12万円と答える  →不正解

Aこのとき社員Bは自分のボーナスが
 Aは自分のボーナスの金額を見て答えているので
 21−9万円(Bのボーナス)=12万円(Aの間違い)
 23−11万円(Bのボーナス)=12万円(Aの間違い)
 のどちらかから答えを出したと類推することができます。

B社員Bは社員Aのボーナスが10万円とわかっているので、
 自分のボーナスの仮定から
 10(Aの金額)+9(Bの類推)=19万円
 10(Aの金額)+11(Bの類推)=21万円
 と計算することができます。
Cホワイトボードに書いてある金額は
 21万円と23万円なので
 Bの式が成り立つ21万円が正しいことがわかり、社員Bのボーナスは11万円ということが わかります。

3人4人・・・と増えてもやることは同じです。
ただし 10人いると計算がとてもめんどくさくなりますが・・・。
Posted by きいぼ at 2006年02月20日 04:37
きいぼさんのコメントを一般化して。

Aのボーナスをa、Bのボーナスをbとすると、ホワイトボードの金額はa+b、a+b+xです(xは0以外)。
Aが勘でa+b−bからaと答えれば正解。a+xと答えれば不正解。
その場合Bは、ホワイトボードの金額からa+xを引いて、自分がb−xかbのどちらかであると分かる。
BにはAの金額が見えているので、それを足してa+b−xとa+b。
ホワイトボードの金額と一致するのはa+b。よってBはbと答えられる。

ただ、問題を読む限り、社員は正直者ですから、分からなければ分かりませんと言い、勘では答えないようです。
勘で答えていいなら正直者という条件はいらないですし。
Posted by ずん at 2006年02月20日 15:13
ついでにやってみました。
社員n人の場合に、必ず自分のボーナスを当てる人が現われると仮定し、社員がn+1人に増えた場合を考えます(帰納法)。
社員1〜n+1のボーナスをN1〜N(n+1)とします。
ここでt番目に答える人(社員t)の考えに注目すると、自分のボーナスは、
Nt、Nt+X1、…、Nt+Xn
と考えます(Xは0以外)。
社員1が仮にN1+Xkと答えて不正解となったら、社員tは自分は
Nt−Xk、Nt+X1−Xk、…、Nt、…、Nt+Xn−Xk
のどれかであると分かります。
最初の候補と社員1が答えた後の候補は、必ず違ってきますから、少なくとも1つは偽のホワイトボードの金額が判明します。
そしてこのとき消える候補はXの値で決まりますから、全ての社員(t=2〜n+1)に共通です。
社員n人の場合に誰かが正解すると仮定してあるので、1つ候補が減れば十分ですから、n+1人の場合にも誰かが正解すると証明できました。
あとは社員2人の場合は上のコメントで証明したので、nに2を入れれば3人4人…と自動的に証明できます。

携帯で打ちながら考えたので、間違ってるかもしれないし、もっと簡単にできるかもしれません。
Posted by ずん at 2006年02月20日 15:14
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:


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

この広告は1年以上新しい記事の投稿がないブログに表示されております。