【誤り訂正】

次の質問:question:1291532081
で思い出したのですが、

「1枚だけ偽物が混じった12枚の金貨の中から、天秤を3回だけ使って偽金貨を特定しなさい。」
という、わりと有名な問題があります。
この問題では、金貨の順列は24通りであり、それを天秤の傾きの組み合わせである27通りの中から判定できる事がなんとなくわかります。
また、この問題が情報理論における誤り訂正符号の問題に置換できる事も知られています。

では、金貨の枚数を、(12枚ではなく)13枚にした問題:
「1枚だけ偽物が混じった13枚の金貨の中から、天秤を3回だけ使って偽金貨を特定しなさい。」
という問題についてはどうですか:

天秤の傾きの組み合わせは27通りであり、金貨の順列は26通りですから、一見解けそうに見えるのですが、いろいろやってみても、どうも解けなさそうです。

そこで質問なのですが、
「この問題を解くために必要な理論的要件」と
「それを、この問題が満たしているかどうか」
について教えてください。

※偽金貨は本物と重さが違うという事以外は不明とします。

回答の条件
  • 1人2回まで
  • 登録:2010/12/05 21:09:24
  • 終了:2010/12/10 00:21:56

ベストアンサー

id:sushi0 No.3

sushi0回答回数66ベストアンサー獲得回数132010/12/05 23:28:43

ポイント34pt

いろいろな解き方がありますが、平衡三進法での解法が好きです。

ただし、n回の計量で偽物コインを発見し、重いのか軽いのかを決定することが出来るのは、(3n-3)/2枚までという条件があるため、

13枚の場合には偽物のコインの特定は可能ですが、偽物コインが本物よりも重いのか軽いのか決定できない場合があります(1/13の確率で)。



下のサイトで詳しく解説されていますのでご参照ください。

id:kuro-yo

回答ありがとうございます。

平衡三進法を使うと、天秤の使用回数と偽物を発見できる金貨の枚数の関係が明確に示されるわけですね。

2010/12/06 12:10:59

その他の回答(7件)

id:Riomario No.1

Riomario回答回数1ベストアンサー獲得回数02010/12/05 21:53:57

ポイント34pt

解けますよ??

天秤の左側がA、天秤の右側がB、

天秤の外がCだとして、

1回目-A:4 B:4 C:5

2回目(1回目でAかBのどちらが重かった場合)(重い方をだして)-A:1 B:1 C:2

2回目(1回目でAとBがつりあった場合)(Cを出して)-A:2 B:2 C:1

3回目-もう2枚か1枚なので説明しません

id:kuro-yo

13枚のうち12枚について、12枚の時と同じ方法で偽物を探し、

「見つからなかったら」

13枚目が偽物、というアルゴリズムと考えて良いですか?

~~~

何故だかIDが消滅してる…

2010/12/10 00:18:15
id:yossiy7 No.2

勇者よっしー回答回数778ベストアンサー獲得回数962010/12/05 23:15:03

ポイント33pt

普通に解けますよね?

12枚の時と全く同じ方法で解けます。

4枚と4枚で比較し、どちらかが重かったら、12枚の時と全く同じ方法で解きます。

同じ重さだったら、残りの5枚中、2枚と2枚で比較。同じだったら残り1が偽者だし、違った場合も12枚と同じ方法で解きます。

---

という事で、

「この問題を解くために必要な理論的要件」

上記どおりです。解法が存在している。

具体的に言えば、12枚の時でも「計測しないという事が計測の1部となっている」という解法を使っているので、増えた1枚に対してその解法を当てはめる、それだけです。

「それを、この問題が満たしているかどうか」

上記どおり、全部のパターンで解けますので、満たしているでしょう。

ちょっと数学的な言い方ではありませんが……(そういうのを書こうとしてすっかり忘れているのに気がつきました……)

id:kuro-yo

13枚のうち12枚について、12枚の時と同じ方法で偽物を探し、

