ログインしてさらにmixiを楽しもう

コメントを投稿して情報交換!
更新通知を受け取って、最新情報をゲット!

ロジカル・シンキングコミュの論理パズル

  • mixiチェック
  • このエントリーをはてなブックマークに追加
論理パズル問題をみんなで
出し合いましょう♪

旅行者がやってきた異国の村には、
正直族とウソツキ族が住んでいました。
旅行者は飲料水が欲しかったのですが、
目の前のオケに入っている水が
飲めるものかどうかわかりません。

ではたった一回質問するだけで
飲めるかどうかを判断できる質問を
考えてください。
(この問題は知ってる人多いかな?)

コメント(625)

(3^n-1)/2

この式で不足している要素は、これです。

「nは2以上の自然数」

1では答えが1になり、確かに1枚しかなければそれがターゲットに決まってるんですが、しかし天秤が使えませんから。nは天秤を使う回数なので、この条件は必須となります。


ですから同じく、

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

の場合も、

「nは3以上の自然数」

という条件が必要です。



ちなみに私とワイネフさんの式は微妙に違いますが、同じものです。私は総当たりの理論からアプローチしたのではなく、解法からアプローチしたので、こう記述しておくほうが自分で状況を飲み込みやすいんです。
>>[587]

ログの彼方ですが、ワイネフさんが5回41枚を言い当てた時、解き方を考えるのは手間なのでまた後で、みたいなコメント残されてましたね。
解き方のメカニズムが一般解てなくてもまだはっきりしてない段階で、先に最大値だけ的中させるのは、かっこ良かったです。私から見ると神業です。

総当たり表の意味も鴫野と妥当性も、あちこちつっかえながら自分なりの解法を見つけてから、やっと何が書いてあるかわかりました。

今なら自信をもって、ワイネフさんのここまでの説明を、見た瞬間わかると即答できると思います。
鴫野って、なんだ!?

誤植です。式の、です。
失礼しました。
>>[589] ID 7198891

コメントのなかで、気が付いたら、訂正するわな、普通は

つまり、それ、ほのめかしの可能性があるよな

