- - PR -
論理的思考力テスト【解答つき】
| 投稿者 | 投稿内容 | ||||||||
|---|---|---|---|---|---|---|---|---|---|
|
投稿日時: 2006-08-23 12:01
ん〜。『球の軽重を判定しなくてよいので、「２７÷２で、上限は１３だ」というのは誤り』
というのが伝わりにくいようですね。 ちなみに、１４個の不明な球と、１個の標準球の１５個の組み合わせで、２８通りの状態候補がありますが、どれが犯人球かを判定することができますよ。 あと、量子状態を使った場合のもうちょっと具体的な方法を教えていただけないでしょうか？ ちょっとイメージができませんでした。 観測結果は、確率分布などじゃなくて、右に傾く、釣り合う、左に傾くといずれかですよね？ あとで、昼休みに、昨日からの考えをまとめてみます。 | ||||||||
|
投稿日時: 2006-08-23 12:09
右にいる偽者が軽いから左に傾いているのか、左にいる偽者が重いから左に傾いているかはわからないですよね。 27と13.5を含めて検索したら答えが出てきました（これがあっているかどうかはお任せしますが） http://www.m.is.sci.toho-u.ac.jp/message/puzzle-1.html
とても楽しみにしています。 ２７だと思っている人は他にいらっしゃるのでしょうか？ どうもわちゃさん以外はそうではないと考えているように見えますが。 [ メッセージ編集済み 編集者: ほげほげ 編集日時 2006-08-23 12:11 ] [ メッセージ編集済み 編集者: ほげほげ 編集日時 2006-08-23 12:12 ] | ||||||||
|
投稿日時: 2006-08-23 12:58
＃ちょっと、書き込みに厳密性を求め始めてしまったので、非常に読みにくい文です。
＃興味が、すごいある方を除いて、この書き込みはムシされることをオススメします。 どうも、おさわがせしております。 log2n で、ログか、RSS かを整理するツールと思ってしまったわちゃです。 さて、私の主張が「判定可能な上限は、２７個である」と誤解されているのでしょうか。 上限に関する私の主張は、「判定可能な上限は１３個」です。 しかしながら、その根拠として、、「２７÷２で、上限は１３だ」というのは誤っているという 事を申し上げております。 「２７÷２で上限は１３だ」という説明であれば、１４個の不明な球と１個の標準球による ２８通りの状態候補からの犯人球の特定が可能であるという事実に対して矛盾してくるように 思います。 また、coasm さんの10ページの書き込みと同様に、軽重の判別不能な回答になる場合を含めて、 2*n - 1 ≦ 27 という不等式が成り立つはずと考えました。 そのため、「犯人が重いか軽いかを指摘しなくても良い場合」であれば、１４個まではできるかも しれないという考えに至っておりました。 そして、14 個でできないかと考えた末に、一つの標準球を追加することで解決できました。 この場合、１４個の不明な球と、１個の標準球の１５個の組み合わせで、２８通りの状態候補が ありますが、どれが犯人球かを判定することができたわけです。 さて、2*n - 1 ≦ 27 という不等式にある「−１」の根拠ですが、軽重の判別不能な回答になる場合 というのは、その球を天秤に一度も乗せていない状態となります。 ここで、二つ以上の球を天秤に乗せていないという事はありえないため、軽重の判別不能な回答は、 一つの球にしかありえず、状態数に対する補正は、「−１」のみとなります。 このような、軽重の判別不能な回答となる場合を、以降「状態の縮退」と呼びます。 ここまでの結論は、１４個が判定可能な上限である事を示しています。 ＃上限であり、１４個で可能な事は示していません。 そして、１４個では、標準球を追加するというインチキをする事に可能な事は具体的な方法によって 示すことが可能ですが、インチキをしない場合に１３個が上限であることを示すのは、もう少し ややこしくなってしまいます。 これは、標準球を追加しない場合に 13 個が上限であるというのは、13 個で出来るということと 14個ではできないという反証でいけるかと思います。 １４個ですと、状態候補数は２８通りになり、これを最初の試行の結果によって、状態候補を ９通り，９通り，１０通りに絞り込む必要があります。 なぜ、傾いた場合に９通り以下に絞り込む必要があるかというと、傾いてしまった後は 「状態の縮退」が起こらないため、試行によって得られる情報量と、状態候補の数は常に 「情報量 ≧ 状態候補の数」という不等式が成り立つためです。 また、なぜ、傾かない場合に１０通り以下に絞り込む必要があるかというと、「状態の縮退」を 含めて、「情報量 ≧ 状態候補の数＋１」という不等式が成り立つためです。 それでは、傾いた場合に９通りの状態候補に絞り込む事ができるでしょうか？ 例えば、右に傾いた場合は、右側に乗せた球のどれかが重い可能性と、左側に乗せた球のどれかが 軽い可能性しかありません。 つまり、右に傾いた場合に絞り込まれた候補の数は、右に乗せた球の数と、左に乗せた球の数の 合計になってしまいます。 これは、どうやっても偶数ですよね。 というわけで、傾いた場合は、偶数通りの候補数しか得られないので、もっともよい場合でも、 最初の試行で、最初にある候補を、８，８，１０に絞り込むのが上限となります。 これは、１３個の場合ですよね。 で、１３個の場合は、がんばればできますので、１３個が上限という結論になるかと思います。 | ||||||||
|
投稿日時: 2006-08-23 17:20
ほげほげ殿が、問題の答えとしてあげられたホームページを見てみました。
たしかに、n ≦ 13.5 が上限のように書かれていますが、 最後の方に以下のような記述があります。 ＞この問題の微妙なところは，不等式 n ≦ 13.5 は必ずしも厳密な議論の結果ではないことである． このように、この筆者自身 n ≦ 13.5 を導いた過程は厳密なものでなく、正しいと認めていませんでした。 | ||||||||
|
投稿日時: 2006-08-23 17:24
最初は天秤を1回使うことで得られる状態が3通りなので
3^3=27通りの状態を区別できるため、 27通り以下の状態の判断ならできるだろう、と考えました。 そして、n個の玉のうち１つが重いか軽いとなれば、そのパターンは n個×(重い、軽いの2パターン) = 2nパターン となるので、2n <= 27 の不等式を整数で解くことで13個が限界と考えました。 しかし、この単純な考え方では、 14個の不明球と1個の標準球のケースを解けることを説明できません。 では、何が間違っているのか？ それは、「天秤を1回利用したときに得る情報」についてではないかと思うのです。 天秤がつりあわなかったことによって、比較された玉は 「重い、軽い、標準」の3値を取る可能性があった状態から 「軽い、標準」か、「重い、標準」の2値しか取らない状態になります。 残された玉が標準で確定することばかり考えていましたが、 3値を取る可能性が2値になることは大きい。 この天秤が与えてくれる情報をどう評価するべきなのでしょう？ そこに関しては考えがまとまらないので後日の宿題として…。 14個を判別できる論拠を私なりに示します。 天秤3回の施行ですから、1回目が等しい場合と等しくない場合に分けて考えます。 等しくなかった場合、天秤にかけられた玉は3値をとる可能性から 2値を取る可能性になります。 2値を取る場合、残り2回の施行で確定できる上限の数は9個ですね。 （混ざっている玉が重いか軽いかわかっていればn回で3^n個から識別可能） 等しかった場合、残りの3値を取る可能性がある玉を2回の施行で 確定させなくてはなりません。 2回目の施行が等しくなかった場合、2値を取る玉に答えが残ります。 残りの1回の施行でこれを確定させれる上限は3個ですね。 2回目の施行が等しい場合、残った3値を取る玉を天秤1回で 確定させる必要があります。 これは、標準玉との比較という操作になり、確定させれる上限は2個です。 ただし、これが釣り合った場合に比較がなされなかった玉は軽重不明となります。 軽重を確定させたければ、ここの上限は1個となります。 以上から、目方が不明でよいのであれば9 + 3 + 2 = 14個の場合までは 判別が可能となります。 ただし、1回目の天秤の施行のあとで2値を取りうる玉を9個にするには 標準玉を混ぜて、4個+1個：5個という比較の仕方が必要となるのですよね。 標準玉がない場合、1回目の施行の際に2値を取りうる玉を9個残すことができません。 8個残すことは可能なので、1個上限が減って13個となる、というところでしょうか。 以上の指針から実際の操作を想定するのは難しくはありませんよね。 | ||||||||
|
投稿日時: 2006-08-23 17:29
よくかんがえてみたら、天秤操作を重ね合わせる必要があるので無理ですね^^; 演算結果が重ね合わせ状態になるわけですから…。 # 量子コンピュータの量子ビットを利用した演算って # 理解がどうも怪しくてなりません…。修行が足りてません 
| ||||||||
|
投稿日時: 2006-08-23 19:43
並行世界でネアンデルタールが天秤に球を乗せているイメージが浮かびました。 私は量子コンピュータについて何か誤解しているのでしょうか？ | ||||||||
|
投稿日時: 2006-08-23 20:16
あぁ、量子コンピュータの話だったんですね。普通の量子力学で考えてました。
あんまり量子コンピュータの話を知らなかったので、調べてみたのですが、 量子状態を測れる天秤でやれば、nagise さんのおっしゃるとおり天秤を「使う」のは一回 でいいかもしれませんね。 ただ、観測というか、データを取得するのは３回必要かもしれませんけど。 とりあえず、量子コンピュータについて浅学の身ですが、私も Yam さんの「並行世界でネアンデルタールが天秤に球を乗せているイメージ」というのは、 分かりやすい例えであるように感じました。 で、１４個＋標準１個の場合のパラドックスについてですが、 私は、証明っぽくしようとしたので書き方が複雑になってしまいましたので、 むしろ coasm さんの考え方の方がイメージしやすいかもしれません。 つまり、「１３個の球の重い、軽いの組み合わせ」による２６個の状態候補と、 「１３個の重さは同じ」という１個の状態候補（つまり１４個目の重さが異なる）の 合計２７個の状態候補からの絞込みになるということです。 このように考えると、丁度、得られる情報量と等しくなるので、 できる気がしてきますよね。 ちなみに１４個の場合の nagise さんの論証は、おおむねよいようにも見えますが、 最初に傾いた場合、９個の球に２値の可能性が残るという意味では正しいですが、 ここから具体的にどれとどれを乗せてやればいいかというのは、さほど自明では ありません。 | ||||||||
スキルアップ／キャリアアップ（JOB@IT）
Copyright © ITmedia, Inc. All Rights Reserved.
著作権はアイティメディア株式会社またはその記事の筆者に属します。
当サイトに掲載されている記事や画像などの無断転載を禁止します。
著作権はアイティメディア株式会社またはその記事の筆者に属します。
当サイトに掲載されている記事や画像などの無断転載を禁止します。