問題の意味すらわかりません

質問

1g , 2g , 4g ,……, 2^(n-1)gの分銅が各１個あれば、これらを組み合わせて1gから(2^n －1)gまでの1gごとの重さが測れることを示せ。

数学的帰納法をつかうことはわかるのですが…
問題の意味から教えて下さい。

回答No.1

age_momo · ベストアンサー

証明ではなく、示すだけならこれらの重さを2進法で表すと
1
10
100
1000
10000
・・・・
・・・・
10000…00　(0はn-1個)
これらを組み合わせれば1から111111(1がn-1個つまり、2^n-1)まで
作ることができます。

回答No.5

jamf0421

>しかし{2^(k+1)-1} - 2^k =2^k(2-1)-1=2^k-1は
>どこからでてきたのでしょうか？

あらたに2^k gの分銅が加わったときに、測ることができなければならないのは、2^k（これは2^k-1の次の数です。）から2^(k+1)-1までの1 g刻みですね。その個数を数えるのですが、この引き算で2^k+1から2^(k+1)-1までの個数を数えたことになります。これが2^k-1個の数字になるので、2^kから数え始めた時
2^k, 2^k+1, 2^k+2,....2^k+X
でXが丁度（2^k-1）になることを示したかったのです。

あらたに1 g刻みで測るのに必要なg数が2^k gから始まって、終点が
2^(k+1)-1 = 2^k + (2^k-1)
であることさえわかればことさらに書かなくてもよかったかも知れません。

お礼

大変よくわかりました!!

本当にありがとうございます。

回答No.4

jamf0421

数学的帰納法の場合（厳密性に自信ないですが）；
n=1の場合明らかに成り立ちます。
n=kで成立したとします。即ち、1, 2, ....2^(k-1)までの分銅各1個で、1から（2^k-1)までの整数の重さが測れたとします。
n=k+1の場合、上記に2^kの分銅が加わります。この時2^(k+1)-1まで測れることが示せればよいです。
この場合、2^k-1の次の数から、即ち2^kから2^(k+1)-1までを1 g単位で測れることが示せればよいわけです。あらわな形でかけば、
2^k, 2^k+1, 2^k+2, 2^k+3,...2^(k+1)-1
ですが、
{2^(k+1)-1} - 2^k =2^k(2-1)-1=2^k-1
を考慮すると、
2^k, 2^k+1, 2^k+2, 2^k+3, ...2^k+(2^k-1)
とかけます。即ちこれらは2^kに1, 2, 3, ...(2^k-1)を足した数です。
2^(k-1) gまでの分銅で2^k-1 gまで整数刻みではかれたのですから、これに2^k gの分銅が加われば2^(k+1)-1まで測れることは明らかです。

お礼

ありがとうございます!!

しかし{2^(k+1)-1} - 2^k =2^k(2-1)-1=2^k-1はどこからでてきたのでしょうか？

回答No.3

staratras

No.2です。すみません。２＾４－１＝１５グラムまでですね。
9=8+1
10=8+2
11=8+2+1
12=8+4
13=8+4+1
14=8+4+2
15=8+4+2+1　ここまで書けばよくわかりますね。

お礼

ありがとうございます。

問題の意図がとてもよくわかりました。

しかし…あまり連想できないのですが……

回答No.2

staratras

ｎを適当な数にして具体的に考えてみれば分かりやすいと思います。ｎ=4とすると、1,2,4,8グラムの分銅が１個ずつある。これを組み合わせると1,2,3,4,5,6,7,8グラムの重さが量れることを示せ、ということになります、
1=1
2=2
3=2+1
4=4
5=4+1
6=4+2
7=4+2+1
8=8 確かに量れることが分かりますが、この式を見て何かを連想されませんか？