この質問は、【パズル】http://q.hatena.ne.jp/1291532081 の変種です。解答があるのかどうか私にはわかりません。みなさんからご教示を頂きたく思っております。

問題。ここにどちらが重いのか、あるいは、等しい重さであるのか、を量れる天秤と、13枚の金貨があります。 金貨のうち2枚は贋物です。贋物の重さは互いに同じです。贋物の重さは本物よりも軽いです。 4回だけ天秤を使って贋物の金貨を探すにはどうしたら良いでしょう。 ただし、n回目の計量の結果をみて(n+1)回目以後の計量の方法を考える、といったことが出来ません。
例題。13枚を4回ではなく、7枚を3回で、というより簡単な例題では、以下のように考えることができます。
今、7枚のコインを、A,B,C,D,E,F,G とします。この中から2枚の軽い偽コインを特定するための3回の計量方法の一例は、下のようになります。もちろん3回の計量の順番を変更しても構いません。
[ ABC ^ DEF ]
[ BE ^ CD ]
[ AE ^ BF ]
お確かめください。

回答の条件
  • 1人3回まで
  • 登録:2010/12/08 14:20:50
  • 終了:2010/12/14 15:51:34

ベストアンサー

id:imo758 No.1

imo758回答回数121ベストアンサー獲得回数192010/12/10 04:51:28

ポイント100pt

計測結果によって計測方法を変更できないということは、計測順序を入れ替えても構わない方法でなければなりません。しかし1回目の結果でどの結果にせよそれぞれ3^3以下のパターンに収めるには、4枚ずつを載せるしかありません。計測順序の交換に耐えうるようにするには、4回すべての計測において4枚ずつ計測するしかないことになります。

ところで対称性を考慮すると、1回目の計測のコインは"ABCD ? EFGH"、計測しないコインはIJKLMと名づけて一般性を失いません。そして2回目の計測において考えうるパターンは、対称性において同一のものを省くと以下のとおりですが……

■1
"ABCD=EFGH" "ABCD=EFGI" 18 AE AF AG BE BF BG CE CF CG DE DF DG JK JL JM KL KM LM
"ABCD=EFGH" "ABCD=EFIJ" 11 AE AF BE BF CE CF DE DF KL KM LM
"ABCD=EFGH" "ABCD<EIJK" 12 AF AG AH BF BG BH CF CG CH DF DG DH

■2
"ABCD=EFGH" "ABCD>IJKL" 10 IJ IK IL IM JK JL JM KL KM LM
"ABCD=EFGH" "ABCE=DFGH" 20 AF AG AH BF BG BH CF CG CH DE IJ IK IL IM JK JL JM KL KM LM
"ABCD=EFGH" "ABCE=DFGI" 13 AF AG BF BG CF CG DE JK JL JM KL KM LM

■3
"ABCD=EFGH" "ABCE>DFIJ" 10 DF DG DH IJ IK IL IM JK JL JM
"ABCD=EFGH" "ABCE>DIJK" 12 DF DG DH IJ IK IL IM JK JL JM KL KM
"ABCD=EFGH" "ABCE=FGIJ" 10 AF AG BF BG CF CG DH KL KM LM

■4
"ABCD=EFGH" "ABCE>FIJK" 10 DF IJ IK IL IM JK JL JM KL KM
"ABCD=EFGH" "ABCE>IJKL" 10 IJ IK IL IM JK JL JM KL KM LM
"ABCD=EFGH" "ABCI=DEFG" 15 AE AF AG BE BF BG CE CF CG JK JL JM KL KM LM

■5
"ABCD=EFGH" "ABCI=DEFJ" 10 AE AF BE BF CE CF IJ KL KM LM
"ABCD=EFGH" "ABCI<DEJK" 11 AF AG AH BF BG BH CF CG CH IL IM
"ABCD=EFGH" "ABCI>DJKL" 10 DE DF DG DH JK JL JM KL KM LM

■6
"ABCD=EFGH" "ABCI=EFGJ" 14 AE AF AG BE BF BG CE CF CG DH IJ KL KM LM
"ABCD=EFGH" "ABCI=EFJK" 11 AE AF BE BF CE CF DG DH IJ IK LM
"ABCD=EFGH" "ABCI<EJKL" 10 AF AG AH BF BG BH CF CG CH IM

