問題
上皿天秤で、とある物体Xの重さを分銅で計り取る。Xは1から40gの内から一個選ぶとする。どんなXでも測れる条件で、分銅の数を最も少なくしたい時、最低何個必要で、その時の分銅の重さはそれぞれ何グラム？

この問題、文章を読んだ段階でパッと理解できる人はどれくらいいるんだろう。
まあ、しょうがない。数学ってこういうもんだもの。この問題、筆者が中1の最初の方にしれっと出されたんだけど。
解き終わったら証明してみてとか言い出すし。

注意点: この記事はこの1つの問題について、説明、回答、解説、一般化、証明までやるクソ長記事だ。しかも一般的な無知識の人向けの解説で行う。加えて特段の盛り上がりなどない。
数学が本当に好きな人や、暇人と奇人だけが読むと良い。

証明って難しい？の前に何を言っているかわからない。

さて、解説だ。
この問題ポイントは以下の4つだ。

①上皿天秤は左右の重さが一緒の時釣り合う。だから、左右の重さが同じことがわかる。
②1g刻みのものを計りたいなら、同じ重さになる分銅の組み合わせが必要だ。
③重さが1gから40gまでわからないなら、全ての場合が必要だ。
④分銅の数に限りがあるなら、作れる組み合わせにも限りがあるはずだ。むしろもっと少ない時から作れる組み合わせを考える方が簡単そうだ。

ここまでで分からないことがあれば下の各説明を読んでも良い。
ただこの時点のことは、この問題を考える上で必要なことだし、まだ序盤だ。

①上皿天秤

上皿天秤というものは、いわゆる「はかり」だ。ただし、デジタルどころかメモリも無い。ただ左右に1つずつの「皿」があり、左右の皿に乗せた重さが同じ時だけ左右がつり合って、重さが同じことがわかる。だから何かの重さを計りたいときには、既に重さがわかっている「基準」が必要になる。その「基準」が分銅だ。

②分銅

天秤でものを測るときに使うのが分銅だ。理科の授業で、ピンセットで掴んだ円柱型のあれだ。分銅にはそれぞれ重さが書かれている。普通は分銅はセットになったものを買うだろう。というか理科室のでかい箱に入ったやつしか見たことない。
大体の場合100g、50g、10gが5個、5g、1gが5個、0.5g、0.1gが5個のようなセットが入っている。(この場合合計19個だ。多い)
これを適当に選んで皿に乗せ、天秤を釣り合わせる。乗せた分銅の重さを全部足して、反対側に乗せたものの重さを測るわけだ。
ということは分銅が足りなかったり、組み合わせが悪いといつまでも釣り合わなくて測れなくなるのだ。
今回の問題では、今みたいな1gと5gだけじゃなくて、3gとか13gみたいな中途半端な重さの分銅を買ってきても良いとするのだ。で、その数を少なくしてほしいらしい。

ちなみに左右の皿の両方に分銅を乗せる方法もある。計りたいものの上にも分銅を置いてしまう方法だ。置いた分銅の重さの差が、測るものの重さになるわけだ。
今回の問題ではこれを許すと問題が難しくなるので、あえてOKとする。(マジかよ)

条件1:　分銅は測る物体Xと同じ側にもおいて良い

③1g〜40gの全パターンが必要

さて、今回の問題では物体Xは1g刻みでどれか分からない。で、それを計れなければいけない。ちゃんと測るためには、どんな重さでもちょうど合わせられないといけないのだ。
例えば、どうやっても組み合わせの合計(左右の差)が13gにならないときは失敗だ。分銅が足りないか、重さが違う。

ちなみに今回は物体Xは全てピッタリ1g刻みだ。ということは、0.1gとかは必要ない。基本的に1g、2g…から分銅を選んでいくわけだ。
加えてもう一個裏技がある。
もし物体Xが、「22gより重く、24gより軽い」と分かったとする。当然この物体は23gになるわけだ。この要領でやればパターンが節約できそうな気がする。
ただ、今回はこの技を禁止する。何故かはあまり重要ではないが、実際問題Xが22gと釣り合っているか、少し重いかは微妙な差だ。(天秤は釣り合っても真ん中で停止したりしない。フラフラ加減が左右で一緒か、偏っているかを見るのだ。)この問題では誤差はないという仮定だが、現実的には「Xは22より重く23より軽い。どっちかというと22の方が偏りが小さい。だから22gってことで」という感じで測るからだ。
まあOKにしても良いのだが、作る組み合わせが2、4、6、8…となるだけで特に面白みもない。
ゴネてくるやつには0.5g刻みの重さを測らせてやれ。それで一緒になる。

条件2: 物体Xと分銅、天秤に誤差はないが、重さを測る際は必ず左右が釣り合っていること。Xは何グラムより重いとかは使っちゃダメ。

