2015/01/03

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

分野: 場合の数  レベル: 数学オリンピック

天秤を使って偽物(重さの異なる)のコイン(金貨ということもある)を見つけ出すという有名問題について紹介します。

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.限界を少しでも超えたら達成できないこと

の二つに分けて考えるとスッキリ説明できることが多いです。

数学オリンピックでは,1と2の両方とも難しく,片方証明すれば部分点がもらえそうな問題もあります。

(もちろん簡単な問題では,二つに分けるとまどろっこしくなるので一気に最大性を述べたほうがよい場合もあります)

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

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

問題

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

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

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

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

Tag: 難しめの数学雑学・ネタまとめ

分野: 場合の数  レベル: 数学オリンピック