■7
"ABCD=EFGH" "ABCI<JKLM" 12 AE AF AG AH BE BF BG BH CE CF CG CH
"ABCD=EFGH" "ABEF=CDGH" 18 AG AH BG BH CE CF DE DF IJ IK IL IM JK JL JM KL KM LM
"ABCD=EFGH" "ABEF=CDGI" 12 AG BG CE CF DE DF JK JL JM KL KM LM

■8
"ABCD=EFGH" "ABEF>CDIJ" 11 CG CH DG DH IJ IK IL IM JK JL JM
"ABCD=EFGH" "ABEF>CGIJ" 10 CG CH DG IJ IK IL IM JK JL JM
"ABCD=EFGH" "ABEF>CIJK" 11 CG CH IJ IK IL IM JK JL JM KL KM

■9
"ABCD=EFGH" "ABEF>IJKL" 10 IJ IK IL IM JK JL JM KL KM LM
"ABCD>EFGH" "ABEI=CDFJ" 10 EF EJ FI GH GK GL GM HK HL HM
"ABCD=EFGH" "ABEI>CDJK" 11 CF CG CH DF DG DH JK JL JM KL KM

■10
"ABCD=EFGH" "ABEI=CFGJ" 10 AF AG BF BG CE DH IJ KL KM LM
"ABCD>EFGH" "ABEI>CFJK" 10 FG FH FJ FK FL FM GJ GK HJ HK
"ABCD=EFGH" "ABEI<CJKL" 10 AE AF AG AH BE BF BG BH DE IM

■11
"ABCD>EFGH" "ABEI>FJKL" 12 FG FH FJ FK FL FM GJ GK GL HJ HK HL
"ABCD=EFGH" "ABEI=JKLM" 10 CF CG CH DF DG DH IJ IK IL IM
"ABCD=EFGH" "ABIJ>CDKL" 11 CE CF CG CH DE DF DG DH KL KM LM

■12
"ABCD=EFGH" "ABIJ=CEFG" 10 AE AF AG BE BF BG DH KL KM LM
"ABCD>EFGH" "ABIJ>CEFK" 13 EF EG EH EK EL EM FG FH FK FL FM GK HK
"ABCD>EFGH" "ABIJ>CEKL" 12 EF EG EH EK EL EM FK FL GK GL HK HL

■13
"ABCD=EFGH" "ABIJ=CKLM" 10 DE DF DG DH IK IL IM JK JL JM
"ABCD=EFGH" "ABIJ=EFKL" 12 AE AF BE BF CG CH DG DH IK IL JK JL
"ABCD=EFGH" "ABIJ=EKLM" 14 AE BE CF CG CH DF DG DH IK IL IM JK JL JM

■14
"ABCD=EFGH" "AEIJ=BFKL" 10 AF BE CG CH DG DH IK IL JK JL
"ABCD=EFGH" "AEIJ=BKLM" 13 BE CF CG CH DF DG DH IK IL IM JK JL JM

と、全てのパターンにおいて、偽コインの組み合わせが3^2パターンを超える計測結果の組み合わせを避けることができません。

よって上記のパターンに抜けなどのミスがあるか、頓智などを用いない限り、「解答はない」というのが答になります。

補足:■は、単にチェックしやすくするためのナンバリングです。

id:hoshikuzu

12/10付け返信。

imo758さん、ていねいな回答をありがとうございます。とりあえず、オープンさせて頂きました。 これは…きちんと消化させて頂かなくてはいけません。

「対称性において同一のものを省く」作業を私のほうでも追わせて下さいませ。

12/13付け返信。

たとえば、"ABCD>EFGH" の際に、

2回目の計量において、ABCDのどの一枚も含まない計量というのは、考慮に値しないのでしょうか…ちょっと私のはやとちりかもしれません。

12/14付け返信。

本質問の自動終了が12/15です。 本日手動で締めさせていただきました。

imo758さんによる斬新な切り口で膨大な量の分岐を減らすことができました。ありがとうございました。

2010/12/14 15:50:04

その他の回答(1件)

id:imo758 No.1

imo758回答回数121ベストアンサー獲得回数192010/12/10 04:51:28ここでベストアンサー

ポイント100pt

計測結果によって計測方法を変更できないということは、計測順序を入れ替えても構わない方法でなければなりません。しかし1回目の結果でどの結果にせよそれぞれ3^3以下のパターンに収めるには、4枚ずつを載せるしかありません。計測順序の交換に耐えうるようにするには、4回すべての計測において4枚ずつ計測するしかないことになります。

ところで対称性を考慮すると、1回目の計測のコインは"ABCD ? EFGH"、計測しないコインはIJKLMと名づけて一般性を失いません。そして2回目の計測において考えうるパターンは、対称性において同一のものを省くと以下のとおりですが……