④少ない数でできる組み合わせ

1〜40gの分銅を全部揃えてから、これはいらないとかやるのは勿体無い。というか今の時点で41個は絶対いらない。
もちろん1個でムリなのは誰でもわかる。2個でもムリそうだ。
ただ、今回は40gまでという範囲に拘らなくて良い。
「分銅が何個の時、何グラムまで作れる。」というのが分かれば良いのだ。
これが分かっていれば、「何個かの時点から1個減らすと今より少なくて、何グラムまでしか計れなくなる」みたいなことが言える。だから最小はこれだ。と言えるわけだ。これが証明に必要なのだ。
例えば1〜40gの分銅が全部あれば40gまで測れるのはすぐわかる。でもこれが答えだとは言えない。本当に減らせない？と聞いてみれば40がいらないのはすぐわかる。1gと39gでできるからね。

ようやく事前知識が終わった
回答に入れる。ふう。

ここからは、シンプルに一気に回答が続く。
これは、多分中1の時の答えと多分一緒だ。

回答

分銅が1個の時、一つの値しか測ることはできない。常に1gから考えれば1gの分銅で1gが分かる。

分銅が2個の時
1gと1gを選んでみる。測れるのは、1gと2gだけ。
次に、1gと2gを選んでみる。1gと2gと3gが計れる。
次に、1gと3gを選んでみる。1gと3gは当然計れるし、4gも計れる。
問題は2gだ。ただ条件1を思い出せば、Xの反対の皿に3gを、Xと同じ皿に1gを置けば良い。この時釣り合えば、Xは2g。
だから1gから4gまで計れる。
これ以降、Xは常に同じ方に置くことにする。で、Xのある方を左、ない方を右と呼ぼう。
こうするとX+1=3てな具合にちょうどよく合う。もちろんX=2だ。

次に、1gと4gをえらぶ。
1、4、5はできるし、3もできるが、2だけがどうしても出来ない。だからこれはダメな例だ。
この後いろいろ試して見るがどれも4までのどれかが計れない。(2、3だと4がだめ。2、4だと1がだめ。1、6とか全然ダメ)
だから2個の時の答えは1gと3gの分銅で1gから4gまで計れる。

分銅3個の時
2個の時と同じようにすると途方も無さそうだ。
1gと3gがあれば1から4の組み合わせができることがわかっているので、これにもう一つ加えることにする。

では4gを加える。1〜4はもう出来ている。そのパターンに4gを追加すると5から8まで簡単にできる。だから、1、3、4で1〜8
次に5gの場合、同じ要領で１〜4と6から9 あと5は5gだけで良い。だから1、3、5で１〜9
次に6g。１〜4と７〜10と6、5は右に6gと左に1gでできる。だから1〜10
こんな感じで9まで進む
9gで1〜4と10〜13と9、
5から8が作れるかだが、そろそろ気付く。
1gと3gで1から4までできるのだから、
右側に9gを、おいて1〜4のバージョンの逆におけば-1〜-4ができて8〜5ができる。
だから1g、3g、9gで1か13までできる。
この後何をやっても上手くいかないので、9gで正解。(10gだと5gがダメ、11もやっても無駄)

さて分銅が4個の時、
1、3、9に何を加えるか考える。
たださっきの最後と同じで考える1、3、9だと要は、1〜13と何も置かない0、反対に置く-13〜-1
つまり-13〜13まであらわせる。
ここにちょうどいいのは、追加の1個を使って14以降をうまく表せる27だ(-13+27は14)
27を使うと、1〜40が表せる。

これが答えだから、
1g、3g、9g、27gの4つが1〜40を測るのに最少となる分銅の組み合わせである。

オワリ

はあ。疲れた

一応この段階で中1当時のマルはもらえると思う。
まあ確か中1当時はプリントがあって、ちょうど良い組み合わせを図で書いて試していたと思う。
だから全部やっていたわけじゃないと思う

でも後半に必要な発想は一緒。
例えば4個目を追加する時、
追加する前までの合計13までは当然表せる。そこから今までのをマイナスに使って14を表すために
13+13+1で27が出てくる。
この27に今までの組み合わせで27+13=40まで表せる。この発想は次でも同様に使える。

一般化への道

実際に教科書にはもう一個あればどこまで計れるか？という追加の問題があった。
まあ同じようにやれば良いだけだ。
4つまでの合計は40だった。
だから次に必要なのは40+40+1=81だ
で合計81+40=121まで表せる。

ちなみに6個目は(計算を省略するが)243gで364gまで。7個目は729gで1093gまでだ。

これ、もっと簡単に表せないだろうか。
要は同じ計算するだけなんだから。

文字の使用

