- PR -

論理的思考力テスト【解答つき】

«前のページへ 10|11|12|13|14|15|16|17|18|19|20 次のページへ»
投稿者投稿内容
にー
常連さん
会議室デビュー日: 2006/04/30
投稿数: 35
投稿日時: 2006-08-23 20:59
かなり難しそうな話題になっていますが、現実世界で13個から1つを特定する作業を玉と天秤を使って行ったら、天秤から手を離した瞬間に複数の玉がいっきに移動し、1回目や2回目の左・右においていた玉がどれであったか確認することが殆どできなくなるのでは? なんて思ってしまいました。

場合によっては、玉の重みの差が大きければ、天秤から落ちてしまうものもあるかも。

もっとも、玉の重みの差が大きければ、手で判別することもできそうで、天秤は1回も使う必要がなくなりますけど...

くだらない事を想像してしまいました。

ぼのぼの
ぬし
会議室デビュー日: 2004/09/16
投稿数: 544
投稿日時: 2006-08-23 21:52
こんばんは〜。

12個バージョンの解答は、私が自分で考える前に覗き見してしまったものが非常にわかりやすかったので、貼っておきますね。
12個バージョンの解答

この解答を応用して、13個バージョンと14個+正解玉1個バージョンの解答もつくってみました。
見たくない方もいらっさるでしょうから、リンクにしておきます。
13個バージョンと14個+正解玉1個バージョンの解答

んで、一連の投稿の流れに参戦すると、私はnagiseさんの説明が一番わかりやすかったです。
＃理解するのに時間がかかりましたけど…

ちょっと補足すると、
1回目の計測で、傾いた場合（容疑玉の状態が2値となる場合）を考慮することで「1回目に秤に乗せる玉の数」の上限が求められる。
1回目の計測で、釣り合った場合（容疑玉の状態が3値となる場合）を考慮することで、「1回目に秤に乗せない玉の数」の上限が求められる。
玉数の上限は、この２つの和となる。
また、「1回目に秤に乗せる玉の数」の上限は、3のべき乗すなわち奇数となるため、あらかじめ1個の正解玉を持っていないと必然的に1減る、と。

この理解が正しければ、n回秤を使って犯人玉を見つけ出すときの玉数の上限値は以下の公式で求められることになります。

Z(2) = 4（あらかじめ1個の正解玉を持っている場合は5）
n≧3の場合
Z(n) = 3^(n-1) + Z(n-1)

あってるかな？

＃単語が間違ってたので修正（×階乗○べき乗）

[ メッセージ編集済み 編集者: ぼのぼの 編集日時 2006-08-25 18:04 ]
nagise
ぬし
会議室デビュー日: 2006/05/19
投稿数: 1141
投稿日時: 2006-08-24 10:00
引用:

わちゃさんの書き込み (2006-08-23 20:16) より:
あぁ、量子コンピュータの話だったんですね。普通の量子力学で考えてました。

あんまり量子コンピュータの話を知らなかったので、調べてみたのですが、
量子状態を測れる天秤でやれば、nagise さんのおっしゃるとおり天秤を「使う」のは一回
でいいかもしれませんね。
ただ、観測というか、データを取得するのは３回必要かもしれませんけど。

測る操作の重ね合わせって、それは平行世界を利用して
天秤をたくさん使ってることになるんじゃないの？
と思えるので根本的に間違ってたように思います。


引用:

ちなみに１４個の場合の nagise さんの論証は、おおむねよいようにも見えますが、
最初に傾いた場合、９個の球に２値の可能性が残るという意味では正しいですが、
ここから具体的にどれとどれを乗せてやればいいかというのは、さほど自明では
ありません。

自明か、と言われると言葉に窮しますね。確かに。

容疑の玉が重いとわかっている場合、3個から容疑の玉を見つける場合には、
天秤の両側に1個ずつ重いかもしれない玉を乗せます。
そして、重かったほうが犯人で、釣り合えば天秤の外の玉が犯人ですね。

では、ここに軽いかもしれない玉が混ざっている場合はどうするか。
「標準か軽い」玉を「標準か重い」玉に変換してやればよい。
つまり、符号を反転させるのです。

具体的には天秤の左右を入れ替えれば符号反転相当のことができます。
「標準か重い」玉と「標準か軽い」玉を左に、標準の玉を右に2個置くことで
「標準か重い」玉を左右に置いて比較するのと同等のことができますね。
十分な数の標準玉が用意できるなら、「標準か重い」玉と「標準か軽い」玉の
混合状態は「標準か重い」玉が同数ある場合と同じ手数で判別可能なのです。

引用:

この理解が正しければ、n回秤を使って犯人玉を見つけ出すときの玉数の上限値は以下の公式で求められることになります。

Z(2) = 4（あらかじめ1個の正解玉を持っている場合は5）
n≧3の場合
Z(n) = 3^(n-1) + Z(n-1)