■1
"ABCD=EFGH" "ABCD=EFGI" 18 AE AF AG BE BF BG CE CF CG DE DF DG JK JL JM KL KM LM
"ABCD=EFGH" "ABCD=EFIJ" 11 AE AF BE BF CE CF DE DF KL KM LM
"ABCD=EFGH" "ABCD<EIJK" 12 AF AG AH BF BG BH CF CG CH DF DG DH

■2
"ABCD=EFGH" "ABCD>IJKL" 10 IJ IK IL IM JK JL JM KL KM LM
"ABCD=EFGH" "ABCE=DFGH" 20 AF AG AH BF BG BH CF CG CH DE IJ IK IL IM JK JL JM KL KM LM
"ABCD=EFGH" "ABCE=DFGI" 13 AF AG BF BG CF CG DE JK JL JM KL KM LM

■3
"ABCD=EFGH" "ABCE>DFIJ" 10 DF DG DH IJ IK IL IM JK JL JM
"ABCD=EFGH" "ABCE>DIJK" 12 DF DG DH IJ IK IL IM JK JL JM KL KM
"ABCD=EFGH" "ABCE=FGIJ" 10 AF AG BF BG CF CG DH KL KM LM

■4
"ABCD=EFGH" "ABCE>FIJK" 10 DF IJ IK IL IM JK JL JM KL KM
"ABCD=EFGH" "ABCE>IJKL" 10 IJ IK IL IM JK JL JM KL KM LM
"ABCD=EFGH" "ABCI=DEFG" 15 AE AF AG BE BF BG CE CF CG JK JL JM KL KM LM

■5
"ABCD=EFGH" "ABCI=DEFJ" 10 AE AF BE BF CE CF IJ KL KM LM
"ABCD=EFGH" "ABCI<DEJK" 11 AF AG AH BF BG BH CF CG CH IL IM
"ABCD=EFGH" "ABCI>DJKL" 10 DE DF DG DH JK JL JM KL KM LM

■6
"ABCD=EFGH" "ABCI=EFGJ" 14 AE AF AG BE BF BG CE CF CG DH IJ KL KM LM
"ABCD=EFGH" "ABCI=EFJK" 11 AE AF BE BF CE CF DG DH IJ IK LM
"ABCD=EFGH" "ABCI<EJKL" 10 AF AG AH BF BG BH CF CG CH IM

■7
"ABCD=EFGH" "ABCI<JKLM" 12 AE AF AG AH BE BF BG BH CE CF CG CH
"ABCD=EFGH" "ABEF=CDGH" 18 AG AH BG BH CE CF DE DF IJ IK IL IM JK JL JM KL KM LM
"ABCD=EFGH" "ABEF=CDGI" 12 AG BG CE CF DE DF JK JL JM KL KM LM

■8
"ABCD=EFGH" "ABEF>CDIJ" 11 CG CH DG DH IJ IK IL IM JK JL JM
"ABCD=EFGH" "ABEF>CGIJ" 10 CG CH DG IJ IK IL IM JK JL JM
"ABCD=EFGH" "ABEF>CIJK" 11 CG CH IJ IK IL IM JK JL JM KL KM

■9
"ABCD=EFGH" "ABEF>IJKL" 10 IJ IK IL IM JK JL JM KL KM LM
"ABCD>EFGH" "ABEI=CDFJ" 10 EF EJ FI GH GK GL GM HK HL HM
"ABCD=EFGH" "ABEI>CDJK" 11 CF CG CH DF DG DH JK JL JM KL KM

■10
"ABCD=EFGH" "ABEI=CFGJ" 10 AF AG BF BG CE DH IJ KL KM LM
"ABCD>EFGH" "ABEI>CFJK" 10 FG FH FJ FK FL FM GJ GK HJ HK
"ABCD=EFGH" "ABEI<CJKL" 10 AE AF AG AH BE BF BG BH DE IM

■11
"ABCD>EFGH" "ABEI>FJKL" 12 FG FH FJ FK FL FM GJ GK GL HJ HK HL
"ABCD=EFGH" "ABEI=JKLM" 10 CF CG CH DF DG DH IJ IK IL IM
"ABCD=EFGH" "ABIJ>CDKL" 11 CE CF CG CH DE DF DG DH KL KM LM