ここで今までの合計を$${S}$$と書くことにしよう。(合計の英語Sumの頭文字だ)
この時次の分銅は、$${S+S+1=2S+1}$$ だ
これで$${2S+1+S=3S+1}$$まで表せる。

こんな感じで増えていくわけだ
(ちなみに高校数学をやった人は覚えているだろう。漸化式だ。もちろん中学では習っていないし、そもそも数列の概念がないから、n個目までの合計とかは使わなかった。)

これでもう完璧だ。何個までも計算できる。
と思った矢先。

「証明してみて。」
、
、
、
、
「は？」

さて中学校1年生に初めて課せられた、
「証明の問題」だ。

・証明って何？
・どうすればいいの？
・何をすれば正解？
ハテナしか浮かばなかったし、3日考えたが結局分からなかった。まあ、その内忘れてしまったわけだ。
その後高校生の時に何故か思い出し、納得いくまで証明し切った記憶がある。(その頃はもっと簡単な証明になれていたしね)

とにかくその日に夜に考えていたことを書いていこう。

よく見ると、分銅の重さって3倍ずつだなあ。
何でだ？これを証明すれば良いのか？

計算で、やっていたことは、$${2S+1}$$と$${3S+1}$$だった。
何故これが3倍ずつになるのか考えて見る

まず1個目、1だ。これは3倍がどうとか関係ない。ただのスタートだ。まず1から始まるだろ？って感じ。(高校数学の数列ではこれを初項とよんでaで表す)

次、2個目、2個目は$${2S+1}$$だから3なわけだが、これが3の倍数の理由かと言われるとハテナ？なわけだ。

次の、3個目は$${2S+1}$$だ。
このSには1個前の合計の$${3S+1}$$が入るから
$${2(3S+1)+1}$$ってことだ。ここでの$${S}$$はあくまで1個前の$${S}$$だ。(これ番号つけないとわかんなくなるな、2個目までの合計は$${S_2}$$、3個目の合計は$${S_3}$$てな具合にしよう。ついでに分銅もおんなじ感じで、$${a_1}$$、$${a_2}$$だ。)
つまり、$${a_3=2S_2+1=2(3S_1+1)+1}$$
でこれは計算できて、$${a_3=6S_1+3}$$だ。ここで最近習った因数分解を思い出した。$${a_3=6S_1+3=3(2S_1+1)}$$だ。
これ、$${a_2=2S_1+1}$$だよな
ということは、$${a_3=3×a_2}$$だ
次の分銅は、一個前の分銅の3倍だ。

あれ、これ、ずっと続くじゃん。てことは、1から始まったら1、3、9、27…あ一緒だ。
できた！

一体何ができたんだ？

中1当時の筆者はこの「できた！」感に満足して考えるのをやめたが、実際証明はできたのだろうか？
もちろん答えは「NO」だ。
じつはこれでやったことは、
「初項1、漸化式$${a_{n+1}=2S_n+1}$$」
の数列の一般項を求めただけだ。
もちろん、一般項$${\{a_n\}=3^{n-1}}$$だ。
実際の問題では漸化式に数字を代入していたせいで、直ぐに3倍になっていることに気がついたというわけだった。
ちなみに、この数列のn個目までの合計は$${(3^n-1)/2}$$である。

証明とは何か

ここで証明とはなにか、本当にやりたかったことは何か言っておこう。

「この問題で、分銅の重さが一般項{a_n}=3^(n-1)となるときの組み合わせであるとき、
1gから計量範囲の限界Mまでくまなく計量が可能であること、
また(3^(n-1)-1)/2< M ≦(3^n-1)/2 となるようなnが最小の分銅の個数であることを示せ」
だろう。

要は中1の時の解き方は、「なんかこれやってみた。多分あってる。」なのだ。
nに数字を入れてみたら確かにできはするが、証明されてない。証明したつもりで、ただ答えを書いただけだ。

照明の難しさとはここにあると言える。
答えが合っているだけではダメで、
他にパターンがないか。例外はないか。
これ以外に何もないか、ちゃんと答えを網羅しているか。問題文に答えれているか。
全ての途中式を書き記さないと証明したことにはならないのだ。

ここまで長く書いてきたがそろそろ証明しよう。
因みにこの証明には、数列の知識、組み合わせの知識がいる。要は高校数学レベルだ。

証明

それぞれの重さの分銅がn個合った時、それぞれの重さを$${\{a_n\}=\{a_1,a_2,…,a_n\}}$$と書くことにする。ここで$${a_1≦a_2≦…≦a_n}$$とする。
(要は重い順に名前をつける。)
分銅は、それぞれ右に置くか左に置くか置かないかの選択肢がある。
$${i}$$番目の分銅を
右に置く時$${c_i=1}$$、
左に置く時$${c_i=-1}$$、
置かない時$${c_i=0}$$としよう。
すると　$${X=c_1a_1+c_2a_2+…+c_na_n}$$となる。

