天秤で1～1000gを判定する分銅の最小個数は？【解説】
問題はこちら：
答え：1,3,9,27,81,243,636gの7種類の分銅を一つずつ（一番重いのは636～729gの範囲ならOK）※これ以外もあり
1～1000gのどれかの重さを持った箱は、実は上の7種類の分銅だけでその重さを天秤で判別する事が可能です。7種類の重さの配分は色々とありますが、最低が7個なのは変わりません。重さは1g単位で1000種類もあるのに、たった7個の分銅でそれを測定できるというのは信じ難いのですが、分銅をうまい事皿に乗せる事で可能なんです。詳しく解説します。
解説1：分銅の「左右の重さの差」に注目しよう
天秤は小学校の理科の授業で出てきます。左の皿に測りたい物を乗せて、右の皿に分銅を釣り合うように乗せる。釣り合った時の分銅の重さを足し算すると測定値となります：
ただ、ちょっとここでこういう事を考えてみます。今上図のように左に測定したい箱を、右に2gと5gの分銅を一つずつ乗せて釣り合っているとします。つまり箱の重さは7gです。この状態で左右に3gの分銅を1つずつ乗せます：
左の皿に分銅を乗せてはいけないとは問題に記載していません。そして、当然これでも天秤は釣り合いますよね。
通常分銅は右の皿にだけ乗せるので「分銅の合計＝測定値」なのですが、左の皿に分銅を乗せるとそれは引き算する必要があります。すなわち「右の分銅の合計 - 左の分銅の合計＝測定値」です。
実際上の例だと、右の皿には2,5,3gの分銅があるので+10g。左の皿には3gの分銅があるので-3g。双方を合計すると10-3=7gでちゃんと箱の重さになりますよね。
この左右の分銅の差が測定値そのものになるので、以後その差に注目する事にします。
「でも左に分銅を乗せる意味ってなくない？使う分銅の個数が増えるだけじゃん。」
そう思うかもしれませんが、これが今回の問題の鍵になるんです。具体的な解説に進みます。
解説2：重さの差のパターン
1gの分銅の乗せ方は3パターン
今分銅はg単位なので、1gの箱を測るには1gの分銅が絶対1つ必要です。そりゃそうだって話です(^-^;。なので必要な最初の分銅は1gであると確定できます。
解説1の話にあるように、分銅は左右どちらに乗せても別に構いません。そこで1gの分銅1個の乗せ方のパターンを列挙してみましょう：
重さの差を「右の皿の分銅 - 左の皿の分銅」と定義し、1gの分銅でできる重さの差のパターンを考えると、{-1g、0g、1g}の3つある事がわかります。分銅を乗せないというのも一つのパターンである事を忘れずに。
1gの箱も別に右左どちらに乗せても構わないわけですが、上のように置き方のパターンは左右対称であるため、箱は左側だけに乗せるとしましょう。
そうするとこの中で釣り合うのは下の+1gパターンしかありません。また2g以上の箱はどう足掻いても釣り合いを取れません。よって1gの分銅で判定可能なのは1gの箱のみで、1パターンのみとなります。
2つ目の分銅は”3g”が美しい
2g以上の箱を判定するには2つ目の分銅が必要です。その分銅の重さをx(g)と仮にしておきます。2つの分銅の置き方のパターンは、
この9通りです。ここで表を上中下の3段に分けると特徴が見えてきます。太文字で示した真ん中はx(g)の分銅を皿に置いていません。つまり1つ目の1gの分銅のみで作れる3パターンになっています。そして上下は真ん中のパターンにx(g)の分銅を左右に置いた3パターンになっています。
x(g)に具体的な分銅の重さを入れてみます。例えばx=1gとすると、
こうなります。差の項を見ると-2g～2gまで1g単位で揃っていますので、1gと2gの箱を測定できる事が分かります。でも測定値の重複が多いですよね。{-1,0,1}gがそれぞれ2つ出てきてます。
ではx=2gならどうでしょう？
今度は-3g～3gまで揃っています。1gの分銅2つより判定の幅が±1g分広がり、1g、2g、3gの箱を判定できます。ただ良く見ると-1gと1gが2個ずつあります。惜しい…
そこでx=3gにすると…
差の項が-4g～4gまできれいに揃っています！美しい！つまり1gと3gの2つの分銅を左右に振り分けると-4g～4gまでの9通りの重さの差を重複なく作りだせて、1g～4gの箱を判定できるんです！3gの分銅が2つ目の分銅として最適かつ唯一です。
xを4g以上にしてしまうと測定幅は広がりますが測定できない重さが出てきてしまいます。例えばx=4gだと2gの箱が測れなくなりますよね：
よって2つの分銅で1g単位を測る時、パターンが最大になるのは1g、3gである事がわかりました。
解説3：追加する分銅は3のべき乗g
1gと3gの分銅で5g以上の箱は判定できません。3つ目の分銅が必要です。何gの分銅が理想的でしょうか？
1gと3gの分銅では-4g～4gの9パターンを1g単位で綺麗に作れました。ここに3つ目の分銅を加える時、その分銅は左右のどちらかに乗せる事になります。という事は3つ目の分銅の重さをx(g)とすると、新たに
{-4g～4g} - x(g)
{-4g～4g}
{-4g～4g} + x(g)
という27パターンができる事になりますよね。
+x(g)の方に注目すると、今1gと3gの分銅で-4g～4gを1g単位で作れるのですから、一番小さい-4gに足し算して+5gになる分銅を用意すると5g以降の重さも1g単位で作れる事になります。つまりx=5-(-4)=9gです！これは-x(g)側も対象的なので同様です。結果として、
{-4g～4g} - 9(g) ⇒ {-13g～-5g}
{-4g～4g}
{-4g～4g} + 9(g) ⇒ {5g～13g}
このように-13g～13gまでの27パターンを重複なく測定できます。
3のべき乗gの分銅
1つ目は1g、2つ目は3g、そして3つ目は9g。この並びは明らかな特徴があります。3のべき乗です。実は4つ目以降の分銅もこのルールで最適となります。なぜでしょうか？
n個の分銅でできる皿の乗せ方のパターン数は、
です。例えばn=2の時、1つ目の分銅が「左」「乗せない」「右」の3パターンで、それぞれに対して2つ目の分銅も「左」「乗せない」「右」の3パターンが組み合わされるため上式のようにべき乗になるわけです。
n=1の時、パターン数は3つで{-1,0,1}gでした。0を真ん中にして左右対称で1g単位で数字が並んでいます。n=2の時のパターン数は9ですが、2つ目の分銅を使わない3パターンを軸としてn=1のパターン数と同じ重さ3g分だけプラスマイナスすれば、-4g～4gまで9パターンを新たに作り出せます：
{-1,0,1}g - 3g ⇒ {-4,-3,-2}g
{-1,0,1}g
{-1,0,1}g + 3g ⇒ {2,3,4}g
n=3も同様で、n=2でできる-4g～4gの9パターンに対し、n=2の時のパターン数と同じ重さ9gをプラスマイナスすれば-13g～13gまでやはり綺麗に揃えられるんです。
{-4～4}g - 9g ⇒ {-13～-5}g
{-4～4}g
{-4～4}g + 9g ⇒ {5～13}g
これ以降のnでも同じルールで最適分銅を決められます。この事は数学的帰納法を使って証明できますが、そこまでしなくても上のパターンが続けられる事はイメージできますよね。
揃えた分銅で測定可能な最大の重さは、すべての分銅を右に乗せた時なので単純に分銅の合計です。ここまででおぜん立てが全て揃いましたので、今回の問題に適用してみましょう。
解説4：1000gを超えるまで3のべき乗を足していく
用意する分銅は3のべき乗gであり、最大測定重量は分銅すべての和です。よって3のべき乗gの分銅を全部足し算して1000gを超えれば1g～1000gまで1g単位で測定できます。この範囲なら手計算でも十分可能でしょう：
このように7つ目の729gを用意した段階で合計が1093gとなり1000gを超えます。ここから上の7種類の分銅を1つずつ用意すれば1g～1000gまで1g単位で測定できる事がわかりました！
ただ、上の729gの分銅だと1093gまで1g単位で測れるのですが、今回の問題は最大1000gまでで構わないので、一番重い分銅は合計がぴったり1000gになる636g（1000g - 364g）以上の分銅でも構いません。よって一番重い分銅は636g～729gのどれかでOKです。
3のべき乗でなくても良い
実はもっと突っ込むと、最大以外の分銅も重さを減らす余地があります。例えばn=6の分銅を242gと1g減らすとn=1～6の合計が363gになります。これは重複が起こりますが{-363～363}gまでの727パターンが揃っているので、n=7の分銅をパターン数と同じ727gにすると1g～1090gまで測定可能になるんです。
でもどれでも可能というわけでもありません。n=2を3gじゃなく2gにした場合、合計は3gで、n=3は3×2+1=7gとなります。この計算はより大きい分銅に伝播しパターン数を狭めていきます：
上の場合n=7でも合計が850gとなり1000gに届きません。よってn=2が2gは選択できないのが分かります。興味があれば表計算ソフトやプログラムなどで可能な分銅パターンを作ってみて下さい。
深堀1：1g～地球の重さ（6×10^27g）を1g単位で測る分銅の個数は？
さ、ここからは深堀です。今回の問題は最大1000gでしたが、もっと重い物、それこそ地球の重さの概算である6×10^27(g)までを1g単位で測るという奇想天外な規模にした場合、分銅は何個必要になるでしょうか？
6×10^27(g)をあえて数字で書くと6000000000000000000000000000(g)です。しかも今求められているのは6×10^27(g)を測るのではなくて、1gから6×10^27(g)までを1g単位で測定するというネジがぶっとんだ条件…。何桁の個数になるかもわからない凄まじい数の分銅が必要に感じますが、実際どうでしょうか？
ここまで解説してきたように、用意する分銅は3のべき乗gが最適なのでした。そして測定可能な最大の重さはすべての分銅を足した重さでした。用意する最適分銅の個数をnとし、その合計をSnとすると、
こういう式で表現できます。これは高校数学で習う初項1、公比3の等比数列の和です。つまり、
と計算式を作れます。
今は上式の左辺が地球の重さの時のnを知りたいわけです。そこで式を変形して逆関数にしてみましょう：
底が3の対数を使う事で個数を知る式ができました。右辺のSnに6×10^27(g)を入れればnが出てきます。もちろん計算機などで直接計算しても良いですが、ちょっとだけ工夫しましょうか。
今Snは地球の重さで値が極めて大きいため2Sn+1の「+1」はもうほぼ誤差です。なのでそれを取り除いてしまい、上式を変形すると、
こう表せます。第2項を底を10の対数に変換すればSn=6×10^27(g)を代入した時に便利そうですよね。実際入れてみます：
という事で、n=58.85個で丁度地球分なのでそれを超える個数、すなわちn=59個の3のべき乗gの分銅を用意すると1g～6000000000000000000000000000(g)までを1g単位で測定できます！
これ、ちょっと凄いと思いませんか？1円玉でも、車でも、山でも、海水全部でも、地球上の人全部でも、そして地球でも、1g単位という条件はありますが、それをたった59個の分銅の組み合わせでばっちり測定できるって事です！（もちろん理論的にという話ですが）
では地球じゃなくて太陽系で一番重い天体である太陽ならどうでしょう？太陽の重さの概算値は2×10^33(g)だそうです。先の式のSnにこのとてつも無い重さを突っ込んでnを求めると、
n=71個の３のべき乗gの分銅を用意すれば良い事が分かります。太陽の重さまでを高々71個の分銅の組み合わせだけで1g単位で測定できるというのはにわかに信じがたいのですが、数学的には間違いありません。太陽系には太陽より重い天体や物体はありません。つまり71個の分銅により太陽系のあらゆるものが1g単位で測定できてしまうんです！
深堀2：測定手数の最適化
3のべき乗gの分銅を使う事で思っているよりずっと少ない個数で非常に幅広い測定ができる事がわかりましたが、ここで問題なのは「測定手数」。皆さんも小学校の時に分銅を使う際面倒に感じませんでしたでしょうか？
宇宙を何度繰り返しても測定が終わらない…
測定する重さが既知ではないので一発でその重さと釣り合う分銅を用意することは普通できません。そこで分銅を入れ替え差し替えして釣り合いそうな重さを検討しなくちゃいけなくなります。分銅の個数が少なければパターンも限られますが、先の地球の重さまでを1g単位で測定できる59個の分銅の場合、無策でやるととんでもない事になります。
例えば1g,2g,…と順番に測定していくと最悪6×10^27回測定が必要です。1回の測定に1秒かかったとしても最悪6×10^27秒。これは計算してみると約10^20年くらいでした。これがどれほどの時間なのか？宇宙が誕生してから今までは138億年ほどとされていて、これはざっくり10^7年くらいです。とすると、10^20年はその10兆倍…。途方も無いなんて次元の話ではありません。せっかく1g単位で測定可能な天秤があるのに、最悪ただの1回も現実時間で測定できないのでは本末転倒です。
2分法の凄まじさ
そこで2分法を採用します。最初に天秤の限界測定値（すべての分銅の合計）の半分の重さが右皿にかかるような分銅の組み合わせを天秤にセットします。そして測定したい物は左の皿へ。これで右皿側に傾けば測定物はその半分の重さよりは軽い事になります。逆もしかりです。今仮に測定物が軽かったとすると、この段階で半分より重い測定をする必要が無くなります。10^20年が一気に5×10^19年に減りました。この表記だとピンときませんが、このたった1回のテストで例えば1000年だったのが500年と半分に短縮できるのですから凄まじいショートカットです。
試す残りは1g～最大測定値の半分です。これもまたその真ん中になる重さの分銅セットを作り、左の測定物を測ります。測定物の重い軽いによってまた半分のテストパターンがごっそり削れます。これを続けると測定しなくて良いテストパターンが都度半々に減っていくわけです。
運が良ければどこかのタイミングで釣り合う重さが見つかりますが、最悪残りテストパターンが2個まで減る事もあるでしょう。つまり最悪な測定回数は測定可能な最大の重さを何度2で割れるかで求められる事になります。例えば最大が32gだったら、2^5=32なので最悪5回測定すれば釣り合う重さが必ず見つかります。
最大である地球の重さ6×10^27(g)は2で何回割れるのか？これは、
を満たすnを求めれば良いですよね。実際計算すると、
つまり93回で済むんです！宇宙が何度繰り返しても終わらない測定回数が、たった93回にまで激減しました。2分法の凄まじさを痛感です。
これであれば1回の測定に1分かかったとしても1時間半後くらいには重さが判明しています。測り方を工夫すれば、宇宙を何度も繰り返す必要は無いんです。
深堀3：バシェの功績とフェルマーの最終定理
今回の問題は元があります。それはフランスの言語学者であったクロード＝ガスパール・バシェ・ド・メジリアクが1612年に出版した「楽しくて面白い数の問題（Problèmes plaisans et delectables qui se font par les nombres）」内にある分銅問題です：
今から400年以上前にバシェが出した元の問題は「1g～40gまでを1g単位で測定するには分銅を何個用意すれば良いか？」というものでした。ここまで解答の説明を読んだ皆さんならもう即答だと思いますので答えを言うと1g,3g,9g,27gの4つです。これで丁度1～40gまで測定できます。今回の問題はその本質的な面白さ（測定物の最大重量に対して実は必要な分銅がうんと少なくて良い）を知ってほしかったため、これを1000gまで拡張しました。
バシェは言語学者でありがながら数学のパズル的な側面にとても興味を持っていたようで、数学に関連する書籍の翻訳も行っています。そのパシェが手掛けた翻訳の一つがディオファントスの「算術」のラテン語翻訳で、この翻訳本があのフェルマーの手に渡りました。フェルマーはそれを片っ端から読み解いていき、さらに各問題を改変したり拡張した問題を作って楽しんでいました。その過程で書籍にあったピタゴラスの定理、
を一般化した、
を作り、「これを満たすn≧3以上の自然数は存在しない、その証明を書くには余白が狭すぎる」というあの超有名な定理（予想）である「フェルマーの最終定理」をその書籍に書き残したんです。フェルマーの死後この記述を発見した人類は、以後350年間もこの誰もが理解できる簡単な式の証明に苦しめられる事になります。
3世紀の偉人であるディオファントスが著した「算術」。原本のギリシャ語版は全13巻あったのですが、4世紀に起きたアレクサンドリアの戦禍により7巻が消失、残り6巻がヨーロッパに渡り、16世紀にバシェなどの翻訳家によりラテン語などに翻訳され広まったそうです。残った6巻の中にピタゴラスの定理があった事、それをパシェがラテン語に翻訳してくれた事、その時代にフェルマーがいて、その書籍が彼の手に渡った事、色々な事象やタイミングが重なってフェルマーの最終定理がこの時代に生まれたんです。そして350年後、それを数学者アンドリュー・ワイルズが苦難の上に証明するのですから、何とドラマチックな事でしょうか。
数学にはそういう奇跡的なめぐり合わせによって生まれたり証明されてきたものが沢山あります。ビビパズの数学パズルを通してまた紹介できればと思います。
ではまた(^-^)/