てんびんではかる場合の分銅の最小の個数

質問

（問題）てんびんで，物体のおもさをはかる場合，1ｇから100ｇまでを，1ｇきざみですべてはかることのできる分銅の最小の個数を求めなさい。
（解答）100ｇを2進数で表すと，1100100となるから，分銅は，64ｇ，32ｇ，16ｇ，8ｇ，4ｇ，2ｇ，1ｇの7種の各1個ずつで，分銅の最小個数は7個である。

が，正解のようです。この場合，なぜ，2進数で決めた分銅の個数が最小の個数になるのかが，わからないです。解説をよろしくお願いします。

例えば，
3進数で分銅の種類と個数と決めた場合は，10進数の100ｇ＝3進数で10201だから，81ｇ，27ｇ，9ｇ，3ｇ，1ｇの4種で，各2個ずつ必要だから，分銅は8個です。

4進数でやると，10進数の100ｇ＝4進数で1210だから，54ｇ，16ｇ，4ｇ，1ｇの4種で，各3個ずつだから，分銅の個数は12個となります。

このように，2進数以外でやると，分銅の個数は増えてしまいます。なぜ，2進数で求めた分銅の個数が最小と言えるのでしょうか。教えてください。よろしくお願いします。

回答No.1

tmpname · ベストアンサー

先ず、「n個の分銅で、最大で何種類の異なる重さを測る事ができるか？」ということを考えてみる。すると、これは
＊n個の分銅それぞれについて、はかりに「載せる」「載せない」の2通りがある。
＊つまり、n個の分銅それぞれを「載せる」「載せない」の組み合わせは、全部で2^n通り
＊n個の分銅の「載せる」「載せない」の組み合わせが違う時、分銅の合計の重さが異なるように各の分銅の重さが調整されている時、n個の分銅で測れる重さの種類が最大となる
事を考えれば、つまり

「n個の分銅では、最大で2^n種類の異なる重さしか測れない」

そこで、1gから100gまでを測ろうとすると、全部で100種類の異なる重さを測る必要がある。すると、6個では足りなくて（何故なら6個だとどう頑張っても最大で2^6 = 64種類の重さしか測れない）、7個は絶対に必要なのは分かる
＊7個あれば、最大で2^7 種類の重さが測れる。ただし、これで本当に1~100gまでの間がきれいに測れるかはまだこの段階では分かっていない

で、今分かったのは、「1gから100gまでを測ろうとすると、7個は絶対に必要。だけど7個でできるかどうかはまだ分らない（実は8個いるかも知れない）」という段階。一方、分銅の重さを実際に2進数の方法で作ると、「実際に7個で出来る」（つまり、実際に7個で測る方法が本当にある）。

つまり、1gから100gまでを測ろうとすると、必要な分銅の数は最低7個というのがここで確定します。要は「n個の分銅では、最大で2^n種類の異なる重さしか測れない」というのがポイントです。

お礼

なるほど，2進数の計算とは，別に，まず，分銅の個数によって，はかれる重さの種類の最大数を求めておけばよいのですね。わかりました。
ありがとうございます。

回答No.3

178-tall

参照 URL でも。

参考URL：

http://blog.livedoor.jp/enjoy_math/archives/50466693.html

回答No.2

tmpname

一つ補足しておくと、n個の分銅を「全部載せない」に対応するのは必ず0gなので、これを考えるとn個の分銅で（0gでない）重さは全部で(2^n - 1)個しか測れない。
そうすると、例えば1g から1g刻みで64gまでの重さを測るには、6個でなくて7個必要な事がわかります。