問題の上限と下限を見つける

我々は1つが他のものより少し重いn個のボールを持っており、私たちはより重いボールを見つけたいと思っています。私たちは、スケールの一方の側にいくつかのボールを置くことができ、他方の側にはいくつかのボールを置くことができ、それが傾いているか、どちらの側にあるかを見ることができます。この問題の下限と上限をどのように見つけることができますか?上限と下限を同じにします。

ベストアンサー

これはED Schellが寄稿した “偽造硬貨問題”と呼ばれ、ペーパー”偽造コインの問題 “、1977年

Theorem 1: Let $S$ be a set of coins, one lighter than the rest.
The least number of weighings on a beam balance in which the light
coin can be found is the unique $n$ satisfying $3^{n-1} < |S|
le 3^n$.

この境界は厳しいです。

また、偽造された硬貨は他の硬貨とは重さが重いか軽いかを仮定して、この問題のより難しい変形を研究しています。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です