■12
"ABCD=EFGH" "ABIJ=CEFG" 10 AE AF AG BE BF BG DH KL KM LM
"ABCD>EFGH" "ABIJ>CEFK" 13 EF EG EH EK EL EM FG FH FK FL FM GK HK
"ABCD>EFGH" "ABIJ>CEKL" 12 EF EG EH EK EL EM FK FL GK GL HK HL

■13
"ABCD=EFGH" "ABIJ=CKLM" 10 DE DF DG DH IK IL IM JK JL JM
"ABCD=EFGH" "ABIJ=EFKL" 12 AE AF BE BF CG CH DG DH IK IL JK JL
"ABCD=EFGH" "ABIJ=EKLM" 14 AE BE CF CG CH DF DG DH IK IL IM JK JL JM

■14
"ABCD=EFGH" "AEIJ=BFKL" 10 AF BE CG CH DG DH IK IL JK JL
"ABCD=EFGH" "AEIJ=BKLM" 13 BE CF CG CH DF DG DH IK IL IM JK JL JM

と、全てのパターンにおいて、偽コインの組み合わせが3^2パターンを超える計測結果の組み合わせを避けることができません。

よって上記のパターンに抜けなどのミスがあるか、頓智などを用いない限り、「解答はない」というのが答になります。

補足:■は、単にチェックしやすくするためのナンバリングです。

id:hoshikuzu

12/10付け返信。

imo758さん、ていねいな回答をありがとうございます。とりあえず、オープンさせて頂きました。 これは…きちんと消化させて頂かなくてはいけません。

「対称性において同一のものを省く」作業を私のほうでも追わせて下さいませ。

12/13付け返信。

たとえば、"ABCD>EFGH" の際に、

2回目の計量において、ABCDのどの一枚も含まない計量というのは、考慮に値しないのでしょうか…ちょっと私のはやとちりかもしれません。

12/14付け返信。

本質問の自動終了が12/15です。 本日手動で締めさせていただきました。

imo758さんによる斬新な切り口で膨大な量の分岐を減らすことができました。ありがとうございました。

2010/12/14 15:50:04
id:fhty5vu8--0i0gf No.2

グランエル回答回数4ベストアンサー獲得回数02010/12/11 21:34:32

ええ

id:hoshikuzu