この時$${\{a_n\}}$$がどんな時でも、Xのパターンの数は$${\{c_n\}}$$のパターンの数以上には取れない。
ここで$${\{c_n\}}$$のパターン数は分銅一個ずつ全てに-1、0、1の3パターンがあるから$${3^n}$$になる。

ただし、注意しないといけないのが、分銅を何も乗せない時(cが全部0、X=0)や左側に傾いている時(X<0)もあるわけだ(全部左に乗せたら絶対左に傾く)
ただ、乗せ方には対称性がある。
つまり、
とある置き方$${X_m=m}$$になるような$${\{c_n\}}$$の組み合わせ$${\{c_{m,n}\}=\{c_{m,1}、c_{m,2}…\}}$$に対して$${\{c_{-m,n}\}=\{-c_{m,1}、-c_{m,2}…\}}$$となる組み合わせが$${3^n}$$の中に必ずある(全部0の場合を除く)
(例えば、$${\{a_n\}=\{1,3,9,27\}}$$に対する$${\{c_{19,n}\}=\{1、0、-1、1\}}$$には$${\{c_{-19,n}\}=\{-1、0、1、-1\}}$$がある。)
そして$${\{c_{-m,n}\}}$$となる
$${X_{-m}=-c_{m,1}a_1-c_{m,2}a_2…c_{m,n}a_2=-X_m=-m}$$である。
そのため、仮にひとつの$${X}$$が$${X_m≧0}$$ならば$${X_{-m}≦0}$$であるし、
$${X_m≦0}$$ならば$${X_{-m}≧0}$$となる。

つまり$${3^n}$$通りの$${X}$$の中には0が一つあり、
残りの$${3^n-1}$$通りの$${X}$$の半分は$${X≧0}$$、もう半分は$${X≦0}$$である。

したがってどのような$${\{a_n\}}$$を取ろうとも、Xが1gから順に増えていくパターンは、最大で$${(3^n-1)/2}$$しか取れないことがわかる。

よってこのようなパターンが作れるならば、問題の「$${(3^{n-1}-1)/2< M ≦(3^n-1)/2}$$となるような$${n}$$が最小の分銅の個数であることを示せ。」は完了だ。

そして残りの問題は、「Xが順に増えていき最大が$${(3^n-1)/2}$$となるパターンは作れるのかどうか」と「そのパターンは何か」だ
(というかもう問題に書いてある通り、それは$${\{a_n\}=3^{n-1}}$$でOKではあるのだ。あとは、これを導けばよい)

で、残りの証明は、数学的帰納法を使って見る。作れるかどうかは、一個出来た状態から、いつでももう一個できるのなら、いつまででもできるのだ。

分銅がk個ある時、Xは1gから$${(3^k-1)/2}$$まで表せたと仮定する。ここで$${(k≧1)}$$
ここに重さ$${a_{k+1}}$$である$${k+1}$$番目の分銅を加えるとする。
元々$${k+1}$$番目の分銅がなくとも、
Xは$${-(3^k-1)/2〜(3^k-1)/2}$$までの$${3^k}$$個のパターンが表せる。(何故なら$${1〜(3^k-1)/2}$$までを表す$${1}$$個ずつの$${X_i}$$に対応した$${X_{-i}=-X_i}$$が存在するからだ。そして合計$${3^k}$$個しか表せないので、逆にこれ以外は表せない)

ここで$${a_{k+1}=3^k}$$とすると、
$${k+1}$$番目の分銅を使う場合にも、
他の分銅を使ったパターンには$${-(3^k-1)/2〜(3^k-1)/2}$$があるので
$${3^k-(3^k-1)/2}$$から$${3^k+(3^k-1)/2}$$まで表せる。
これはそれぞれ通分すると、
$${(3^k+1)/2}$$から$${(3×3^k-1)/2}$$まで、
つまり
$${(3^k-1)/2+1}$$から$${(3^{k+1}-1)/2}$$まで表せることになる。
$${k+1}$$番目を使わない場合と合わせて、
$${k+1}$$個の分銅を使って、
1gから$${(3^{k+1}-1)/2}$$まで表せることになる。

よってk番目までで成立していれば、$${a_{k+1}=3^k}$$として$${k+1}$$番目でも成立する。

また、n=1の時、$${a_1=3^{(1-1)}=1}$$とすれば、
$${1}$$gから$${S_1=(3^{(1-1)})/2=1}$$gまで成立している。

よって数学的帰納法により、n=1から始めてどこまでも、$${\{a_n\}=3^{n-1}}$$で成立する

証明終了

なんて長い証明だ。(6925字)