偽造金貨と信用できない計測結果（解答）

解答例：まず，結果報告が信用できる場合に，2回の計測で贋物を見つけ出す方法。これは簡単だ。話をわかりやすくするために金貨に1から8までの番号を振っておく。最初に1，2，3の金貨を天秤の左の皿に，4，5，6の金貨を右の皿に載せて計測してもらう。7，8の金貨は計測しない。

 

① 釣り合えば，7，8のどちらかが贋金なので，その2つを比較して軽い方が偽造金貨だとわかる。
② 1，2，3の方が軽ければ，その中に贋金がある。そこで，1と2を計測してもらう。どちらかが軽ければそれが贋金だ。釣り合えば3が贋金だ。
③ 4，5，6の方が軽ければ，その中に贋金がある。そこで，4と5を計測してもらう。どちらかが軽ければそれが贋金で，釣り合えば6が贋金だ。

いずれにせよ，2回の計測で贋金を特定できる。

 

結果報告に信用できないものが混じっている可能性がある場合，問題は急に難しくなる。実は，この問題は木戸孝紀氏がインターネット上に公開している「嘘つき天秤」という問題をほとんどそのままで使わせてもらっている。嘘つき天秤については，読者の方からご紹介頂いた。木戸氏がこの問題をどういう経緯で思いついたかはわからないが，問題はさらに一般化でき，その解を体系的に構成するには「誤り訂正符号」の知識が必要になる。しかし，金貨が8枚で虚偽報告がたかだか1回の場合は，そこまで大げさな道具立てがなくとも解を見つけることはできるので，その1つを以下に紹介しよう。

金貨に1から8の番号を振り，騎士をA，B，C，Dとする。各騎士に次の表のように計測するよう依頼する。

 

 

金貨番号	1	2	3	4	5	6	7	8
騎士A	L	L	L	R	R	R	O	O
騎士B	L	R	O	L	R	O	L	R
騎士C	L	O	R	O	R	L	R	L
騎士D	O	L	R	R	O	L	L	R

 

 

Lは左の皿，Rは右の皿にその金貨を載せることを意味し，Oは計測しない。例えば騎士Aには，左に金貨1，2，3を載せ，右に金貨4，5，6を載せて計測するよう依頼する。

仮にどの騎士からの報告にも嘘がないものとしよう。その場合，各計測においてどちらかが軽ければ，その皿に載せた金貨の中に贋物がある。釣り合えば載せなかった金貨の中に贋物がある。そこで贋物かもしれない金貨に印を付ける。報告に嘘がないとしたら，贋物には4つの印が付くことに注意されたい。一方，上の計測表からわかるように，どの金貨も他の金貨とはただ1回しか同じグループにならないので，本物には贋物と同じグループになったときにただ1回印がつく のみである。

さて，報告に嘘が1つ混じっているとどうなるだろう。その場合でも贋物には最低3つの印がつく。一方，本物にはたかだか2つの印しかつかない。よって3つ以上の印がついた金貨が贋物とわかる。

実は，表の列を縦に取り出したLLLOやLROLという列が，「長さ4の3進ハミング符号」というものを構成する。一般に，ハミング符号は，1文字の誤り訂正が可能なように設計されている。上のLLLOやLROLのような列を符号語というが，ハミング符号では2つの符号語を見比べると3カ所以上で文字が異なっているという特徴があるので，このパズルの解を構成するために利用できるのだ。

長さ4の3進ハミング符号には上の8つ以外にOOOOという符号語もあるので，金貨が9枚あっても贋物の特定が可能だ。9枚目はどの騎士による計測からも外しておけばいい。

さて，最後の16枚の金貨の問題はどうだろう。今度は計測手段が天秤ではなく，放射性物質の有無だから各計測で得られる結果は2通りだけだ。報告に嘘がないなら，候補を半分ずつにして次第に絞っていくことで，合計4回の計測で贋物が特定されることは明らかだろう。

「報告に嘘が1つ混じる可能性がある」という形にしたパズルは筆者の発案によるものだが，この解を構成するのに2進ハミング符号が利用できる。金貨に1から16の番号を振り，下の表のようにグループに分けて計測する。○は計測するグループ，×は計測しないグループに入れることを意味する。

報告に嘘がないとしよう。その場合，各計測において放射性物質が検出されれば，計測したグループに贋物があり，検出されなければ計測しなかったグループに贋物がある。そこで贋物かもしれない金貨に印をつける。報告に嘘がなければ，贋物には7つの印がつくことに注意されたい。

一方，下の計測表からわかるように，どの金貨も他の金貨とは最大で4回しか同じグループにならないので，本物の金貨につく印はたかだか4つである。もし虚偽報告が1つあっても，贋物には最低6つの印がつき，本物にはたかだか5つの印しかつかない。よって6つ以上の印がついた金貨が贋物だとわかる。

先と同様に，左下の表の列を縦に取り出した「○○○○○○○」や「×○○○○××」によって構成されるのが長さ7の2進ハミング符号である。ハミング符 号やさらに別の誤り訂正符号の構成については，ここに詳しく述べる余裕はないが，例えば2進ゴレイ符号を利用すると，虚偽報告が3 回混じっていても，23回の放射能測定で4096枚もの金貨の中から，ただ1枚の贋物を特定することが可能だ。

 

金貨番号

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1回目

○

×

○

×

○

×

○

×

○

×

○

×

○

×

○

×

2回目

○

○

×

×

○

○

×

×

○

○

×

×

○

○

×

×

3回目

○

○

○

○

×

×

×

×

○

○

○

○

×

×

×

×

4回目

○

○

○

○

○

○

○

○

×

×

×

×

×

×

×

×

5回目

○

○

×

×

×

×

○

○

×

×

○

○

○

○

×

×

6回目

○

×

○

×

×

○

×

○

×

○

×

○

○

×

○

×

7回目

○

×

×

○

○

×

×

○

×

○

○

×

×

○

○

×

 

 

 

 

 

問題に戻る