まずはこのひなぶさんのツイートを見てくれ
あまりに唐突すぎたがそんなことはどうでもいい。
これを私は考えていた。講義中に。
素朴に考えれば7個あれば確実である。すなわち1,2,4,8,16,32,64gの分銅があれば二進数の考えで127gまでは測れる。
もちろんそんな単純な話ではない。とんちを効かせればもっと減らせるだろうことはすぐにわかる。
というわけで私はとんちを効かせようと頑張っていた。
で、閃いた。反対の更に置けばよいのではないか。
例えば片方に3g、もう片方に1gの分銅を置けば2gを測ることができる。
これを用いれば個数が減らせる…
さて、ここで数学的準備をしよう。
集合A_nをn個の自然数の集合とし、a_iをその元とする。(i=1,…,n)
また数列{b_i}についてb_i∈{-1,0,1}とする。
整数mに対し∃{b_i},m=Σ(i=1→n)(a_i)(b_i)を満たすとき
「mはA_nで表現可能」と呼ぶことにする。A_nで表現可能な整数の集合をS_nとしよう。
またX⊆Zとa,b∈Z,a＜bに対し∀m∈Z,[a≦m≦b⇒m∈Z]を満たすとき
「Zはaからbで整数上連続」と呼ぶことにする。つまりaからbまでの整数を網羅しているということだ。
連続、といっても一般の言い方的な連続であり数学における連続とは何ら関係のないことに注意する。
A_nで表現可能な自然数mについてmグラムは天秤で表現可能だ。
なぜなら分銅iをa_iグラムとしb_iの値に対し分銅iを
-1なら同じ側、0なら置かない、1なら反対側に置けばmグラムであるか判別可能だからだ。
さて、ここで以下の命題を証明しよう。
『a_i=3^(i-1)のときS_nは-[(3^n)-1]/2から[(3^n)-1]/2で整数上連続である。』
帰納法で示す。n=1のときは自明。
n=kで正しいとする。このときn=kのときを考える。
b_(k+1)=0とすれば-[(3^k)-1]/2から[(3^k)-1]/2で整数上連続であるためまずb_(k+1)=1のときを考える。
j∈S_kに対し(3^k)+jのとる値の集合は
(3^k)-[(3^k)-1]/2=[(3^k)+1]/2=[(3^k)-1]/2+1
(3^k)+[(3^k)-1]/2=[(2+1)(3^k)-1]/2=[3^(k+1)-1]/2より
S_(k+1)は[(3^k)-1]/2+1から[3^(k+1)-1]/2で整数上連続で
b_(k+1)=-1のときも同様に考えS_(k+1)は-[3^(k+1)-1]/2から-[(3^k)-1]/2-1で整数上連続
したがってS_(k+1)は-[(3^(k+1))-1]/2から[(3^(k+1))-1]/2で整数上連続であるためn=k+1でも正しい。
以上帰納的に示された。
これによりn個の分銅で[(3^n)-1]/2グラムまでは(分銅の重さが狂ってるとかの議論は別にして)正確に測れる。
というわけで120＜121=[(3^5)-1]/2なので最初の問題の答えは「5個」といえる。
分銅には3つの状態しかない(左右のどちらの皿に置かれてるかどちらにも置かれてないか)ため
測れる重さは高々3^n通りしかない。
しかしnグラムが測れるということは-nグラムも測れるため
0グラムを考え正のグラム数では[(3^n)-1]/2通りまでであるからだ。
そりゃもちろんこれ以上のとんちを効かせればあるんだろうが数学関係なくなってきそうだしパスしかしひなぶさん、どこからこの問題引っ張ってきたんだろう…
PR
