n個の異なる分銅と天秤ばかりを用いた問題

質問

n個の相異なる重さの分銅の重さをA_n[g]とする。(A_nは整数とする)
1個の天秤ばかりとこれらの分銅を用いて、無限にある液体（粉末でもいい）からX[g]を測って取り出す場合、天秤ばかりを使用する最小の回数Nを求める問題を考えます。

この場合、X=Σ_(1～n)B_n A_nとなるような自然数｛B_1,B_2,…,B_n｝を導入すると、

2^N-1≦min｛max(B_1,B_2,…,B_n)｝＜2^N

で表されるNが最小試行回数となる。

上記の結論で間違いないでしょうか？

回答No.5

stomachman

どうやら、毎回の「試行」で量り取ったモノは、他の試行の結果であるモノと混ざらないように天秤に載せられる、という話なのかな。

> X=Σ_(1～n)B_n A_nとなるような自然数｛B_1,B_2,…,B_n｝を導入すると、

> 

> 2^N-1≦min｛max(B_1,B_2,…,B_n)｝＜2^N

　それじゃまずいが、
　　c = min{ max{|B_1|,|B_2|,…,|B_n|} | X=Σ_(1～n)B_n A_n かつ B_1,B_2,…,B_nはどれも整数}
　　M = ceil(log(c))（logの底は2。ceil(x)はxを越えない整数）
というのならM手の具体的な測定手順が構成できるっぽい気がする。つまりこのMは問題のNの上限を与える(N≦M)と思う。
　もちろん、手数をもっと少なくする方法がないということ（「Mが存在しないならば量り取ることは不可能」ということも含む）を証明しないと解決にはなりませんが、それには、許される操作を明示的に限定する必要があります。たとえば分銅を使わずに「ひと山の塩があるとき、それを天秤の左右の皿に等しく案配することで、半分を量り取る」という操作だって現実にはできるわけで、だから2gの分銅1個だけしかなくても、1gの塩を量り取ることができる。

お礼

ありがとうございます。

基本的にあるものを使って自由に量ることができるという問題設定です。
ご提示の半分に分割して量るというものは実は知っていました。

質問文もある量の、例えば塩を半分にするということまでは考慮しないという制限を与えた結果です。
逆に言うとそれを考慮した場合の式が与えられれば面白いと思っています。

回答No.4

kmee

A={1,6,10}
X=5
のとき
X=B_1 A_1 + B_2 A_2 + B_3 A_3
となる 「自然数(1以上の整数)」 B_1,B_2,B_3 は存在しない。

しかし、実際にはこれらの分銅と天秤を使って 5gを取り出すことができる。

Bを(自然数ではなく)非負の整数とする。
このとき、X=5となるのは
X= 5*1 + 0*6 + 0 * 10
のみ。
ここから、min｛max(B_1,B_2,…,B_n)｝ =5 となる
※ この表現もなんかおかしい。 「式を満す(複数の)数列Bについて、各数列の最大値のうち、最小のもの」という意味なのだろうけど

2^3-1 = 2^2 = 4 ≦ 5
2^3 =8 > 5
より、N=3

ところが、分銅と物体を同じ皿に載せることができるのなら
右: 6gの分銅
左: 1gの分銅 + 5gの物体
と1回で取り出せるので、N=1となり、上記と異なる。

ここで、分銅と物体は同じ皿に置けない、というルールを決める
X=3のとき
X=3*1+0*6+0*10
2^1<3<4 なので、N=2
しかし、分銅と物体を同時に置けないルールにより、 1g との比較を3回行うしかないのでN=3となり、上記と異なる。

以上のように、結論への反例があります。

お礼

ありがとうございます。

>分銅と物体は同じ皿に置けない、というルールを決める

こういうルールは設定しない。
自然数ではなく整数でよかったのですね。

回答No.3

Tacosan

「『はかり取ろうとしているもの』は分銅じゃない」というのは明白だから, 「既にはかり取ったもの」を分銅と同一視していいかどうかは議論の余地があるところじゃない?

そして「分銅とはかり取ろうとしているものを一緒にしていい」と仮定すると, やっぱり質問文の式は成り立たないという結論で終わる.

お礼

ありがとうございます。

質問では量られるものの量を決めると分銅を使わずにいきなり半分の量を量ることができてしまうので、それを除外した場合の条件設定をしたつもりでしたが、穴を埋められていないようですね。

基本的にあるものを使って自由に量ることができるという問題設定です。

回答No.2

Tacosan

その式からすると, おそらく「1 g の分銅のみを使って 3 g をはかりとる」ときに
1. まず 1 g の分銅を使って 1 g 分はかりとる
2. 1 g の分銅と 1 ではかりとった 1 g 分を使って「2 g」をはかりとる
ということを想定したんだろうと思うけど, この 2 が許されるかどうか (つまり「はかりとるものと分銅をいっしょにする」のがよいかどうか) は明確にしとかないとダメだよね. ふつうそのような使い方はしないから.

お礼

いや、その考え方はおかしい。
「異なる種類の分銅を同じ天秤に乗せてもいい」なんて記述はないにもかかわらず、一般の問題では暗黙の了解として書かれない。

「分銅と天秤ばかりを使ってものを測る」「複数回測る可能性がある」という中に回答にあるケースは暗に含まれている。

回答No.1

Tacosan

解釈に曖昧なところがあるので問題として成立しない.

お礼

回答ありがとうございます。

ではどの点が曖昧なのでしょうか？
具体的にお願いします。(回答数を無駄に増やしたくないので、回答を見た人がご解釈しないように回答願います。)

補足
自然数の集合→｛B_1,B_2,…,B_n｝(これは０の要素を含める)
max(・・・)→()内の全ての要素の中で最も大きい数を表す
min{・・・}→{}内を取りうる数値の中で最も小さい数を表す