「見つからなかったら」

13枚目が偽物、というアルゴリズムと考えて良いですか?

2010/12/06 12:08:31
id:sushi0 No.3

sushi0回答回数66ベストアンサー獲得回数132010/12/05 23:28:43ここでベストアンサー

ポイント34pt

いろいろな解き方がありますが、平衡三進法での解法が好きです。

ただし、n回の計量で偽物コインを発見し、重いのか軽いのかを決定することが出来るのは、(3n-3)/2枚までという条件があるため、

13枚の場合には偽物のコインの特定は可能ですが、偽物コインが本物よりも重いのか軽いのか決定できない場合があります(1/13の確率で)。



下のサイトで詳しく解説されていますのでご参照ください。

id:kuro-yo

回答ありがとうございます。

平衡三進法を使うと、天秤の使用回数と偽物を発見できる金貨の枚数の関係が明確に示されるわけですね。

2010/12/06 12:10:59
id:yossiy7 No.4

勇者よっしー回答回数778ベストアンサー獲得回数962010/12/06 15:20:32

ポイント1pt

>13枚のうち12枚について、12枚の時と同じ方法で偽物を探し、

>「見つからなかったら」

>13枚目が偽物、というアルゴリズムと考えて良いですか?

そういう事です。

ただ、動きをシミュレートしていただければ判りますが、12枚の時より少ない回数で判るケースもあります。

id:kuro-yo

何故にコメントでなく回答…

2010/12/06 22:07:52
id:ryou1000 No.5

ryou1000回答回数6ベストアンサー獲得回数02010/12/06 17:51:29

ポイント10pt

重さや形を全て測定すれば出来ると思います。

id:kuro-yo

それはそうです。

2010/12/06 22:09:40
id:fhty5vu8--0i0g No.6

CO回答回数7ベストアンサー獲得回数02010/12/07 17:59:49

ん・・

私 バカですね

id:adlib No.7

adlib回答回数1859ベストアンサー獲得回数1092010/12/08 03:57:49

ポイント20pt

 

 真贋の条件 ~ 金貨より重い銅貨は存在しない ~

 

1)1枚を余し、左6枚と右6枚に分けて、重い方を金貨とみなす。

2)軽い方の6枚を、左3枚と右3枚に分けて、重い方を金貨とみなす。

3)軽い方の3枚から、左1枚と右1枚に分け、重い方を金貨とみなす。

 

 13枚あって、一回の計測を4枚以下に制限すると、手順が増える。

 

1)5枚を余して、左4枚と右4枚に分け、重い方を金貨とみなす。

2)軽い方の4枚と、5枚のうち任意の4枚と比べる。

3)軽い方の4枚を、左右2枚づつに分ける。

4)軽い方の2枚を、左右1枚づつに分け、重い方を金貨とみなす。

 

 前提の誤謬 ~ 偽金貨は(略)重いか軽いかも不明 ~

http://www.coguchi.com/search-date/genso.html

 元素記号および比重表

 

 貴金属は、同じ容積で比重の高いほど価値があり、偽金貨が本物より

重いことはあり得ない。銅貨を金で偽造しても、ワリが合わないからだ。

 

 まれに収集家が、比重にかかわらず希少価値を尊重することもあるが、

それでも軽い方を“偽金貨”と呼ぶべきである。

 

 かりに「理論上の比喩」であるなら、常識に即して、誤解を生まない

「適切な比喩」を選ぶべきである。

 

 左右同じ重さなら、余した方に偽貨が存在するとは限らない。

 全13枚のうち、12枚が偽貨である可能性もあるからだ。

 

── 江戸時代の貨幣の金および銀の含有率は、極秘事項とされ、民間

での貨幣の分析は厳禁とされた。(Wikipedia;慶長小判)

 

── 悪貨は良貨を駆逐する(グレシャムの法則)

http://q.hatena.ne.jp/1236264597#c144750

 

