Weekend Mathematics／問題／問題52
５２．上皿天秤の問題
上皿天秤で１ｇから４０ｇまで１ｇきざみではかりたいのですが、 そのためには、４種類の分銅で充分です。 さて、その４種類の分銅の重さを答えてください。
数学パズル／沖田浩／中経出版
（ペンネ−ム：数学がとっても大好きな新潟県民）
２進法で考えると、 １ｇ、２ｇ、４ｇ、８ｇ、１６ｇ、３２ｇ の６種類で ６３ｇまで量れる。
これは、２のＮ乗（Ｎ＝０，１，２，３，・・・・・）の値となる。
この２を３にしてＮ乗（Ｎ＝０，１，２，３，・・・・・）すると、１ｇ、３ｇ、９ｇ、２７ｇとなる。
この４つの分銅の重さの合計は４０ｇとなる。
２ｇは ３−１
５ｇは ９−（１＋３）
６ｇは ９−３
７ｇは （１＋９）−３ ・・・・・・・・・
というふうに１ｇから４０ｇまでの重さを量ることができる。
（答） １ｇ、３ｇ、９ｇ、２７ｇ
（ペンネ−ム：けんたん）
（解答）４種類の分銅の重さをそれぞれＡ，Ｂ，Ｃ，Ｄ（０＜Ａ＜Ｂ＜Ｃ＜Ｄ）とお
くと、Ａ，Ｂ，Ｃ，Ｄの係数は−１，０，１の３種類のため８１通りの数式ができ
る。
ここで、数式の最大値はＡ＋Ｂ＋Ｃ＋Ｄ、最小値は−Ａ−Ｂ−Ｃ−Ｄとなり絶対値は
等しい。
よって、Ａ＋Ｂ＋Ｃ＋Ｄ＝４０
数式の値が３９となるのは、次に大きい数式Ｂ＋Ｃ＋Ｄしかあり得ない。
∴Ｂ＋Ｃ＋Ｄ＝３９ ∴Ａ＝１
∴３８＝３９−１＝Ｂ＋Ｃ＋Ｄ−Ａ
数式の値が３７となるのは、次に大きい数式Ａ＋Ｃ＋Ｄしかあり得ない。
∴Ｂ＝（Ａ＋Ｂ＋Ｃ＋Ｄ）−（Ａ＋Ｃ＋Ｄ）＝４０−３７＝３ ∴Ｃ＋Ｄ＝３６
∴３５＝３６−１＝Ｃ＋Ｄ−Ａ
∴３４＝３６−３＋１＝Ｃ＋Ｄ−Ｂ＋Ａ
∴３３＝３６−３＝Ｃ＋Ｄ−Ｂ
∴３２＝３６−３−１＝Ｃ＋Ｄ−Ｂ−Ａ
数式の値が３１となるのは、次に大きい数式Ａ＋Ｂ＋Ｄしかあり得ない。
∴Ｄ＝（Ａ＋Ｂ＋Ｄ）−Ａ−Ｂ＝３１−１−３＝２７ ∴Ｃ＝９
よって、４種類の分銅の重さは１ｇ、３ｇ、９ｇ、２７ｇ
（ペンネ−ム：kiyo）
１ｇ、３ｇ、９ｇ、２７ｇの４種類の分銅です。
| １ | ２＝３−１ |
| ３ | ４＝３＋１ |
| ５＝９−（３＋１） | ６＝９−３ |
| ７＝（９＋１）−３ | ８＝９−１ |
| ９ | １０＝９＋１ |
| １１＝（９＋３）−１ | １２＝９＋３ |
| １３＝９＋３＋１ | １４＝２７−（９＋３＋１） |
| １５＝２７−（９＋３） | １６＝（２７＋１）−（９＋３） |
| １７＝２７−（９＋１） | １８＝２７−９ |
| １９＝（２７＋１）−９ | ２０＝（２７＋３）−（９＋１） |
| ２１＝（２７＋３）−９ | ２２＝（２７＋３＋１）−９ |
| ２３＝２７−（３＋１） | ２４＝２７−３ |
| ２５＝（２７＋１）−３ | ２６＝２７−１ |
| ２７ | ２８＝２７＋１ |
| ２９＝（２７＋３）−１ | ３０＝２７＋３ |
| ３１＝２７＋３＋１ | ３２＝（２７＋９）−（３＋１） |
| ３３＝（２７＋９）−３ | ３４＝（２７＋９＋１）−３ |
| ３５＝（２７＋９）−１ | ３６＝２７＋９ |
| ３７＝２７＋９＋１ | ３８＝（２７＋９＋３）−１ |
| ３９＝２７＋９＋３ | ４０＝２７＋９＋３＋１ |
（ペンネ−ム：Chee）
「４種類の分銅で充分です。」と言われると、１種類で充分！と答えたくなる
（１ｇの分銅を４０個用意すると、種類としては１種類．．．）
のですが、異なる重さの分銅を４つという意味ですよね？ m(_ _)m
まず、１つは１ｇとして、次に２ｇが計れるようにするには、３ｇを用意すればＯＫ！
１ｇと３ｇで．．．
１ ＝ １
２ ＝ ３ − １
３ ＝ ３
４ ＝ ３ ＋ １
１ｇ〜４ｇまでできた。
さてと、５ｇ以上を計れるようにするには、９ｇを用意すれば（１ｇ〜４ｇまではできているので）
５〜８ ＝ ９ − （４，３，２，１）
９ ＝ ９
１０〜１３ ＝ ９ ＋ （１，２，３，４）
これで、１３ｇまでできた。
同じように、１４ｇ以上を計れるようにするには、２７ｇを用意すれば、（１ｇ〜１３ｇはできているので）
１４〜２６ ＝ ２７ − （１３，１２，１１，...，３，２，１）
２７ ＝ ２７
２８〜４０ ＝ ２７ ＋ （１，２，３，...，１１，１２，１３）
おぉ！ちょうど４０ｇまでできました。 (^_^)v
でも、この回答って、やってみたらできたって感じ。
これ以外の回答はあるのかな？
（ペンネ−ム：judas）
1g, 3g, 9g, 27g の四つで大丈夫なハズです。
どうやって証明しよう・・・？
下から考えることにすると、まず1gの分銅を用意する。
すると次の2gを計るには2gがあってもよいが、3g-1gでも2gが計れる。
従って、まず1gと3gが必要になる。
このように、必要最低限の分銅の重さを決定していくことを考える。
まず、この2つの分銅で合計1〜4gまで計ることができる。@
すると、次の分銅の重さをAgとした場合、その3つの分銅で1〜(1+3+A)の重さが計れ
るようにしなければならない。
このとき、1gと3gの分銅で4gまで計れるから、A〜(A+4)の重さもこの3つで計ること
ができる。A
また、(A-4)〜Aも引き算によって計ることができる。B
言いかえると、この1g、3g、Agの分銅では1〜4、(A-4)〜(A+4)の範囲しか計ることが
できない。
Aの値によって(A-4)〜(A+4)の範囲は変動するから、1〜(A+4)の範囲をもれなくカ
バーするには4〜(A-4)の範囲に穴が開かないようにしなければならない。
従って、A-4は4の次の値（つまり4+1)、すなわちA-4=5であることが必要である。C
∴A=9
これを数列で表してみる。
1gからもれなく計るのことのできる組み合わせの分銅のうち小さい方からn個目の分
銅をa(n)とあらわす。
上記よりa(1)=1、a(2)=3、a(3)=9となる。
a(3)を上で出したときのように考えると、a(1)からa(n)が決まっているとき、a(n+1)
との関係を式にすると、
a(n+1)-[a(1)+a(2)+.....+a(n)]＝[a(1)+a(2)+.....+a(n)]+1 （Cより）
移項すると、
a(n+1)=2×[a(1)+a(2)+.....+a(n)]+1となる。
以上により、1g, 3g, 9g, 27gの重さがあれば40gまで1gきざみで計ることができる。
＃＃＃＃
この問題の解答としてはこれでいいかと思いますが、この解き方が一般的に必要最小
限かどうかってのはわからないですよね？
一番小さい分銅を1gとした場合にはこれでいいとは思うのですが、もし一番小さい分
銅を2g以上のものにした場合、
最初を1gにした場合より効率的に、つまり個数を少なくできる組み合わせができるこ
とはないとの証明にはなっていないんですよね。
この証明って存在するんでしょうか？
＃＃＃＃
以前疑問に残った、一般化して考えたときに他により効率的な方法（より少ない分銅
で同じ範囲を計ることができる、あるいは同じ数の分銅でより広い範囲を計ることが
できる）はない、ということを証明できたと思います。
a(n+1)=2×[a(1)+a(2)+.....+a(n-1)+a(n)]+1 D
同様に、
a(n)=2×[a(1)+a(2)+.....+a(n-1)]+1
これを変形すると
a(1)+a(2)+.....+a(n-1)=1/2×[a(n)-1] E
EをDに代入すると
a(n+1)=2×[1/2×[a(n)-1]+a(n)]+1=a(n)-1+2×a(n)+1=3×a(n) F
従って、この選び方では初項1、公比3の等比数列となり、
n個目の分銅はa(n)＝3n-1、
n個の分銅で計ることができる上限すなわち総和はSn=1/2×[3n-1] G
と表すことができる。
上記の効率的な組合せとは全く無関係に、n個の分銅があったときの分銅の組合せを
考える。
上皿天秤で計るので、計る対象となる物は左の皿に置くことにする。
このとき、各分銅について、
右皿に置く（つまり+）
左皿に置く（つまり-）
どちらにも置かない（つまり0）
の3通り考えられる。（3n通り）
このうち、0gの組合せ、すなわち全ての分銅をどちらにも置かない組合せを引く。
（3n-1通り）
また、対象となる物は左皿に置くから、最終的に左皿がプラスとなる組合せ（つまり
右皿がマイナス、対象物の重さがマイナスになる？という無意味な組合せ）を引く。
左皿がプラスになる組合せの数と右皿がプラスになる組合せの数は全く等しいので、
結局、n個の分銅で右皿がプラスとなる組合せは1/2×[3n-1]通りあることになる。H
Gは1gから1/2×[3n-1]gまで1/2×[3n-1]通り計ることができる、と言う事ができる
から、
Gでできる組合せで得られる結果（重さ）の種類の数がHと等しいことから、上で求
めた効率的なn個の分銅でできるすべての組合せ（H）は1〜1/2×[3n-1]までの1gき
ざみの重さすべて（G）と1対1で対応していることがわかる。
以上により、この選び方は必要最小限の数の分銅を選ぶことができるといえる。
もちろん、他の選び方の存在は否定できないが、少なくともこの選び方より効率のよ
い方法はないといえる。
ちょっと長くてごちゃごちゃしてますが、こんなところでどうでしょうか？
最初の選び方において「重さが同じとなる組み合わせは2つ以上ない」ことを説明で
きれば簡単だったのですが、
重さに関係なく可能な組合せの数を出した方が説得力があるかな？とおもったのでこ
うなりました。
（ペンネ−ム：ねこ）
１（＝３０）ｇ、３（＝３１）ｇ、
９（＝３２）ｇ、２７（＝３３）ｇの４つ。
−１，０，１の３進数と見ればOK。
量るものを右のさらに乗せるとき、
１なら左、−１なら右、０なら乗せないようにする。
| ２７ | ９ | ３ | １ | ||
|---|---|---|---|---|---|
| １ | ０ | ０ | ０ | １ | |
| ２ | ０ | ０ | １ | −１ | |
| ３ | ０ | ０ | １ | ０ | |
| ４ | ０ | ０ | １ | １ | |
| ５ | ０ | １ | −１ | −１ | |
| ６ | ０ | １ | −１ | ０ | |
| ７ | ０ | １ | −１ | １ | |
| ８ | ０ | １ | ０ | −１ | |
| ９ | ０ | １ | ０ | ０ | |
| １０ | ０ | １ | ０ | １ | |
| １１ | ０ | １ | １ | −１ | |
| １２ | ０ | １ | １ | ０ | |
| １３ | ０ | １ | １ | １ | |
| １４ | １ | −１ | −１ | −１ | |
| １５ | １ | −１ | −１ | ０ | |
| １６ | １ | −１ | −１ | １ | |
| １７ | １ | −１ | ０ | −１ | |
| １８ | １ | −１ | ０ | ０ | |
| １９ | １ | −１ | ０ | １ | |
| ２０ | １ | −１ | １ | −１ | |
| ２１ | １ | −１ | １ | ０ | |
| ２２ | １ | −１ | １ | １ | |
| ２３ | １ | ０ | −１ | −１ | |
| ２４ | １ | ０ | −１ | ０ | |
| ２５ | １ | ０ | −１ | １ | |
| ２６ | １ | ０ | ０ | −１ | |
| ２７ | １ | ０ | ０ | ０ | |
| ２８ | １ | ０ | ０ | １ | |
| ２９ | １ | ０ | １ | −１ | |
| ３０ | １ | ０ | １ | ０ | |
| ３１ | １ | ０ | １ | １ | |
| ３２ | １ | １ | −１ | −１ | |
| ３３ | １ | １ | −１ | ０ | |
| ３４ | １ | １ | −１ | １ | |
| ３５ | １ | １ | ０ | −１ | |
| ３６ | １ | １ | ０ | ０ | |
| ３７ | １ | １ | ０ | １ | |
| ３８ | １ | １ | １ | −１ | |
| ３９ | １ | １ | １ | ０ | |
| ４０ | １ | １ | １ | １ |
（ペンネ−ム：夜ふかしのつらいおじさん ）
解答は（１）・（３）・（９）・（２７）ｇの４種類です。
なぜなら、次のように１から４０までの数と分銅とで等式を作れるからです。
左辺は左のサラに、右辺は右のサラにのせれば天秤は釣り合います。
| １＝（１） | ２＋（１）＝（３） |
| ３＝（３） | ４＝（１）＋（３） |
| ５＋（１）＋（３）＝（９） | ６＋（３）＝（９） |
| ７＋（３）＝（１）＋（９） | ８＋（１）＝（９） |
| ９＝（９） | １０＝（１）＋（９） |
| １１＋（１）＝（３）＋（９） | １２＝（３）＋（９） |
| １３＝（１）＋（３）＋（９） | １４＋（１）＋（３）＋（９）＝（２７） |
| １５＋（３）＋（９）＝（２７） | １６＋（３）＋（９）＝（１）＋（２７） |
| １７＋（１）＋（９）＝（２７） | １８＋（９）＝（２７） |
| １９＋（９）＝（１）＋（２７） | ２０＋（１）＋（９）＝（３）＋（２７） |
| ２１＋（９）＝（３）＋（２７） | ２２＋（９）＝（１）＋（３）＋（２７） |
| ２３＋（１）＋（３）＝（２７） | ２４＋（３）＝（２７） |
| ２５＋（３）＝（１）＋（２７） | ２６＋（１）＝（２７） |
| ２７＝（２７） | ２８＝（１）＋（２７） |
| ２９＋（１）＝（３）＋（２７） | ３０＝（３）＋（２７） |
| ３１＝（１）＋（３）＋（２７） | ３２＋（１）＋（３）＝（９）＋（２７） |
| ３３＋（３）＝（９）＋（２７） | ３４＋（３）＝（１）＋（９）＋（２７） |
| ３５＋（１）＝（９）＋（２７） | ３６＝（９）＋（２７） |
| ３７＝（１）＋（９）＋（２７） | ３８＋（１）＝（３）＋（９）＋（２７） |
| ３９＝（３）＋（９）＋（２７） | ４０＝（１）＋（３）＋（９）＋（２７） |
Ｐ．Ｓ．
中学２年生の数学の授業でほぼ同じ内容のものがありますね。
記数法を学習するのですが、お金を払うのにどんなコインを用意するのがいい
のかという設定です。
（相手からおつりをもらうとすればまったくおなじになる）
普通のお金だと1円玉、５円玉、１０円玉ですが例えば１９円払うのに３種類６枚使います。
いろいろなコインの種類を考えて種類と枚数が総合的に少なくなるようにするにはどうしたらいいか？
結論は２進法のコインを用意する
（１円玉、２円玉、４円玉、８円玉、１６円玉・・・）。
２進法コインの最大のメリットはどんな額を払うにもコインはどの種類も１枚だけ用
意しておけばよいということです。
（ペンネ−ム：高橋 道広 ）
「答えは1,3,9,27」ですが、この考えを一般化して説明するにはどうすればいいでしょう。
イメージ的には、数字を三進法で表して、40（10）=1111（3）ですから、1111（３）以下の数は、
たとえば1021（３）とかは1021＝1101-10を利用すればいいことになります。
一般に1,3,9,27,81,..グラムの分銅があるとして、
ｎ個で（3n-1）/2通りのはかり方があることを証明します。
分銅が１個のときは1通りのはかりかたがあります。
分銅がｋ個のときに、1+3+...3k-1=（3k-1）/2の図り方があると仮定して、
k+1個の時は、
まず３ｋを使わない（3k-1）/2通り 次に3kのみを使う１通り
更に、3kと（3k-1）/2通りを同じ天秤に載せるか、逆に載せるかの2×(3k-1）/2通り
（実際は天秤の両方に分銅を載せるのですが、便宜上1グラムから、（3k-1）/2グラム間での1グラム
おきの分銅があって、それを3kの分銅の同じ方におくか、逆のほうにおくかというイメージです）
合計(3k-1)/2×3+1=(3k+1-1)/2通りになります。
さてこの中で同じ重さを図ることがない事を証明します。
便宜上1グラムから、（3k-1）/2グラム間での1グラムおきの分銅があると考えててください。
問題は、3kの分銅と逆の方に、おくときです。これ以外は、（3k-1）/2より少ないか、3kより多いか
のどちらかですから、だぶってはいません。
逆のほうにおくと当然3kよりは少ない事になります。また、最大で（3k-1）/2を逆におくことができ
ますが、3k−（3k-1）/2= （3k+1）/2でこれは（3k-1）/2より大きいことがわかります。
このことから、重複のはかり方がない事が分かり、最大は(3k+1-1)/2グラムですから
１グラム刻みではかれることが分かりました。
（ペンネ−ム：Idaho Potato）
答：1g, 3g, 9g, 27g.
要するに、-1, 0, 1 の3つの数字を用い、n桁目に 3n の重みをつけた3進数を考えるわけです。
0, 1, 2 の3つの数字を用いる通常の3進数では、4桁で 0 〜 80 の整数を表現できますが、
使う数字を -1, 0, 1 とすると、-40 〜 40 の整数を表現できます。
一般に、この記数法によるn桁の数で表現できる整数の範囲は、-(3n - 1) / 2 〜 (3n - 1) / 2 です。
天秤でいえば、「1」の桁は左に分銅をのせて、「-1」の桁は右に分銅をのせればよいのです。
この記数法の特徴は、「マイナス記号」を使うことなく、負の数を正の数と同様に記述できることです。
整数はもちろん、無限小数を用いれば実数も表現できます。
また、使う数字の範囲は違っても、基本的には「位取り記数法」ですから、足し算やかけ算の筆算もできます。
足し算の場合、「1」が2つ重なったら、その位を「-1」にして上の位に 1 を繰り上げ、「-1」が2つ重なったら、その位を「1」にして上の位に -1 を繰り上げ（？）ればよいわけです。
かけ算は、普通の筆算と同様に、桁をずらして足せばできます。
2つの数の大小判定は、単に上の位から順に数字を比較すればOKです。
特に、最上位の数字を見れば正負がわかります。
8 1 0 -1
+) 7 +) 1 -1 1
------ ---------------
15 1 -1 -1 0
7 1 -1 1
*) 5 *) 1 -1 -1
------ ------------------
35 -1 1 -1
-1 1 -1
1 -1 1
------------------
0 1 1 0 -1
マイナス記号を使わずに負の数を記述する別のアプローチとして、0, 1 の2つの数字を用い、n桁目に (-2)n の重みをつける「-2進法」も考えられます。
n が偶数のとき、n桁の-2進数で表現できる整数の範囲は、(-2)×(2n - 1) / 3 〜 (2n - 1) / 3 です。
やはり、無限小数を用いれば、実数も表現できます。
2桁ずつ束ねて見れば、-2, -1, 0, 1 の4つの数字を持つ4進数と考えられるので、上述の3進数のバリエーションともいえます。
-10 1010 -9 1011 -8 1000 -7 1001 -6 1110 -5 1111 -4 1100 -3 1101 -2 0010 -1 0011 0 0000 1 0001 2 0110 3 0111 4 0100 5 0101
これをさらに発展させれば、n桁目に (sqrt(2)×i)n （ただし i は虚数単位）の重みを持たせて、0, 1 の2つの数字だけで複素数を表現する、なんてこともできそうですね。
（ペンネ−ム：浜田 明巳）
答：１，３，９，２７
エクセルのマクロで解きました．この頃不調です．答もこれひとつしかないことも確認しました．
Option Explicit
Sub Macro1()
Dim bundou(4) As Integer
Cells(1, 1).Value = 0 '答の個数
Range("A1").Select
bundou(0) = 1
Call check1(1, bundou())
End Sub
Sub check1(ByVal n As Integer, ByRef bundou() As Integer)
Dim j(4) As Integer
Dim omosa(40) As Integer
Dim i As Integer
Dim dame As Integer
bundou(n) = bundou(n - 1) 'bundou(1)≦bundou(2)≦bundou(3)≦bundou(4)
While bundou(n) <= 50
If n < 4 Then
Call check1(n + 1, bundou())
Else
For i = 1 To 40
omosa(i) = 0
Next i
Call check2(1, bundou(), j(), omosa())
dame = 0
i = 1
While dame = 0 And i <= 40 '1〜40まで計れるか
dame = -(omosa(i) = 0)
i = i + 1
Wend
If dame = 0 Then
Cells(1, 1).Value = Cells(1, 1).Value + 1
For i = 1 To 4
Cells(Cells(1, 1).Value, i + 1).Value = bundou(i)
Next i
End If
End If
bundou(n) = bundou(n) + 1
Wend
End Sub
Sub check2(ByVal n As Integer, ByRef bundou() As Integer, ByRef j() As Integer, ByRef omosa() As Integer)
Dim i As Integer
Dim wa As Integer
j(n) = -1
While j(n) <= 1
If n < 4 Then
Call check2(n + 1, bundou(), j(), omosa())
Else
wa = 0
For i = 1 To 4
wa = wa + j(i) * bundou(i)
Next i
If wa > 0 And wa <= 40 Then
omosa(wa) = 1
End If
End If
j(n) = j(n) + 1
Wend
End Sub
| 夜ふかしのつらいおじさん | kiyo | 高橋 道広 |
| judas | 浜田 明巳 | 数学がとっても大好きな 新潟県民 |
| けんたん | ねこ | Chee |
| Idaho Potato |
最初に問題文に誤解をまねく表現があったことをお詫びいたします。
１ｇの分銅で充分ではないですか？ というご指摘を受けましたが、
いくら支払うにしても大量の１円玉があれば、支払うことはできるというのと同じですね。
今回の問題は、"４種類の分銅はそれぞれ１個ずつ"ということで考えてください。
問題の答えは、１，３，９，２７の４種類です。
しかし、この答えを出しただけでは不十分で、
この４つで実際に１ｇ〜４０ｇまでを１ｇきざみで表現できるということの
検証が必要かと思います。
高橋 道広さんのように一括証明できればベスト、
または実際に４０通り示してもいいと思います。
解答の一意性についての疑問(答えはこの組み合わせだけなのかなあ？)に対する答えは、 浜田 明巳さんが検証してくださいました。 そしてこれが、もっとも効率的な組み合わせであるということを、 judasさん、高橋 道広さんが示してくださいました。
夜ふかしのつらいおじさんのご指摘の通り、普通は２進数で考えます。
しかしこの天秤問題は、相手方に分銅をのせることでマイナスの数を表現できる(相手からおつりをもらえる)
ということで、結果的に３進数ということになります。
ねこさんが３進法表示の解答を示してくださいました。
これをみるとよく理解できると思います。
問題文にある４０ｇというのも実は意味のある数です。
おわかりですよね？ ４０＝１１１１(3)です。
さらに４種類の分銅で３進法表示すると、３４＝８１通りの表現があるはずです。
残りの４１通りはどこにいってしまったか？
それは、−４０ｇ〜０ｇです。
逆に、１，３，９，２７，・・・というｎ個の分銅で、(３ｎ−１)/２ｇまで、
１ｇきざみではかることができるわけです。
（高橋 道広さんの証明参照）
E-mail
戻る
top