漸化式で書くとそうなりますね。私も同等の理解です。
1: 2
2: 2 + 3
3: 2 + 3 + 3^2
4: 2 + 3 + 3^2 + 3^3
...
あ〜。ばらしてもうまく纏められない…。
数学が得意な人、HELP!
ぼのぼの
ぬし
会議室デビュー日: 2004/09/16
投稿数: 544
投稿日時: 2006-08-25 18:13
うまく纏められました。

3^(n-1) + 3^(n-2) + … + 3 + 2
= 3^(n-1) + 3^(n-2) + … + 3 + 1 + 1
= 2(3^(n-1) + 3^(n-2) + … + 3 + 1) / 2 + 1
= (3-1)(3^(n-1) + 3^(n-2) + … + 3 + 1) / 2 + 1
= ((3^n + 3^(n-1) + … + 3^2 + 3) - (3^(n-1) + 3^(n-2) + … + 3 + 1)) / 2 + 1
= (3^n - 1) / 2 + 1
= (3^n + 1) / 2

これで
引用:

coasmさんの書き込み (2006-08-23 01:11) より:
ｍ個の球があって、その中の１個（以下、「犯人」と呼ぶ）だけ重さが違う。
天秤をｎ回使用して、犯人を突き止める。

情報量の制限から、mの上限が決まる。

(A) 犯人が重いか軽いか指摘する必要がある場合。
・天秤は右に傾く・左に傾く・つりあうの３状態を判別できるので、ｎ回では3**nの状態を判別可能。
・ｍ個の球のどれか一つが重い、または軽いので、判別すべき状態の数は2mである。
したがって、2m≦3**n がmの上限となる。

(B) 犯人が重いか軽いか指摘しなくても良い場合。
実は、(A)と比べてあまり楽にはならない。
手順の途中で一度でも犯人を天秤に乗せた場合、犯人が確定した段階で、それが重かったか軽かったかも確定する。
つまり、「犯人が重いか軽いか指摘しなくても良い」という条件を有利に活用できるのは、犯人を一度も天秤に乗せなかった場合に限られる。
この場合のmの上限は、2m-1≦3**nである。

というわけで、n=3の場合、
(A)なら、13個まで実現できるかもしれない。14個は不可能。
(B)なら、14個まで実現できるかもしれない。15個は不可能。
と繋がりましたね。

ただし、これは「あらかじめ1個の正解玉を持っていた場合」です。
持ってない場合は１減って

(3^n - 1) / 2

になります。これは、coasmさんの論理に「1回目の計測で秤に乗せられる玉の数は偶数でなければならない」という考察が抜けていたからですね。
Ｒ・田中一郎
ぬし
会議室デビュー日: 2005/11/03
投稿数: 979
投稿日時: 2006-08-25 19:24
この問題の回答をコードで書いた場合、IF文を重ねがちですが、きっとメソッドと併用して書くと読みやすいコードが作れることでしょうね。

コード:
１３個の変数がある。
１２個は同じ数値が格納されており、１個だけ違う値が格納されている。
これを 左辺と右辺を比較するだけの単純なIF 文を３回だけ使って、
１つだけ値の違う変数を特定しなさい。

みたいなｗ

