この問題を解いてください。お願いしますｍ（－－）ｍ

質問

天秤がひとつあります。これで1グラムから13グラムまでの13通りの整数値の重さ（１，２，３、…13g）をすべてはかれるようにしたい。どのような重さの分銅（重り）を揃えら良いか？
（１）、揃えておく分銅の数が最も少なくなる場合の分銅の組み合わせを示せ。
（２）、その個数が最小個数であることを証明せよ。
（３）、（１）の組み合わせをすべて求めそれがすべてであることを示せ。
（４）、40グラムにしたらどうなるか。（１～４０までの40通りがはかれるように　　　　する。）
（５）、この問題をネタに好きなように論じてみろ。（一般化したり拡張化した　　　　　り・・・）論じてみよ。例えば上の13とか40に特別な意味があるだろうか　　　　など。
＜ヒント＞
　　　　例えば５グラムの分銅と７グラムの分銅ではかれる重さは５と７、12の三　　　　つだけではありません。右の皿に５グラム、左に７グラムをのせることに　　　　より、２グラムもはかれます。

どうしてもこの問題が解けずに困っているので教えてください。

回答No.1

tomin · ベストアンサー

(1)1g,3g,9g
1=1,2=3-1,3=3,4=1+3,5=9-3-1,6=9-3,7=1+9-3,8=9-1,
9=9,10=1+9,11=9+3-1,12=3+9,13=1+3+9
(2)おもりが２個では４通りの重さしか量れない。
おもりが３個になると・・・
３個とも使う場合　４通り量れる
２個使う場合　３×２＝６通り量れる
１個使う場合　３通り計れる
４＋６＋３はちょうど１３なので、(1)の個数は最小である。
(3)おもりの重さの合計は13ｇでなければならない。
また同じ重さの重りはあってはならない。そのことからすべての
場合をしらみつぶしにしらべればよい。
(4)おもりが４個になれば、
４個とも使う場合　８通り
３個使う場合　４×４＝１６通り
２個使う場合　６×２＝１２通り
１個使う場合　４通り量れる
よって８＋１６＋１２＋４＝４０なので、
おもりが４個の場合で解があれば、それが最小になる。
（つづく）

お礼

分かりやすく書いていただきありがとうございました。助かりましたｍ（－－）ｍ
またなにかあったらご協力おねがいします。　　yahi-

回答No.3

guiter

組み合わせで考えてみると

まず、ｎ個のおもりのうち何個皿に乗せるかを決めます。
その後乗せるおもりのうちいくつを左（または右）に乗せるかを決めます。

1g,3g,9g で具体的に見てみると
・１個　　3Ｃ1( 1Ｃ0 ) = 3Ｃ1( 1Ｃ0 + 1Ｃ1 )/2 = 3通り
・２個　　3Ｃ2{ 2Ｃ0 + (2Ｃ1)/2 } = 3Ｃ2( 2Ｃ0 + 2Ｃ1 + 2Ｃ2 )/2 = 6通り
・３個　　3Ｃ3( 3Ｃ0 + 3Ｃ1 ) = 3Ｃ3( 3Ｃ0 + 3Ｃ1 + 3Ｃ2 + 3Ｃ3 )/2 = 4通り
となります。

３個のうち１個のおもりを使う場合は
おもりの選び方が 3Ｃ1 = 3通り、乗せるひとつを決めた後
左の皿に乗せる個数を０個とした 1Ｃ0 = 1通りなので 3*1=3通り
左の皿に乗せる個数を１個とすると右の皿が０個となるので
これは重複しています。

次に３個のうち２個のおもりを使う場合も同様に考えますが、
(2Ｃ1)/2 としているのは２個のうち左に乗せるおもりを１個選ぶと
左右の皿に乗る個数が同じなので重複を除くために２で割っています。
（左1g,右3g と 左3g,右1g はおなじ重さを量ることになりますね。）
したがって、偶数個のおもりを使う場合において
半分ずつ左右の皿に乗せるときだけ２で割ることになります。

このように考えると、1g,3g,3^2g,…,3^(n-1)g のn個のおもりのとき
ｎ個のうちｋ個を選んだ場合の組み合わせの個数は
　nＣk (ΣkＣi)/2　通り
となります。
ここで、Σは i=0 から i=k までの和です。
したがって
　nＣk (ΣkＣi)/2 = (1/2)(nＣk)*2^k　通り
となります。

あとは、ｋについて１からｎ個までの和をとれば
（k=0 は皿にひとつもおもりを乗せないことになるので）
　(1/2)Σ(nＣk)*2^k = (3^n - 1)/2 通り
となり、(3^n - 1)/2 通りのおもさを量れることになります。
また、1g,3g,…,3^(n-1)g のn個のおもりを全部あわせると
　1 + 3 + … + 3^(n-1) = (3^n - 1)/2 g
となるので、これは１つももらさず 1g から (3^n - 1)/2 g まで
量れることを意味します。

コンビネーションの和をとるときに２項定理を用いました。

お礼

どうもご協力ありがとうございました。すごく助かりました（＾－＾）またなにかあったらご協力お願いします。　　yahi-

回答No.2

tomin

(4)
40=3^3+3^2+3+1である。
1g,3g,9g,27gが答え。
１～４０の間の数を３進法で書いたときに
それぞれの桁が０か１か２によって、
1g,3g,9g,27gの重りを置く場所を変える。
０・・・おかない
１・・・左に置く
２・・・右に置き、左に１回り大きい重りを置く。
こうすれば、右側に調べたい重りを置くことで量ることができる。
(5)たとえば、
1,3,3^2,・・・,3^(n-1)gのn個のおもりがあれば、
1+3+・・・+3^(n-1)=(3^n-1)/2gまでの整数値の重さをすべて量ることができる。