ソフトウェアの品質を学びまくる

ソフトウェアの品質、ソフトウェアテストなどについて学んだことを記録するブログです。

地味な天秤系パズルが実はけっこう面白いと気づかされた。

Balance scale"Balance scale" by Sepehr Ehsani is licensed under CC BY-NC-ND 2.0

こんな有名な問題がありますね。

8個のボールがある。7個は同じ重さで、残りの1個だけ他の7個よりわずかに重い。
天秤を2回だけ使って、重い1個を特定するにはどうすればいいか。

このような「天秤系」のパズル、どうも根気系・しらみつぶし系に思えてあまり魅力を感じず、すぐに答えを見てしまうわたしです。
そんな天秤系パズルについて、「やっぱ面白いかも!」と思える話を2つ見つけたので、紹介します。

1g刻みで重さを測る方法

元ネタはこの本です。

問題はこんな感じ。

1gから40gまでの重さを、1gきざみで量るためには、最低何個の分銅が必要か。

たとえば3gと5gの分銅があれば、3g、5g、(2つ使って)8gの重さを測ることができます。一方、1gを測ることはできませんね。

この問題を見て反射的に、IT関連の人

両手の指10本を使って表現できる数は何種類?

という話を連想するかもしれません。元の問題は、「1から40までの数字を表現するには、指が何本必要?」と読み替えることができますよね。
たとえば18gを測りたければ、(13)10=(001101)2 なので、20=1gと、22=4gと、23=8gの、計3つの分銅があれば済むわけです。
40gまでを1gきざみで測りたければ、2の累乗となる1g、2g、4g、8g、16g、32gの6つがあれば済みます。

ということで、「簡単な問題だな~」といい気になっていたのですが、実は6つさえいらず、4つだと

その4つとは、3の累乗となる1g、3g、9g、27g。
いや、それだとたとえば7gなんて表現できないし、そもそも4つだと最大でも24しか表現できないのでは・・・と思いません?

では、この4つで7gを測るにはどうすればいいか。
測る側に、1gと9gを載せる。測られる側に、測られるもの(7g)と3gを載せる。こうすれば釣り合う、というんですね・・・!

上の例だと

13 = 1*1 + 2*0 + 4*1 + 8*1

にように、各分銅はプラスかゼロかだったのですが、こちらの例だと

7 = 1*1 + 3*(-1) + 9*\1

のように、分銅を「マイナス」として使えるようになるというのがミソなんですね。これによって、最大40(すべての分銅を足した重さ)まで測ることができるようになるというわけです*1

といった数学関連の興味深い話が満載の本書、高校数学くらいの知識がある方にお勧めです。

情報量から考える天秤の使い方

問題はこんな内容です。

12枚のコインのうち1枚だけ、本物と少しだけ重さの違う偽コインが含まれている。 天秤を3回だけ使って偽コインと特定するにはどうすればいいか。

このパズルとその解はよく見かけるのですが、『情報数学のはなし』ではこれを情報エントロピーの観点から説明しているのが面白いです。

その説明を要約してみます。

(1)測定のパターンを洗い出す

左右で枚数が違うと意味がない*2ので、枚数は合わせます。1枚対1枚、2枚対2枚、・・・6枚対6枚、という6パターンがあります。

(2)各パターンで起きる事象と確率を整理する

たとえば2枚対2枚の時に発生する事象とその確率は、以下の通りです。

  1. 左が下がる。確率は2/12*3
  2. 右が下がる。確率は2/12。
  3. 傾かない。確率は8/12。
(3)各パターンで得られるエントロピーを計算する

n個の事象を対象にしたエントロピーは

H = p1*log(1/p1) + p2*log(1/p2) + ... + pn*log(1/pn)

なので、2枚対2枚のエントロピーは

H = (2/12)*log(12/2) + (2/12)*log(12/2) + 8/12*log(12/8)
= 0.43083 + 0.43083 + 0.38998
= 1.25163

このように整理していくと、エントロピー、つまり得られる情報が一番大きいのは、4枚対4枚を比べた場合で、1.584ビットであることがわかります。次点は3枚対3枚の1.500です。

(4)1枚を特定するためのエントロピーを計算する

コインが12枚、重さは本物より重いか軽いかの2つ、つまり12*2 = 24ケースから1つを特定する必要があるため、エントロピーは log224 ≒ 4.582ビット。 これを3で割ると1.527ビットで、これだけの情報量を稼げるのは4枚対4枚の測り方のみ*4

以上から、4枚対4枚の測定を3回行うことで、このパズルを解くことができるということになるわけです*5。「解ける」ことがわかっただけで、具体的な解法を示してくれるわけではないのが、また面白いところです。

まとめ

パズルは、直観で解けるものと論理で解けるものがあり、論理一辺倒のものはあまり好きではないのですが、情報数学で捉えるとまた違った様相を呈して面白いですね!
大村平さんの「はなし」シリーズは、どれも説明が平易かつ展開も独自で、楽しんで数学を学ぶことができる好著が多いです。ぜひ。

*1:かといって表現力が単純に34になるわけではない。1つも載せない場合は重さがゼロになって意味がなかったり、重複するケースがあるため。

*2:必ず傾くことがわかっているので情報量がゼロ。もちろん重さの差は、コイン1枚の重さより小さいことが前提ですね。

*3:偽コインが重く、かつ左に含まれる確率 = 1/2 * 2/12 = 1/12。 偽コインが軽く、かつ右に含まれる確率 = 1/2 * 2/12 = 1/12。 合わせて2/12。

*4:4枚対4枚を2回、3枚対3枚を1回でも4.670ビット稼げるので、この解もありうる・・・?

*5:この最後の部分が実は理解できていません。2回目の測定が1回目と独立でないと、1.584ビットを稼ぐことができないはずだけれど、独立した測定が3回できるかをどう確かめるのかがわからない。