人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

【誤り訂正】
次の質問:question:1291532081
で思い出したのですが、

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

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

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

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

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

●質問者: くろょ
●カテゴリ:学習・教育 科学・統計資料
✍キーワード:question: いるか 情報理論 理論 符号
○ 状態 :終了
└ 回答数 : 8/8件

▽最新の回答へ

1 ● Riomario
●34ポイント

解けますよ??

天秤の左側が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枚なので説明しません

◎質問者からの返答

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

「見つからなかったら」

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

???

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


2 ● 勇者よっしー
●33ポイント

普通に解けますよね?

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

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

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

---

という事で、

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

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

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

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

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

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

◎質問者からの返答

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

「見つからなかったら」

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


3 ● sushi0
●34ポイント ベストアンサー

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

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

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



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

◎質問者からの返答

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

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


4 ● 勇者よっしー
●1ポイント

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

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

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

そういう事です。

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

◎質問者からの返答

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


5 ● ryou1000
●10ポイント

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

◎質問者からの返答

それはそうです。


1-5件表示/8件
4.前の5件|次5件6.
関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