偽物のコインと天秤の有名問題

更新 2021/03/07

天秤を使って偽物（重さの異なる）のコインを見つけ出すという有名問題を紹介します。

9枚のコイン

まずは有名な9枚の場合です。簡単なクイズです。

問題

9枚のコインがある。そのうち偽物が1枚だけある。偽物は本物のコインより軽い。このとき天秤を二回だけ使って偽物を見つけ出せ。

解答を見る前に少しだけ考えてみてください！

解答

一回目は，左の皿に3枚，右の皿に3枚のせる

左が高くなった場合：左の3枚の中に偽物あり
右が高くなった場合：右の3枚の中に偽物あり
つりあった場合：残った3枚の中に偽物あり

いずれにせよ偽物の候補を3つに絞れる。

二回目は偽物の候補3枚のうち左の皿に1枚，右の皿に1枚のせる

左が高くなった場合：左に載せたのが偽物
右が高くなった場合：右に載せたのが偽物
つりあった場合：残った1枚が偽物

一般化

さきほどの問題を一般化します：

問題

$N$ 枚のコインがある。そのうち偽物が1枚だけある。偽物は本物のコインより軽い。このとき天秤を $k$ 回だけ使って偽物を見つけ出せるような最大の $N$ を， $k$ を使って表せ。

天秤が一回しか使えない場合，判別できる枚数の限界は明らかに3枚です。
さきほどの例より， $N=9$ のとき二回で偽物が判別できます。
$N=10$ だと二回で判別するのは難しそうです。

以上より， $k$ 回天秤を使って判別できる限界の枚数は $3^k$ だと予想できます。

解答

1． $N=3^k$ のとき偽物を特定できる

これはさきほどの $k=2$ の場合の方法を一般化すればよい。 $3^k$ 枚あるときに，左右の皿に $3^{k-1}$ 枚ずつのせることで，偽物の候補を $3^{k-1}$ 枚に絞り込むことができる。この操作を繰り返すことで毎回偽物の候補を $\dfrac{1}{3}$ ずつにすることができる。

2． $N > 3^k$ のときどう頑張っても偽物を特定できない

天秤を一回使ったときに得られる出力（結果）は「左が高くなる」「右が高くなる」「つりあう」の三通り。よって， $k$ 回天秤を使うことで得られる出力は $3^k$ 通り。よって， $3^k+1$ 通り以上の場合を判別することはできない。

※上記の2の説明は，そんなの当たり前だと感じる人もいれば，ピンと来ない人もいるかと思います。ピンと来ない人は $k=1,\:2$ の状況を考えてみると納得しやすいでしょう。

限界の証明

上記のような，限界値・最大値を求める問題では
限界ギリギリの値は達成できること
限界を少しでも超えたら達成できないこと
に分けて考えるとスッキリ説明できることが多いです。
数学オリンピックでは，1と2の両方とも難しく，片方証明すれば部分点がもらえそうな問題もあります。
もちろん，簡単な問題では二つに分けるとまどろっこしくなるので，一気に最大性を述べたほうがよい場合もあります。

偽物が重いか軽いか分からない場合

この場合は一気に問題が難しくなります。有名なのは13枚のコインの問題です：

問題

13枚のコインがある。そのうち偽物が1枚だけある。偽物は本物のコインと重さが違う。このとき天秤を三回だけ使って偽物を見つけ出せ。

解答は長くなるので省略します，考えてみてください！

ちなみに，重いか軽いか分からない場合も一般化できて，天秤が $k$ 回使えるときに判別できる枚数の限界は $\left\lfloor\dfrac{3^k}{2}\right\rfloor=\dfrac{3^k-1}{2}$ 枚です。

9枚のコインの問題は友達に出したくなるクイズですね。

Tag:難しめの数学雑学・ネタまとめ（金貨ということもある）

この記事の監修者

マスオ

高校数学の美しい物語の管理人。「わかりやすいこと」と「ごまかさないこと」の両立を意識している。著書に『高校数学の美しい物語』『超ディープな算数の教科書』。記事の誤植やわかりにくい等のご指摘はお気軽にメールください！