id:kuro-yo

純金で金貨を作ると、やわらかすぎて貨幣としては使い物にならないと思います。

~~~

>adlib 2010-12-09 01:27:51

>金の比率(含有率)が50~85%以上あれば、金貨と称します。

>金の比重(19.32g/cm3)は、純度にかかわらず一定不変です。

>銀(10.49g/cm3)、銅(8.95g/cm3)に比べれば一目瞭然ですね。

いや、ただの冗談ですので。

2010/12/10 00:17:06
id:mahhi11 No.8

TAKANO回答回数2ベストアンサー獲得回数02010/12/08 20:17:47

え~ マジでわからん

  • id:karuishi
    うーんダメかな。
    偽物が「重い」か「軽い」か判っていればいいみたいですけど。
    http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1143983131
  • id:kuro-yo
    再掲しますが、
    『※偽金貨は本物と重さが違うという事以外は不明とします。』
    したがって、重いか軽いかも不明ですので、どちらか一方のみを前提とした解法は示さないでください。
  • id:kuro-yo
    回答1と回答2のお二方に、今朝、誤解されてると返信してしまいましたが、私の方が誤解していました。すみません。一旦精査してから返信しなおします。
  • id:kuro-yo
    天秤の27通りの傾きの組み合わせから、25通りの情報しか得られない理由が知りたいです。
    また、問題を少し変えて「偽物の有無」までも条件に含めた場合に、12枚(25通り)なら解けるのに13枚(27通り)なら解けない(ここまでに示された解法では解けないですよね?)理由が知りたいです。
  • id:kuro-yo
    余談ですが、14枚目の「本物」があれば、解ける事はわかっています。
  • id:kuro-yo
    プロフィールの「回答回数」というのは、回答した質問の個数ではなく、一つの質問に複数回回答すれば、それも全部数えた回数です。

    もし、同じような内容の回答を一つの質問でした場合、それぞれの回答にポイントを分配してしまうと、1回当たりの受け取りポイントが減る事になります。もしそれぞれの回答に同じようにポイントを配分すると、余計にポイントを払う事になり、他の回答に対して不公平です。かと言って、一方を0ポイントにすると、今度は回答者の受け取り率が減ってしまう事になります。

    …この仕様は、以前からどうかと思っていましたが、やっぱり納得行きませんので、アイディアに出す事にします。
    http://i.hatena.ne.jp/idea/28804

    それまでは、回答者の側で対処してもらうしか仕方ありません
  • id:sushi0
    27通りの組み合わせのうち、1通りは全部つり合っている場合なので、
    偽物の重さのわからないときには判定できない状態ですね
  • id:yossiy7
    問答形式のコメントをした場合、回答に再び記入するのは、普通に質問サイトのルールに沿ったやりとりだと考えます。そのコメントが「回答」である限り、です。
    今回は受け取り率を減らすなり、ポイントを他の方の半分にするなり、どちらの対処にしていただいても結構です。
    私自身は、そこはこだわりません。
  • id:kuro-yo
    いや、私が拘り過ぎなんですね。お騒がせしました。
    私は、与えられたシステムがあれば、そのシステム上での最良のやり方を考えずにはいられない性質で、思い切りが足りません。
  • id:kuro-yo
    今日、いろいろ考えていたら、なんか自己解決したような気がしましたので、終了します。
  • id:adlib
     
    >純金で金貨を作ると、やわらかすぎて貨幣としては使い物にならない<
     
     金の比率(含有率)が50~85%以上あれば、金貨と称します。
     金の比重(19.32g/cm3)は、純度にかかわらず一定不変です。
     銀(10.49g/cm3)、銅(8.95g/cm3)に比べれば一目瞭然ですね。
     
  • id:kuro-yo
    では、白金を使って(金より高価(笑))、
    いや、タングステンで(やっぱり高価)、
    いや、ウラニウムで(死ぬ)

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません