99個のコインの中から30個の偽のコイン

あなたは30個の偽のものからなる99個のコインを与えられます。また、あなたが置いた重さの違いを示す完璧な精度のデジタルバランススケールもあります。たとえば、左側に10
g、反対側に20 gを置くと、-10、それ以外の場合は+10が表示されます。

あなたは指定された99コインの間に偽のコインを見つけるよう求められます:

  • すべての本物の硬貨は同じ重量を持ちますが、重量は分かりません。
  • すべての偽造硬貨は、本物の硬貨より1グラム重くて軽いこともご存知でしょうか?

それで、あなたが探している偽の硬貨を見つけるために最低限必要な計量はいくらですか?あなたが見つけようとしている偽の硬貨は重くても軽くても問題ありません。偽の硬貨を見つける必要があります。

注意:重みは正の整数であると仮定できますが、結果は変更されません。

ベストアンサー

これは部分的な回答です。これは、9つの重さの中の実際のコインを識別します。最適なソリューションを作成するのに役立つ概念をカバーしていると思うので、私はここに掲載しています。

私のソリューションで最も重要なアルゴリズムは次のとおりです。

クレーム:$ n
$コインのグループに奇数の実数があることが分かっている場合、1回の計量で$(n/2)+ 1
$コイン以下のグループを特定できます(私は知っていますそれは必ずしも整数ではないので、それ以下である)、奇数の実数も含まれます。

  証明:$ 2x $を$ n/2 $以下の最大偶数とする。スケールの両側に$ x $コインを置く。
 事例1:スケールが均等に読み取られます。この場合、$ 2x
$のコインのうち偶数個の偽物があることはわかっています。これは、摂動によって簡単に表示されます。各側に$ x
$の実際のコインで始まると想像し、コインを偽物に変更するには、スケールを読み続けるために別のコインを偽物に変える必要があります。したがって、2倍の$コインに偶数のオッズがある場合、偶数の実数があります。つまり、計量していないコインには、$(n/2)+
1 $以下のODD数の実数があります。
 事例2:スケールは奇妙な量を読みます。上記と同様の理由から、私たちは$ 2x $コインにODD数の偽物を、そして$ 2x
$コインにODD数の実数を持っています。この金額は$ n/2 $以下です。

 奇数の実数のコインで、より小さなサンプル空間を識別できることが分かります。

 注意すべき点は、このアルゴリズムはコインの役割を逆にして動作することです。

しかし、私たちはいくつかの細部を細分化する必要があります。

奇数の実数$ n $を持つコインの数が0 mod 4の場合、$ x $は$ n/4
$になります。だから、私たちの計量は疑いなく、奇数の実数を持つ$ n/2 $コインのグループを特定することにつながるでしょう。
 奇数の実数$ n $のコインの数が1 mod 2(すなわち1または3 mod
4)である場合、サイズが1だけ異なる2つのグループに分けることができます。これらの1つグループは偶数であり、その場合には$ 2x
$に設定されます。したがって、$ n $が1 mod 4の場合、計量は$(n + 1)/ 2 $または$(n-1)/ 2
$になります。
 最後のケースは$ n $は2 mod 4です。$ n = 4z + 2 $です。 $ x $を$ z
$に設定します。したがって、サイズ$ 2z $、または$ 2z + 2 $、つまり$(n/2)+ 1 $または$(n/2)-1
$のグループを特定します。

重要なアルゴリズムを適用し、その2番目の段落を使用してすべての可能なケースを見つけます。

START:99コインには奇数番号があります。本当の  1つの重さ:私たちは、奇数番号の48または
49 のグループを特定しました。本当の49を特定した場合は、停止してANNOYING
CASEにスキップしてください。
 TWO WEIGHS:奇数番号の24または 25
のサイズのグループを識別しました。本当の  3つのWEIGHS:12の 13
のグループが見つかりました。  4ウェイ:サイズが6 7
で、奇妙な事実があるグループが見つかりました。
 5つのウェイ:サイズのグループが見つかりました(2または 3 または4)
 後で大胆になります。

さて、今、私たちはいくつかの卑劣なことをする必要があります。

6つ目の重さ:すべてのコインをスケールの片側に置きます。実際の硬貨の重量が$ w $グラムの場合、$ 99w + –
$(偽造品によって相殺されます)の数が得られます。私たちは、偽の硬貨の相殺は均一であることを知っています。偽の偶数があるからです!そこで、$
99w $ mod 2の小数点以下の剰余を知り、それを$ r $と呼んでください。
 $ 99w $ mod 2 = $ r $。
 $ 99(w + -1)$ mod 2 = $ r + -99 $。
 99は奇数であるため、99個の偽造硬貨は$ r $とは異なる残余を持ちます。 (注 –
私は99個の偽の硬貨は、必ずしも間違った重み付けの方向を持っているとは限りませんが、処分は奇妙です、とにかく、別の残余を作ります)

今この知識を適用してください:

NINE WEIGHS FINISH:2つのコインのグループを特定した場合、1つは実数であり、もう1つはコインではありません。
r を残した場合、もう1つは偽物であり、残っていなければ r
em>、それは偽物です。あなたは7つの重さで終わっています。
 あなたが4つのコインのグループを特定した場合、そのうちの3つを1つずつ計量し、上記と同様のロジックで真偽を判断し、最悪の場合9つの方法で完了しました。

 3つのコインを識別することはできません。そのリスト内の太字の各項目には上記の太字の項目でしかアクセスできないため、49を特定した場合は停止すると言います。しかし、REALコインを識別するためには、あなたは49コインに行って3に降ります。そこでは8重の実数を特定できます。

ANNOYING
CASEは同じ方法でリアルを識別するのが簡単なケースですが、突然偽物を特定することはより多くの作業になります。私はここでこの部分を去ります。私はそれを考える:

残量とスケール表示のパリティ

かなり高性能な2つの重要な概念があります。うまくいけば、誰かがもっと水密的な方法でこれらの概念を使用するための洞察力を持っていることを望みます。

返信を残す

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