今日、私は再び、ダイヤルなしのはかりで計量することによって偽のコインを見つける問題のトピックに戻りたいと思います。
これらのタスクの中で最も一般的なのは、次の場合に偽造コインを識別するための計量回数を決定することです。
1）重量が不明です。
2）他のものよりも軽い/重いことが知られています。
または逆の問題：特定の数の計量で、特定の数のコインの偽物を識別することは可能ですか？
1.最初に、オプション1の特別なケースであるオプション2を扱います。
少し前に、Habréでそのような問題の解決策をすでに説明しましたが、コメントの1つで、コインの少し奇妙な最初の分離についての発言がありました。それが、別の解決アルゴリズムを提案する理由です。 結果は同じになりますが、問題を解決するための式は同じままです。
N> = log 3 A
Nは、必要な計量の最大数、自然数、切り上げです。
Aはコインの数です。
実験に基づいて導き出されます（1計量の場合、3コインの偽物、2の9、3の27など）を見つけることができます）
解法アルゴリズム自体は単純で、例を示して説明します
1）26枚のコインを持ちましょう。 より軽い/重いものを見つける必要がある
最初のステップは、コインを3つのグループに分割することです。2つのグループではコインの数が同じになります。3番目のグループ（残りの部分）のコインは他の2つのグループのそれぞれよりも少ないことが重要です つまり、頻度はより大きな自然数に丸められます。 それは
A = 2 * B + C、
ここで、Aはコインの数です。
Bは、コインの数を3で割った商です。自然数は切り上げられます。
Cは余りです。
問題の状態によって
26/3 = 8.666（6）、
26 = 2 * 9 + 8
最初の計量では、2つのグループが比較されます：右（PG）-9コインと左（LG）-9コイン。
さらに、2つのオプションがあります。
1）左/右グループの偽コイン（9コイン）
2）残高の偽コイン（8コイン）
オプション1の場合、次のグループへの分割は-9 = 2 * 3 + 3になります。
2つのオプション-8 = 2 * 3 + 2
さて、1回の計量で、2つまたは3つのコインのどちらが軽い/重いかを判断できます
同じ結果を表に示します
| 計量値 | コインの数 | Lh | PG | 残り |
| 1 | 26 | 9 | 9 | 8 |
| 2 | 8 | 3 | 3 | 2 |
| 2 | 9 | 3 | 3 | 3 |
| 3 | 2 | 1 | 1 | 0 |
| 3 | 3 | 1 | 1 | 1 |
式によると-ログ3 26 = 2.9656-したがって、計量の数-3。
別の例：
コインの数は71です。式ログ3 71 = 3.8800によると、計量の数は4です。
| 計量値 | コインの数 | Lh | PG | 残り |
| 1 | 71 | 24 | 24 | 23 |
| 2 | 23 | 8 | 8 | 7 |
| 2 | 24 | 8 | 8 | 8 |
| 3 | 7 | 3 | 3 | 1 |
| 3 | 8 | 3 | 3 | 2 |
| 4 | 2 | 1 | 1 | 0 |
| 4 | 3 | 1 | 1 | 1 |
まあ、これらの問題を解決するためのアルゴリズムで、私は理解できると思います。
2.次に、コインがより軽くまたはより重く分からないタスクに目を向けます。
この場合、私はこの最初のアクションを提案します：コインを4つのグループに分けます。3つが最も同数のコインで、4番目のグループが残りです。 さらに、残高は1枚または2枚のコインである必要があります。 つまり、3で除算すると、商はより小さな自然数に丸められます。
A = 3 * B + C、
ここで、Aはコインの数です。
Bは、コインの数を3で割った商です。自然数は切り捨てられます。
Cは余りです。
たとえば、58コインの場合、58 = 3 * 19 + 1、23 = 3 * 7 + 2、15 = 3 * 5 + 0などになります。
次に、2つの計量を実行します。
1）最初と2番目のグループ。
2）1番目と3番目のグループ。
結果を分析します。
ここでは4つのオプションが可能です。1、2、3-これは最初、2番目、または3番目のグループが他の2つと重量が異なるか、等しい場合、偽物が残りなので幸運でした。 また、2つの計量により、コインを偽造するのが難しいか簡単かを判断できます。 ちなみに、天びんにコインが2枚ある場合は、さらに2回計量して偽のコインを判別する必要があります。
ここで、タスクがあります。より軽い/重いグループから1つの偽造コインを識別することです。
式については、次の形式になります
N> = log 3 B + 2
Nは計量の最大必要数で、自然数です。
B-2回目の計量後のグループ内のコインの数。
そして、B = A / 3（Aはすべてのコインの数）を考慮すると、次のようになります。
log3B =ログ3 A-1
N> = log 3 A + 1
結果：
1）偽のコインがより軽い/重いことがわかっている場合、計量の最大数は次の式で決定されます：
N> = log 3 A
2）どちらが間違っているかわからない場合、計量の最大数は次の式で決定されます。
N> = log 3 A + 1
Nは、必要な計量の最大数、自然数、切り上げです。
Aはコインの数です。