贋金判定問題の復讐



  • ■前置き
    有名な問題を少々捻ってあります。御賞味ください。
    まず例題とその答えを示します。それを踏まえて?捻った問題にチャレンジのほど御願いいたします。

    ■例題
    警察が金貨偽造団のアジトを手入れし,金貨がたくさん入った袋を 5 袋押収した。袋の中身は,全部が贋物であるか,全部が本物であるか,どちらかだとわかっている。本物の金貨 1 枚は 10 グラムであり,贋物はそれより 0.1 グラム少ない 9.9 グラムである。
    0.1 グラム単位で 1 キログラムまで計れる精密な量りで,ただ 1 回計量することにより,各袋の金貨の真贋をすべて決定せよ。

    ■例題解答例
    2 進法を利用すると良い。
    便宜上,袋に 0 から 4 までの番号を振る。0,1,2,3,4 番の袋からそれぞれ金貨を 1,2,4, 8,16 枚を取り出し,それらをまとめて計量する。全部本物なら 310 グラムになるはずだが,贋金が混じっているとそれより軽くなるので,その程度でどの袋が偽であるかがわかる。
    たとえば 308.9 グラムだったとすると,本来より 1.1 グラム軽いので贋金が 11 枚混じっている。11 は 2 進法で 01011 だから,0 番,1 番,3 番は贋物の袋で,2 番,5 番は本物の袋だと判定できる。

    ■捻った問題
    警察が金貨偽造団のアジトを手入れし,金貨が 13 枚づつ入った袋を 5 袋押収した。袋の中身は,全部が贋物であるか,全部が本物であるか,どちらかだとわかっている。本物の金貨 1 枚は 10 グラムであり,贋物はそれより 0.1 グラム少ない 9.9 グラムである。
    0.1 グラム単位で 1 キログラムまで計れる精密な量りで,ただ 1 回計量することにより,各袋の金貨の真贋をすべて決定せよ。

    ■回答解禁
    隠し機能を使うことにしますが、それでも回答解禁日時は11月27日午後9時とします。

    ■後記
    魔法のシャボン玉の出題に相変わらず行き詰まっております。
    しかし、マーモセットさんがそろそろおなかがすいた頃と存じまして、出題してみました。



  • ##煙幕を張るために失敗例を提示

    0 1 2 4 8
    10 ゲタをはかせて
    10 11 12 14 18
    だとどうかな?
    検算。

    0
    10 11 12 14 18
    21 22 24 28
    23 25 29
    26 30
    32
    33
    39 35
    42 40 36
    44 43 41 37
    55 54 53 51 47
    65

    ありゃあ\(゜ロ\)(/ロ゜)/
    よく考えたら失敗じゃー

    検算するまでもなく、そもそも
    10 11 12 14 18
    の時点で駄目じゃー。18は13よりでかいんじゃー



  • 先週末に検査のために病院に行き、長い待ち時間の暇つぶしに今回の問題を持っていきました。
    検査着姿で点滴をしながら、しかめっ面でぎっしり数値を書きこんだ紙と睨めっこをしているところを病院スタッフに見られ、医師にまで伝わり
    「すごく難しい勉強をしているんですね。」
    と勘違いされたようでした。
    よほど険しい顔をして考えていたのでしょう。
    その時はパズルの答えにはまだ到達できませんでしたが、検査結果は当日分かる範囲では異常なしでした。

    今回は、行き当たりばったりの回答です

    私はいつもパズルを考える時には論理的に考えるより先に、まずは片っ端から試してみることから始めます。
    そうすることで、規則性や法則が見えてくることがあるからです。

    今回の手順は以下の通りです
    ・ 白丸は選んだ値
    ・ 黒丸は白丸を足すことで出来るために選べない値
    ・ 【】は重複が起こるために選べない値です。
    最初は、小さい値からやってみます。
    それぞれの値を足すことで出来る値に重複がないようにするためには例題にある2進法を利用した①②④⑧⑯にするしかできません。
    すると、16が13を超えてしまいます。
    では、1をやめて、小さい値から順番に、黒丸をスキップして選んでいきます。

    ②③④❺❻❼⑧❾❿⓫⓬⓭・・・・

    やはり、13を超えてしまいます。

    2をやめてみると

    ①③❹⑤❻⑦❽

    8が1,7と3,5で重複するので7はダメ
    では、もう1度

    ①③❹⑤❻【7】❽❾⑩⓫⑫

    すると、13が1,12と3,10の2通り作れるので12もダメ

    ①③❹⑤❻【7】❽❾⑩⓫【12】⓭

    やはり13以内では作れません。

    このように、いくつか試しましたが、小さいものから埋めていくのは無理そうなので、大きい値から試していくことに方針転換しました。
    小さい値から選ぶ時は、すでに選ばれた値を足した時に出来ない値のものを順番に選んでいきましたが、大きい値から選ぶ場合は、先に選ばれた値同士を足した時に同じ答え(重複)が出来ないように選んでいきます。

    ⑬⑫⑪【10】⑨【8】【7】⑥

    おや、なんとなくうまくいった感じです。

    回答
    5つの袋からそれぞれ13枚、12枚、11枚、9枚、6枚金貨を取り出し、それらをまとめて計量する。

    他にもできるかは、他の方に譲ります。


  • Global Moderator

    @Hannibal さん

    この問題は、試行錯誤して不可能問題ではないかと思ったので、下をやって、解が出てきたときには驚きました:

    参考

    Select[{#, Length@DeleteDuplicates[Total /@ Subsets[#]]} & /@
    Subsets[Range[13], {5}], #[[2]] == 2^5 &]

    どういう理屈なんでしょう。直観的には無理っぽいが解のある、面白い問題ですね。


  • Global Moderator

    @マーモセット さん

    Re: 今回は、行き当たりばったりの回答です

    このように、いくつか試しましたが、小さいものから埋めていくのは無理そうなので、大きい値から試していくことに方針転換しました。

    流石です。私も小さい方から埋めるという試行錯誤をしました。しかしうまくいかず、その時点で無理っぽいと思ってしまいました。大きい値から行けるというのは、(私の)直観に反していて驚きでした。



  • @ソム さん
    ものすご~く低レベルの質問で恥ずかしいのですが
    時々、プログラムのような書き込みを見かけますが
    これはどうすると答えが出てくるのでしょうか?
    何かのソフト(アプリ?)を使うとできるんですか?
    どこかからダウンロードするとできるようになりますか?


  • Global Moderator

    @マーモセット さん

    何かのソフト(アプリ?)を使うとできるんですか?

    失礼しました。別記事「ラズベリー・パイを使って、Mathematica で遊ぼう!」に説明があります(笑! RaspberryPi という、手のひらパソコンに付属の、Mathematicaで実行できるプログラムでした。



  • @ソム さん
    ありがとうございます。
    Mathematicaを使うとできるんですね。
    私にはハードルが高そうなので、記事を見ながら出来そうだと思えたら考えてみます。


  • Global Moderator

    しかし、マスターが変わり種のパズルをどうやって仕入れているのか不思議です。超級市場にでも行ってらっしゃるのでしょうか。最近も、ブルーバックスで新しいパズル集が出ていたので立ち読みしたのですが、ネタになりそうな(面白げな・新鮮そうな)食指のそそられるものが見付からず、購入に至りませんでした。「世界の名作」と題していたので、期待したのですが...。なければ自作すべしということもありますが、そちらもなかなかです。



  • @ソム さん
    同感です。
    問題は解くよりも作る方が桁違いに難しいですよね。
    いつも口を開けて餌(問題)を待ってばかりで申し訳ないのですが、私には作問するだけの力がありませんm(__)m



  • 遅ればせながら

    0_1511791542534_nisegane.jpg

    ①ヒントをベースに11,12,13決め打ち
    ②あと二つ(A,Bとします)の間隔≧3(11+Å≠12+Bまたは11+A≠13+Bを保証)
    ③A+B≠11,12,13
    ❹エクセル様に祈祷(;'∀')


  • Global Moderator

    @riffraff さん

    遅ればせながら

    マーモさんとは別解が出てますね! いつもながらの色つきの表ですね。テーブル生成がお好きなんですね(謎 ①の決め打ちが、私には思いつかないです。よく考えれば、値が大きいからといって、和の組合わせが重複しやすくなるという理屈はないはずですが、避けてしまいました。



  • マーモセットさん、ソムさん

    さすがですね\(^o^)/。
    マーモセットさんの方法で、他にも解があるかどうか探したのですが、見つけられず、ソムさんのプログラムをコピペしてMathematicaで実行したら、もう一つ解が見つかりました。ラズベリーパイを起動するのは、もの凄く久しぶりなので、すっかりやり方を忘れてしまっていました。コピペして実行することしかできないのは情けないですが、私にはこれが限界みたいです(>_<)。

    riffraffさんも、さすがですね\(^o^)/


  • Global Moderator

    @オメガ3 さん

    お久しぶりです。私も久々なのでリハビリ中です。別項の、麻雀問題がなかなか解けずにいます。偽金問題は、マスターのお気に入りみたいですね。気づいたこと:

    • 偽金を捜査する側は、予算が逼迫しているらしい。
      • 天秤が少数しか使えなかったり、妙に精度のよい計測が出来るのに、1回しか使えなかったりする。→結果、捜査員の頭脳にしわ寄せ。
    • 偽金を作る側は、技術・資材が豊富らしい。
      • 重さのよく揃った偽金を多数作る技術を持っている。
      • 重さでしか判別ができない偽金を作ることが出来る。


  • @ソム さん

    お久しぶりです(^_^)v
    ひねったパズルが、次から次に出てきて、凄いです。
    今回は13枚というのが絶妙な数なのでしょうね。
    天秤問題も考察が奥深くて、なかなかついていけないです。
    麻雀問題は私もルールを知らず、でもソムさんやマーモセットさんのようにすぐにはマスターできずというところで、パスしています。


  • Global Moderator

    雑談です。電子上皿天秤で重さを正確に測るのって難しいです。特に粉物はです。空調で飛んだり、静電気で変なところに張り付いたりします。その点で、金貨はまだマシかもしれません。10gの金貨の0.1グラムを1キログラムまで測定するというのは、どれくらい難易度か? 前にも別のパズルのときに調べましたが、スペック上は、0.1グラム単位で1キログラム以上を測定可能な電子天秤は市販されています(島津製作所などがブランドです)。問題は測定の精度やばらつきです。さて、どうでしょうか。



  • @ソム さん

    よく考えれば、値が大きいからといって、和の組合わせが重複しやすくなるという理屈はないはずですが、

    私が大きな値から試すことにしたのは、小さい値で埋めていくと、大きな値を選ぶ段階になった時に、値同士の間隔がすでに選ばれている値又はその和で埋まっていて、それ以上に広げなくてはいけなくなり、13以内に収まらなくなってしまうからです。
    かえって大きな値を選んだほうが選ばれた値同士を足した時、その答えが大きなものになる分次に選ぶ値の選択肢が増えるような気がしました。
    結局はたまたま見つかっただけなのですが(;^_^A アセアセ・・・



  • せっかくご投稿をたくさん頂戴しておりますのに、まとまった時間が取れずお返事ができません、申し訳ありません。

    @ソム さん、
    組み合わせはここまでで登場したもの以外にございますでしょうか? 例の式は全部を洗いだしますか?

    一見すると不可能問題にみえること、私もそう思いました。

    @マーモセット さん お楽しみ頂けたようで幸いです。マーモセットさんの脳がスッキリしていることが実によくわかる御回答ですね。

    @riffraff さん。
    ご提示のA案は、見落としておりました。本当に驚きました。 参りました。嬉しいです。

    @オメガ3 さん
    (o^ O^)シ彡☆

    皆様。
    今回の問題のネタ元は、バイオインフォマティクスの論文です。

    ( ̄▽ ̄;)がーん。

    解析の効率をあげる脈絡なのでしょうけれども、ある種の数学的概念を提示するための例題としてパズルが紹介されていました。

    今待合室ですので落ち着いたら詳しくご報告いたします。



  • @Hannibal さん
    数学的な説明が可能な気がしてきました。(不等式の山)
    例によって頭の中だけでの仮説ですので、orzになる可能性(;'∀')
    これからドキュメントに落としてみます。

    <追記 20:40>
    適合する5つの自然数を小さい方からA1からA5とする
    A5-A3≧αと置くと
    ①A1≧α+1、A2-A1≧α+1
    ②α=2or3 (A2とA3の大きさの制約)
    ③❶A1+A2<A3、α=2 
     ❷A1=4、A2=8、A3=10、A4=11、A5=13、α=3
     ❸A1+A2>A5、α=2or3
     についてチェックすればOK
    ❸についてより条件が狭められればよいのですが、(;'∀')



  • @riffraff さんへ。

    A1=4、A2=8、A3=10、A4=11、A5=13

    との記述を拝見いたしました。
    A3+A4 = A2+A5 = 21
    になっているようです。


Log in to reply
 

Looks like your connection to パズルハウス was lost, please wait while we try to reconnect.