ニコニコ大百科

よくまとまっている良記事
記事作成乙

指定の回数よりも少なく判別できるパターンがあってもおkなら
7枚の金貨に2枚の贋物の問題はこの手順でいける気が

7枚の金貨それぞれをABCDEFGとして区別

1.天秤に金貨を2枚ずつABとCDを載せて比べる

2-1.ABがCDより軽かった場合、AとBを比べる
2-2.ABが釣り合えば両方が贋作確定。
2-3.ABが傾けば軽かった方と贋作でEFGに一枚贋作確定なのでEとFを比べる

3.ABがCDより重かった場合、CDを比べる(ry

4-1.ABとCDが釣り合った場合、EFとABを比べる。
(この場合ABとCDに1枚ずつ贋作があるかEFGに2枚贋作)
4-2.ABがEFより軽かった場合、AとBを比べる
4-3.AとBで軽かった方とGが贋作。

4-2.ABがEFより重かった場合、EとFを比べる
4-3.EとFで傾きがあれば軽かった方とGが贋作。釣り合えば両方が贋作

4-2 ABがEFより軽いときは贋作はABとCDそれぞれに一枚ずつやで

ひっかけパターンに「居合わせている関係者に吐かせてしまえば、その1手で解決する」というのもあったような。どこだったかな？

10gの金貨が1000枚ずつ入った袋が10個ある。
しかし、11gの贋物だけが入った袋が少なくとも1袋混じっているという。
贋物だけ入った袋がいくつあるかは分からない。
はかりを何回使えばすべての贋物の袋を見つけられるだろうか。

「袋に入った金貨」はこんな感じのバリエーションもあった。

>>5
ですね。
記事にも一応「贋物の袋の個数が不明なパターンもある」と記載していますが
考え方は似ているので説明は割愛させていただきました。

居合わせていた人間は運び屋で何を運んだか知らないものとする

昔は割とシャレにならない事態だったんだよね
金貨の中に軽い偽物が混ざってるって

特に中世～近代のフランスは質のいい金貨を大量に集めて、質の悪い金貨と強制的に両替させるとかやってたからな・・・

噛んで見極めちゃえ

味も見ておこう

>>10
中世ならわりと最適解だったりする

裏贋金(ウラガンキン)

実際の贋金には金貨と比重が近いタングステンに
金メッキをしたものが使われるから
秤で見分けられるのは黄銅や黄鉄鉱に限られる

天秤で軽重を調べる行為はある種の正規直交基底による変換なんじゃないかと思った
うまくやればクイックソートや高速フーリエ変換に似た高速贋金探しアルゴリズムができるかもしれない
あるいは贋金が全体に比べて少ないならスパースモデリングみたいな「自動的に高確率で異物を選り分けるアルゴリズム」が存在するかも
と考えたのでだれか続き考えてくれないかなあ

>>4
「頭の体操」（多湖輝）シリーズで見たような覚えがある。でも考えてみると、それが成り立つのにも条件があるのでは……。

「敵の潜水艦を沈めるのに使うべき脳を浪費させられた」
「ドイツと日本にもこの問題をばら撒けばこの戦争は早く終わる」

オススメ記事で見つけて来たんだけど、１３枚の金貨とかのところに書いてある最大数の証明、たぶん間違ってる（少なくても不十分）だよ。

偽物の金貨が重いか軽いかまで求めなければいけない場合は書いてある通りなんだけど、かならずそうであるとは言い切れないよ。
普通の天秤ばかりの場合の反例は知らないけど、左右の重さが2対1の時につり合う特殊な天秤の場合は、１４枚までなら３回で偽物が特定できるよ（やり方は後述）。
この場合も『天秤ばかりは1回の操作で「左<右」「左=右」「左>右」の3通りの情報のうち1つをもたらし、1回操作するたびに候補は1/3に絞られていく。3回操作すると(1/3)^3=1/27にまで絞れる』という性質は変わらないから、記事の内容とは矛盾するよ。

17の続き


重さ２対１でつり合う天秤と１４枚のコイン（偽物１枚）の場合の求め方

１回目　左123456 右789
(1）１回目で傾いた場合
　　２回目　左123789 右ABC
（1-1）つり合った場合
　　　　　偽物は789のどれか、重いか軽いかも判明
　　 (1-2) １回目と同じ側に傾く
　　　　　偽物は123のどれか、重いか軽いかも判明
　　（1-3) １回目と逆側に傾く
　　　　　偽物は789のどれか、重いか軽いかも判明
(2）１回目でつり合った場合
　　２回目　左AB 右C
　　 (2-1) 傾いた場合
　　　　　 ３回目　左1A 右B
（2-2）つり合った場合
　　　　 　偽物はDEのどちらか
　　　　　 ３回目　左12 右D
　　　　　 傾けばD、
傾かなければE(注、この時Fが重いか軽いかは分からない)

正直、厳密に証明しようと思って書いた箇所じゃないので、間違いがあるかもなぁとは思っていたんですが
精査して修正する時間的余裕がないので、間違いであるならば丸々削除する方向で対応しようと思います。

まぁ「左右の重さが2対1の時につり合う特殊な天秤の場合」という条件をつけないといけないなら
今の記述は「正しいかは分からないが間違いとも断定できない」という感じなんでしょうかね。
もう少し様子見しておきます。

17、18を書いた者です。

先程考えてみたのですが、N回で贋金を見つけることができる最大数は、(3^N-1)/2以下になるようですね。
４日前は、むしゃくしゃしてる時に深くは考えないで書きこんでしまったのですけど、申し訳ないです。
一度に天秤の両側に乗せる金貨の枚数の合計が奇数か偶数かが関係してるみたいです。
もうちょっと詳しい話は後日書きます。今眠すぎて上手く説明できないので。

>>21で言ってた証明です。

天秤ばかりをＮ回使って偽物を見つけ出せる場合の金貨の枚数の最大数が、(3^N-1)/2以下であることの証明

（半角と全角で数字や文字を区別しないので注意、見た目で適当に変えてます）

（偽物を含めた）金貨の枚数をＭとして、天秤Ｎ回の使用で偽物が見つけ出せたとする。
この時の偽物を見つけ出す操作を操作Ｓとおく。

操作Ｓの１回目の操作で天秤に乗せる金貨の集合をＡ、乗せない金貨の集合をＢとする。
（以下、任意の集合Ｘの要素の個数を＃Ｘと表記する）
天秤に一度も乗せずに偽物だと断定できる枚数は１枚以下であること、
それ以外の金貨が偽物である場合は、操作Ａによって偽物が重いか軽いかが判明することに注意する。

（ⅰ)、＃Ａ≦3^(N-1)-1 の証明
　操作Ｓの一度目の操作で天秤が傾いたとき、集合Ａの中に偽物が存在する。
　この時、操作Ｓの全Ｎ回の操作の結果の組み合わせは最大で2×3^(N-1)通り。
　一方、集合Ａの金貨が偽物である場合の組み合わせは、偽物の重い場合と軽い場合を区別して数えると、
　2×(♯Ａ)通りで、それぞれに、対応した『操作Ｓの全Ｎ回の操作の結果』が存在する。
　よって　
2×(＃Ａ)≦2×3^(N-1)
⇔　＃Ａ≦3^(N-1)
　
また、＃Ａは一回目に天秤に乗せる金貨の総数なので、偶数でなければならない。
　よって
　　　　　　＃Ａ≦3^(N-1)-1

（以下、>>23？に続く）

>>22の続き

(ⅱ)、＃Ｂ≦{3^(N-1)+1}/2 の証明
　操作Ｓの一度目の操作で天秤がつり合ったとき、集合Ｂの中に偽物が存在する。
　この時、操作Ｓの全Ｎ回の操作の結果の組み合わせは最大で3^(N-1)通り。
　一方、集合Ｂの金貨が偽物である場合の組み合わせは、
　『一度でも天秤に乗せる金貨が偽物であった場合のみ、それの重い場合と軽い場合を区別する』とすると、
　2×{(＃Ｂ)-1}＋1通りで、それぞれに、対応した『操作Ｓの全Ｎ回の操作の結果』が存在する。　
　よって
　　　　　2×{(＃Ｂ)-1}＋1≦3^(N-1)　
⇔　＃Ｂ≦{3^(N-1)+1}/2

（ⅰ）、（ⅱ）より、
　　金貨総数Ｍ＝(＃Ａ)＋(＃Ｂ)
≦3^(N-1)-1＋{3^(N-1)+1}/2
＝(3^N-1)/2 [Q.E.D]

>>22、>>23の続きです。

というわけで、重いか軽いか分からない偽物１枚を天秤N回使用で見つけられる金貨の最大数は(3^N-1)/2になりそうです。
（できることの証明はちょっと待ってください。）
ただし、(3^N-1)/2の中から偽物を探す場合、偽物が軽いか重いかまでは特定できない場合が存在するようです。
（記事の１３枚の解法でも金貨Mが偽物の場合は特定してないですしね。とはいえ、>>22と>>23の証明が合ってる場合の話ですけど）

記事の証明は間違っている部分もありそうですが、全部消しちゃうのはもったいないですね。
記事の『1回の操作で「左<右」「左=右」「左>右」の3通りの情報のうち1つをもたらし』や『軽いか重いか分からない贋物が1枚だけ混じっている場合、答えは2n通り』などの考え方を読んでなかったら、自分もさっき書いたような証明は考えられなかったでしょうし。

>>24
できることの証明
https://mistlewheat.akazunoma.com/three/