曲者っつ!(苦笑

2010/12/12 14:06:21
  • id:hoshikuzu
    こちらに、若干詳しく、例題の趣旨について書いてありますので、よろしければ、ご参照のほどお願いいたします。
    http://d.hatena.ne.jp/hoshikuzu/20100512
    http://d.hatena.ne.jp/hoshikuzu/20100615
  • id:hoshikuzu
    http://q.hatena.ne.jp/1291532081 と、本質問には、実は関連性があります。
    本質問において、各計量では、5対5や6対6の重量比較をすると、失敗してしまうからです。 そのことを示すために、まず、6対6の計量をしたと仮定しましょう。釣り合った場合が問題で、この時、左の皿の6枚のうち1枚と、およびに右の皿の6枚のうち1枚とが、贋物だです。その組み合わせの数は、6×6=36通りです。 ところが、残る3回の計量で分別できる組み合わせは、3×3×3=27通りにすぎません。 これでは贋物の特定が不可能です。(続く
  • id:hoshikuzu
    次に、5対5の計量が行われたとしましょう。 釣り合ったときが厄介です。 計量が行われていない3枚の金貨のうち、2枚が贋物である可能性があり、容易に、3通りだとわかります。 また、左の皿の5枚のうち1枚と、およびに右の皿の5枚のうち1枚とが贋物である可能性があり、その組み合わせの数は、5×5=25通りです。 両方の可能性の組み合わせの数を合算して、25+3=28通りが、5対5の計量で釣り合ってしまった場合の贋物の組み合わせの数となります。 ところが、既に示したように、残る3回の計量で分別できる組み合わせは27通りにすぎませんから、これでは、贋物の特定が不可能です。(続く
  • id:hoshikuzu
    以上からわかるとおり、本質問においては、天秤の左右の皿に乗せることができる枚数は、それぞれ最大4枚であるということになります。
    さて、http://q.hatena.ne.jp/1291532081 にて、ひとつの皿に4枚まで、という制限をつけた理由がここにあります。 1291532081は、前回の天秤の計量結果を参照しつつ、次回以降の計量方法を決めていくタイプなのですが、この時点で、たとえひとつでも解が存在しなければ、より条件の厳しい、前回の結果を参照できない条件の、本質問に解が存在するはずがないからです。
    幸いにして、1291532081の質問で解がありそうだとわかりましたので、ひょっとしたら本質問にも解があるかもしれない、そういった希望が出てきたわけです。
    本質問は、長い間、折にふれ、個人的にたびたび考えてきた課題でして、そろそろ結論が欲しいなぁと念願しているしだいです。
  • id:imo758
    同様に3,2,1枚ずつの計測をしてしまうと、それだけで失敗ですね。
    可能だとしてもどのみち、4枚ずつの計測だけで達成しなくてはなりません。
  • id:imo758
    ミスが無ければダメだという感触は得られたのですが
    ミスチェックが非常に厄介です……
  • id:hoshikuzu
    うお・・・ひょっとしたら不可能ですって? ながねん紙と鉛筆で解こうとしていた私はいったい・・・
  • id:imo758
    ┏━━━━━━━━━━━━━━━━━━━━━━
    ┃n回目の計量の結果をみて(n+1)回目以後の計量の方法を考える、
    ┃といったことが出来ません。
    ┗━━━━━━━━━━━━━━━━━━━━━━

    とあるので

    ┏━━━━━━━━━━━━━━━━━━━━━━
    ┃たとえば、"ABCD>EFGH" の際に、

    ┃2回目の計量において、ABCDのどの一枚も含まない計量というのは、
    ┃考慮に値しないのでしょうか…ちょっと私のはやとちりかもしれません。
    ┗━━━━━━━━━━━━━━━━━━━━━━

    といったことはできません。

    ■ABCDとEFGHの対称性を考慮すると、2回目でABCDのどの1枚も含まない計量というのは、EFGHのどの1枚も含まない軽量と同一です。
    するとIJKLMだけで計量することになりますが、合計5枚だけでは4枚ずつ8枚を用いた計量は無理です。
  • id:hoshikuzu
    imo758さん、ていねいなご教示をありがとうございます。

    im758さんwrote:『ABCDとEFGHの対称性を考慮すると、2回目でABCDのどの1枚も含まない計量というのは、EFGHのどの1枚も含まない軽量と同一です。』について、重ねて質問をさせてください。

    "ABCD>EFGH" の状況が成立していると、ABCDとEFGHの対称性がふっとんでいる、そのように感じたものでして。これは、1回目の計量にてABCDが無罪(苦笑)であって、さらに、私が言うところの《2回目でABCDのどの1枚も含まない計量》というのは、ABCDが無罪に決まっているのだからもはや取り調べの要なし、ゆえに、1回目だけではまだまだ有罪の可能性の残されている EFGH およびに、IJKLM から、4枚ずつ8枚を用いた計量をしてみたらどうなるのだろう?という…
    別の角度から、おたずねいたしますと、以下のようにもなります。
    imo758さんのおっしゃる通りに、『ABCDとEFGHの対称性を』重視するのであるならば、ABCDとEFGHの立場を逆転させて書き下して良いことになります。すなわち、以下のように。

    ┃逆転前
    ┃たとえば、"ABCD>EFGH" の際に、

    ┃2回目の計量において、ABCDのどの一枚も含まない計量というのは、
    ┃考慮に値しないのでしょうか

    ┃逆転後
    ┃たとえば、"ABCD<EFGH" の際に、

    ┃2回目の計量において、EFGHのどの一枚も含まない計量というのは、
    ┃考慮に値しないのでしょうか

    しかるに、imo758さんが付番された、■1 から ■14 までには、"ABCD<EFGH"が含まれていません。
    ひよっとしたら、かなり重篤な誤解を私がしでかしているかもしれず、何回か考え直してみたのですが、先入観念に邪魔されているようでして、とんと、柔らかい発想が出てこないのです。

  • id:hoshikuzu
    まいった…まだわからない。とひょよぇー。
  • id:imo758
    1回目の計測結果で2回目の計測を変更することは禁止されています。よって1回目の計測結果を得る前から2回目の計測を計画できなければなりません。

    その状況ではABCDをEFGHと、EFGHをABCDと名付け直してもかまいません。そうすると『2回目でABCDのどの1枚も含まない計量』が得られることになります。例えば

    "ABCD ? EFGH" "ABCD ? IJKL"

    のABCDとEFGHを名付け換えて、1回目の計測の左右も入れ換えれば

    "ABCD ? EFGH" "EFGH ? IJKL"

    が得られます。しかしそうしてもやはり10パターン以上が区別できない計測結果の組み合わせ

    "ABCD = EFGH" "EFGH > IJKL" 10 IJ IK IL IM JK JL JM KL KM LM

    が残ってしまうのです。

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

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

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

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