だれかの住所とかを、知ってるぞ、みたいな
その地名はわしも知ってるから、わしに向かってのほのめかしの可能性は大や(爆

めんどくさいこと言うてんと
さっさと、来いよ(笑
>>[577]

4回15枚の反例を少し考えてみたんだけど・・・

釣り合いか左右に傾くかの3つの状態に
一対一に固定的に対応する3色ランプで
測定結果を表示する電子天秤を使って
15枚の同種コイン中に1枚だけ混ざっている偽コインを
4回の測定で判別する方法

ランプの色は赤R、緑G、青B
コインはabcdefghijklmnoとする


一回目の測定

左  右  外
abcd efgh ijklmno

測定値 R
判定結果なし


二回目の測定(過去の測定値はR)

左  右  外
efgh abcd ijklmno

測定値 G
判定結果 Bはつり合いの意味とわかり、偽コインはabcdefghの8枚の中にあり、ijklmnoの7枚は本物

測定値 R
判定結果 Rはつり合いの意味と分かり、偽コインはijklmnoの7 枚の中にあり、abcdefghの8枚は本物


(以下、この測定の続きで8枚に偽コインが絞られた場合)

三回目の測定(過去の測定値はRG)

左  右  外
abef cgTT dhijklmno

測定値 G
判定結果 偽コインはcefの3枚の中にある

測定値 R
判定結果 偽コインはabgの3枚の中にある

測定値 B(この場合はすでにBがつり合いの意味だと分かっている)
判定結果 偽コインはdhの2枚の中にある


(cefの中に偽コインがある場合)

四回目の測定(過去の測定はRGG)

左 右  外
f e cdhijklmno

測定値 G 偽コインはf
測定値 R 偽コインはe
測定値 B 偽コインはc
>>[577]

捕捉します


三回目の測定(過去の測定値はRG)

左  右  外
abef cgTT dhijklmno



ここでcgTT はTが本物コインという意味です

つまり、右の更に4枚載せるが2枚はdhijklmnoのどれかを使うってことです
捕捉は誤字です

誤植ではありませんが、補足のつもりでしたw
>>[577]


ごめんなさい、何度も

四回目を以下のように修正します

  ↓

四回目の測定(過去の測定はRGG)

左 右  外
f   e   cdhijklmno

測定値 G 偽コインはf
測定値 R 偽コインはe
測定値 B 偽コインはc
こういう風に、コメントしたあとでミスに気が付いて、修正するものであって、
コメント書いてる最中に誤字や変換ミスに気が付いたら、正してから投稿するよね

この順序が違うだけで

特定のターゲットにほのめかしもできるんだね(爆

暗号かなwww


鴫野はわたしはよく知ってる地名なんですけど、みなさんは知らなくてむしろ普通のこと
ほのめかしとか、わたしがなに言ってるかわからないかもしれませんが
ご参考までにと思いまして


こそこそ調べて、ほのめかしとかやってるとしたら

まあ、きもいですわな

プロバイダー経由の情報漏洩なんでしょうかねえ
ゴミクシーは、過疎って当然でしょう
>>[591]

ちょっと待てや!!!

本件とまったく関係ないところから人格攻撃するのは、大嫌いなんだよ!!だから、私が自分から意図的にそれをやることは、絶対にない!!!誓って良い!

なに言われてるかまったく見に覚えがない、腹のそこから意味不明。

文脈から想像するに、あなたの現住所になにかしら関係のある単語がひっかかっていた、ってことか。
誓って言う。正真正銘、まったくのタップミス、誤植だ。それが地名だというのも、まったく知らなかった。

完全なあなたの勘違いだ!
見損なうな!!
ふざっけろや、こいつ。
腹立つ。あったまきた。
なんらかのかたちでまともに謝罪があれば、不問にして598、599、600は削除して全部忘れてやる。
>>[600]

忘れるなよ(笑


おぼえとけ、ずっと
>>[592]

一手目、間違い。

7枚を残り2回の移動で特定はできない。

8枚を3回の移動で特と総当たりの枝がひとつ余る。


1秒でつぶせるよ、こんな解答。
>>[601]

そのうち忘れるよ。
くだらん。
一回目の置き方もいろいろあね

左皿 右皿 外
abcde fghij klmno

左の皿に載せたコインには+を、右のには−、外のものには±を
各コイン固有に割り当てたアルファベットなどの記号の左側から左に向かって符号を重ねていきます
測定値、符号、どちらも3種類あります

この置き方なら、符号は

+a,+b,+c,+d,+e,-f,-g,-h,-i,-j,±k,±l,±m,±n,±o


二回目の置き方の例

 左       右       外
a,b,f,g,k    c,d,h,i,m    e,j,l,n,o

+a,+b,-f,-g,±k +c,+d,-h,-i,±m  +e,-j,±l,±n,±o

(このようにして混ぜる考えで15枚4回の解決を目指す)


二回目の測定値 R
偽の可能性があるコインは

    7枚で、abhino(++a,++b,--h,--i,±±l,±±n,±±o)完全な未知コインは3枚

二回目の測定値 G,B
偽の可能性があるコインは

    8枚で、cdefgikm(-+c,-+d,±+e,+-f,+-g,±-j,+±k,-±m)完全な未知コインは2枚


過去二回の測定値はRGで、三回目では偽コインは8枚以下に絞れる
本物コインも使えるし
7枚8枚を上記のように混ぜ合わすには他にもいろんな可能性がありそうです


これは単なるメモ書きのようなものです
解答ではありませんのであしからず

反例さがしです



上記の具体例のRG(2回で8枚に絞られた場合)の続き

三回目の置き方を以下とする

     左        右            外
-+c,+-f,±-j,+±m -+d,+-g,±+e,Ta  -±k,Tb,Th,Ti,Tl,Tn,To


三回目の測定値が RG→Gの場合 

 +-+c,++-f,+±-j,+-±m  --+d,-+-g,-±+e  ±+±k,Ta,Tb,Th,Ti,Tl,Tn,To

偽の可能性があるコインは  f,d 

※符号の順列に一致する移動履歴と、RGBの色変化と、の関係より偽コインの可能性があるコインは判別できそうです
この場合は2回目以降の符号が重複いているコイン++-fと--+dがそうです
つまり、左から連続して同じ符号になっているものです


測定値 RG→Rの場合

偽の可能性があるコインは  c,g,k

左右外の3箇所の間で移動して元に戻っているコインが偽の可能性を持つ
符号はサンドイッチ型の+-+など

考え方としては、条件によって、ランプの色の意味がつりあいかどうかがわかることがある
これを3回目以降でうまく利用できないかということ

例えば

過去にcとgが入れ替わってもランプは同色だったので、kが偽コインでないならBがつり合いだとか
過去の測定における左c、右k、外gのときの色(測定値)を現在のものと比較して偽コインを特定できないかなど



測定値 B

偽の可能性があるコイン  e,j,m

この場合は符号が全部食い違うコインであり、符号のパターンはランプパターンの順列の逆順に一致する
測定3回までは左からの順列か、右からの順列かの区別はあまり意味ないですけどね

情報をうまく活用すれば、残り1回で3枚以下に限定されて、複数回測定の一連の流れにみられるつり合いと色の関係性などから情報が得られて、あと1回でできそうです
>>[605]

めいっぱいシンプルにしてみます。

ABC3枚のコインと、本物コインRを使います。

左にABC全部乗せて、右にRRR本物コインで数を合わせます。
(ABC,RRR) このときの反応がα

今度は右にABC全部乗せて、左にRRR本物コインで数を合わせます。
(RRR,ABC) このときの反応がβ

さらに、全部外に置きます。天秤には本物コインだけ乗せて動かします。
(RRR,RRR)ABC このときの反応がΓ

最後に、Aをαのときの位置に、Bをβのときの位置に、CをΓのときの位置に置きます。
(A,B)C

このとき、天秤の反応がαなら、Aがターゲット。
反応がβなら、Bがターゲット。
反応がΓなら、Cがターゲットです。

ここでは4回の試行をしていますが、実践ではαとβを試行してΓは省略できます。
たとえば、Aがターゲットだとして、上記のて手順を追いかけていくと、どうやっても必ず最後がαになることが簡単にわかります。
同じくBがターゲットだとして追いかけていっても、必ず最後がβになります。
Γも同じく。

はじめの3回の試行でAがどこにあろうと、結果は同じくなります。
一枚一枚に対してこういう特定のしかたができるので、グループ化の必要がなく、こういう解き方ができるわけで。

( ABCDE , FGHIJ ) KLMN →α

 ↓

( BDEFL , ACHMN ) GIJK →β(仮)

 ↓

( BCMJ , AFLD ) EGHINK →Γ(仮)

 ↓

( LM , AJ ) BCDEFGHIKN →α(仮)

ターゲットはJ

一回目と二回目で移動していないのが5枚あります。
二回目と三回目では、その5枚を除いて、3枚ずつセットでαだったときの位置、βだったときの位置、Γになるはずの位置に移動しています。
三回目と四回目では、Γになるはずの位置に移動したグループを、一枚ずつαだったときの位置、βだったときの位置、Γだったときの位置に移動しています。

天秤の暗号は、どれがどの状態を示すのか最後までわかりません。3回目の試行で3枚にしぼっていますが、その三枚が左右にばらけているからです。この時点ではターゲットが右にあるのか左にあるのかわからず、Γがどちらの状態を示しているのかわかりません。
最後にターゲットが確定すると、さかのぼって解読はできますが。暗号は解けなくてもターゲットは特定できる、というのはこいうことです。
天秤の傾きの状態をRGBの3色で表示し
その傾きと色の対応は固定されているが
つりあう、どっちかに傾く、の意味とRGBの対応はわかていないような
ランプ型電子天秤があるとします

重さの情報がわかっている複数のコインを、複数回測定するなら
逆に天秤の色の意味を逆算することができます

例えば同じ重さの2つのコインを測ったときの色はつり合いの色です
コインにも天秤にも重さの違いの情報が何もなければ、この場合は、何度測定を繰り返しても色の意味はわかりません


ところで、
同じ重さの複数の本物コインと、見分けのつかない重さの異なる偽コインが1枚あって

全部で偶数個という場合

コインを2つの同数のグループABに分けたとき、一方に必ず偽物が含まれます
そうすると、左右の皿に対してABをBAにして2回の測定を行えば、そのときに表示された2種類の色のどちらでもでない色が
つり合いの色だと判明します

全部で奇数個の場合

一個を除外して、偶数個のときと同じことをします
たまたま、除外したコインが偽コインだったとしたら
左右の皿にABの順に並べて測ってもBAにして測っても天秤の色は変わらない
それしか可能性がなく、その色がつり合いです
除外したコインが本物だったら
左右を入れ替えて2回の測定をすると今度は必ず色が変化し、その色以外がつり合いであることがわかります
逆に言うと、左右を入れ替える2回の測定で
色が変わればそれ以外がつり合いの色であり
色が変わらなければそれがつり合いの色です

従ってランプ型電子天秤で、同じ重さの複数の本物コインに見分けのつかない重さの異なる偽コインが1枚混じっているときは、2回の測定でつりあいの色がわかってしまいます

まあ、あれです
重さの情報がわかっている複数のコインを、複数回測定するなら
逆に天秤の色の意味を逆算することができるなんてあたりまえですね

測定開始時点で、コインの重さの情報が不十分でも、足りない情報を、測定によって補填する
すなわち新たな情報を得ることで、偽コインを特定したり、ランプ型電子天秤のつり合いの色を知ることができる可能性があります

つり合いの色がどこかで判明したら、それはもう、ランプ型天秤の当初の前提が崩れています
別の天秤で測っているようなものです
重いか軽いかで色が変動し、つり合うときの色はわかっている天秤です
これはモンティーホール問題で途中で当たりでない扉をあけて見せるようなものですね
別解、挙げておきます。
はじめ二回でααのバージョン。

( ABC , DEF ) GHIJKLMN →α

( CDIK , FGHJ ) ABELMN → α

( ABM , CFL ) DEGHIJKN → β

( AC , LM ) BDEFGHIJKN → γ

一回目と二回目で同じ位置にあり、二回目と三回目で移動したコインのうち、αともβとも違う位置に置いたのはMです。
>>[613]

nを測定回数として、最大の判別可能枚数は


  Σ3^(n-2)+2  (Σはn=3からnまでの和)


この式の導き方は

n=4   5    6   ・・・

RBRR
RBRG
RBRB
RBGR
RBGG  3^3   3^4  ・・・
RBGB
RBBR
RBBG
RBBB

RRRR  2     2   ・・・
RRRB
                 ・
                 ・
                 ・

           3^1

      3^1   3^2   ・・・

RRBR
RRBG  3^2   3^3   ・・・
RRBB

14    41   122  ・・・



>(3^(n-1)+1)/2

122までは一致してるようです
ご参考までにと思いまして


ところで、n回の最大枚数は、つりあいの色が途中で判明しなければ、この式の値を超えられませんよね
4回ではいまのところ反例は思い付きません

つりあいの色がわかる理屈は、数理というより測定器の持つ性質というか道理だと思われます
反例を探したくても5回では41枚+αになりますから
反例どころか41枚の解法自体がわたしにはすでに大変です
>>[617]

気が付きませんでしたが、そうですね
おっしゃるとおりです
>>[619]

ランプ型電子天秤ってのはおもしろいですね
ありがとうどざいます

偽コインは、ある特定の測定手順(一回測定ごとの”一連の”グループ分け)と、そのときの測定値のパターンによって判別できる
測定手順のことを言うと、一枚の偽コインの判別メカニズムがより実感できるかもしれません

(以下は偽コイン判別のメカニズムを説明する目的の例ですから詳細は気にしてません)

 左皿   右皿  外
1回目 abcde fghij  klmno
2回目 bcfgklm hijdeno   a
3回目 bcd          hij
4回目 bj     ch      i

1回目の測定値がRとします

2回目で測定値 RR すなわち色が変わらないとき
動かなかったコインが偽コイン候補であり、動いたものは本物です

bchij(adefgklmno)・・・このように本物を括弧でくくって書いてます

3回目でRRRならbc(adefghijklmno)
4回目でRRRRならb、RRRBならcが偽コインです

3回目でRRBならhij(abcdefgklmno)
このとき、hijは外に移動しており、それ以外に偽コイン候補はすべて皿にあって、動いていません
それでも色が変わっていることから、bcdは本物であり、Bはつりあいの色です
4回目でRRBRならh、RRBBならi、RRBGならが偽コインです


偽コインが特定できるような測定手順が存在しており、測定手順をうまく調整して、ある測定回数では何枚まで偽コインが特定できるか
その際、ランプの識別パターンの場合の数が判別可能なコイン枚数の上限ということですよね

コインの経路の自由度は3^nですから、ランプの色の意味が知らされてない電子天秤の3色パターンよりも広いですから、つり合いの色を知ろうとする方針で判別最大枚数を増やそうと考えてみたわけです
ランプの意味がひとつわかることで、ランプパターンの自由度が広くならないかどうか
あと1個多く判別できればいいんですけど、それが、ちょと考えただけでは思いつきませんでした
問題文、コピーしておきます。

***

ここに★枚のコインと一つの天秤があります。
★枚の中に一枚だけ重さが異なるコインが含まれていますが、そのコインが他のに比べて重いか軽いかはわかりません。
天秤を使って重さが異なるコインを探して欲しいのですが・・・

この天秤、右に重いのを置く、左に重いのを置く、左右が等しい重さになるように置くという3通りの置き方と、右に傾く、左に傾く、釣り合うの3通りの結果が入れ換わっている可能性があります。(入れ替わってない可能性もあるので組み合わせは6通り)
そして両側の皿に必ず同数のコインを載せないと作動しません(0個0個では載せていないため作動しない)

では、4回天秤を使って確実に重さが異なるコインを特定出来る最大の枚数は何枚でしょうか?

***

以上のような文章でした。
よく洗練された合理的な文章ではありませんが、なにを言ってるのか意味は読み取れる普通の日本語だと思います。

どの部分の意味がわからないのでしょう?
天秤の傾きの状態と、問題のコインが含まれる位置の対応は、6通り考えられて、どの状態だかわかりません。コインが思い場合と軽い場合とで動きは逆転するので、観測者としては倍の12通りあると考えるべきなのかもしれません。

で、ここで引っ掛かっている印象を受けますが。

解法に従うと、ターゲットコインを特定するまで、天秤の暗号がどのパターンになっているか判明しないまま解くことができます。だから、ターゲットコインの位置と天秤の傾きの相関々係は、問題を解く上で無視できます。

問題文としてはこの部分はミスリードをさそう余剰要素でもあるのですが、不思議な天秤を使って偽コインを見つける、というシチュエーションを説明するには妥当な部分とも思います。
与えられたシチュエーションから、問題を解くために必要な情報を拾うことができるかどうか、という所から解答は始まっています。

それでも、必要な情報を読解できない、ということなら、ここまでログは延びてきて他の人が情報を読み解き、整理して一般化しているのですから、それを参考にするのも手だと思います。

私も間違った読解から始まり、他の人が解き進むのを参考にしたり、解法例を教えてもらったりしながら、誤読を修正し理解を進めてきました。

それでも理解を進められない、最初の問題文の読解から先に進めないなら、解答は「解なし」と主張するのでも良いと思います。それが正解なのか不正解なのか、それはそれでじっくり考えてみるなり、それでやめておくなり、自由だと思います。

ログインすると、残り597件のコメントが見れるよ

mixiユーザー
ログインしてコメントしよう!

ロジカル・シンキング 更新情報

ロジカル・シンキングのメンバーはこんなコミュニティにも参加しています

星印の数は、共通して参加しているメンバーが多いほど増えます。

人気コミュニティランキング