逆の場合もありますね。
僕の経験ですが、会社で本を読んでいて、QuickSortロジックを知ったのです。
なるほど〜、と思っていると大量の部品図面を前に頭を抱えている女性社員の姿が目に入りました。
聞けば、製品ごとにまとまって部品図面が送られてきたのだけど、管理上の都合で部品図面番号順に並べ替えてファイリングしなければならないとのこと。
厚さ５ｃｍにもなる図面をどうやって並べ替えれば良いのか頭を抱えているという訳です。
なんてタイムリーでしょう。
早速僕は指サックをはめ、ある適当な番号より小さい番号の図面と、大きい番号の図面に素早く分けました。
そして、小さい番号の図面を、更に同様に分け・・・と繰り返します。
その様を、女性社員は黙ってみています。
しかし、しばらくするとテーブルの上がすぐに分類した図面の束で一杯になりました。
僕は一言呟きました。「ワークエリアが足りないじゃないか・・・」
(すみませんオチです。でも実話です）

そういう経験ってありませんか？
囚人
ぬし
会議室デビュー日: 2005/08/13
投稿数: 1019
投稿日時: 2006-08-25 20:59
引用:

逆の場合もありますね。
僕の経験ですが、会社で本を読んでいて、QuickSortロジックを知ったのです。
なるほど〜、と思っていると大量の部品図面を前に頭を抱えている女性社員の姿が目に入りました。
聞けば、製品ごとにまとまって部品図面が送られてきたのだけど、管理上の都合で部品図面番号順に並べ替えてファイリングしなければならないとのこと。
厚さ５ｃｍにもなる図面をどうやって並べ替えれば良いのか頭を抱えているという訳です。
なんてタイムリーでしょう。
早速僕は指サックをはめ、ある適当な番号より小さい番号の図面と、大きい番号の図面に素早く分けました。
そして、小さい番号の図面を、更に同様に分け・・・と繰り返します。
その様を、女性社員は黙ってみています。
しかし、しばらくするとテーブルの上がすぐに分類した図面の束で一杯になりました。
僕は一言呟きました。「ワークエリアが足りないじゃないか・・・」
(すみませんオチです。でも実話です）

現実世界ではバブルソートしか使った事ですな…。

_________________
囚人@わんくま同盟
囚人のジレンマな日々

[ メッセージ編集済み 編集者: 囚人 編集日時 2006-08-25 21:00 ]
nagise
ぬし
会議室デビュー日: 2006/05/19
投稿数: 1141
投稿日時: 2006-08-27 16:01
引用:

Ｒ・田中一郎さんの書き込み (2006-08-25 19:24) より:
僕の経験ですが、会社で本を読んでいて、QuickSortロジックを知ったのです。
なるほど〜、と思っていると大量の部品図面を前に頭を抱えている女性社員の姿が目に入りました。
聞けば、製品ごとにまとまって部品図面が送られてきたのだけど、管理上の都合で部品図面番号順に並べ替えてファイリングしなければならないとのこと。
厚さ５ｃｍにもなる図面をどうやって並べ替えれば良いのか頭を抱えているという訳です。
なんてタイムリーでしょう。
早速僕は指サックをはめ、ある適当な番号より小さい番号の図面と、大きい番号の図面に素早く分けました。
そして、小さい番号の図面を、更に同様に分け・・・と繰り返します。
その様を、女性社員は黙ってみています。
しかし、しばらくするとテーブルの上がすぐに分類した図面の束で一杯になりました。
僕は一言呟きました。「ワークエリアが足りないじゃないか・・・」
(すみませんオチです。でも実話です）

わはははは。IT屋の友人相手だと
「よ〜し、このカード、クイックソートしちゃうぞ〜」
と言えば即刻突込みが飛んでくるのですけどね
現実世界でクイックソートした場合は遅い、とは直感で分かるところですが
理由をまじめに考察するとちょっと難しい。

端的に言えば、コンピュータ上では処理時間が等価な処理が
現実世界上では等しくないという理由に起因します。
たとえワークエリアがたくさんあってもやはり遅い…。
ただし、複数人いて並列処理可能な場合はバブルソートより
早くなることがあります。
nagise
ぬし
会議室デビュー日: 2006/05/19
投稿数: 1141
投稿日時: 2006-08-27 16:11
引用:

ぼのぼのさんの書き込み (2006-08-25 18:13) より:
うまく纏められました。

3^(n-1) + 3^(n-2) + … + 3 + 2
= 3^(n-1) + 3^(n-2) + … + 3 + 1 + 1
= 2(3^(n-1) + 3^(n-2) + … + 3 + 1) / 2 + 1
= (3-1)(3^(n-1) + 3^(n-2) + … + 3 + 1) / 2 + 1
= ((3^n + 3^(n-1) + … + 3^2 + 3) - (3^(n-1) + 3^(n-2) + … + 3 + 1)) / 2 + 1
= (3^n - 1) / 2 + 1
= (3^n + 1) / 2

お〜。そういえば漸化式ってそんな感じのまとめ方するんだったような…。
遠い記憶が蘇…らない


引用:

引用:

coasmさんの書き込み (2006-08-23 01:11) より:
ｍ個の球があって、その中の１個（以下、「犯人」と呼ぶ）だけ重さが違う。
天秤をｎ回使用して、犯人を突き止める。

情報量の制限から、mの上限が決まる。

(A) 犯人が重いか軽いか指摘する必要がある場合。
・天秤は右に傾く・左に傾く・つりあうの３状態を判別できるので、ｎ回では3**nの状態を判別可能。
・ｍ個の球のどれか一つが重い、または軽いので、判別すべき状態の数は2mである。
したがって、2m≦3**n がmの上限となる。

(B) 犯人が重いか軽いか指摘しなくても良い場合。
実は、(A)と比べてあまり楽にはならない。
手順の途中で一度でも犯人を天秤に乗せた場合、犯人が確定した段階で、それが重かったか軽かったかも確定する。
つまり、「犯人が重いか軽いか指摘しなくても良い」という条件を有利に活用できるのは、犯人を一度も天秤に乗せなかった場合に限られる。
この場合のmの上限は、2m-1≦3**nである。

というわけで、n=3の場合、
(A)なら、13個まで実現できるかもしれない。14個は不可能。
(B)なら、14個まで実現できるかもしれない。15個は不可能。
と繋がりましたね。

ただし、これは「あらかじめ1個の正解玉を持っていた場合」です。
持ってない場合は１減って

(3^n - 1) / 2

になります。これは、coasmさんの論理に「1回目の計測で秤に乗せられる玉の数は偶数でなければならない」という考察が抜けていたからですね。


わちゃさんが答えていますが、情報量的には13個が軽重まで判別できて
1個が軽重不明となり、13.5個分の情報が得られる、ということだったかと思います。

0.5の分が軽重判定を要するという条件では0になり、
不要となれば1となる、というように解釈しています。
«前のページへ 10|11|12|13|14|15|16|17|18|19|20 次のページへ»

スキルアップ／キャリアアップ（JOB@IT）