本サイトの 最近のパズル 歴史的に商業と政府、芸術と科学の象徴である控えめなダブルパンバランススケールを特徴としていました. バランス スケールは、レクリエーションの数学でも人気があります。 バランス パズルには、明確で論理的な推論が必要であり、数学的一般化に適しています。 方法を見てみましょう クアンタ 読者は、以下のパズルでこれらの資質のバランスを取りました。
パズル1
あなたはXNUMXつの同じように見えるコインを持っています。 XNUMXつは偽造品であり、同じ重量を持つ他の製品よりも軽量です。 XNUMXつの計量で悪いコインを見つけます。 偽造コインを見つけることができるコインの最大数の一般式を見つけてください x 計量。
問題の単純なバージョンに取り組むと、多くの場合、解決策の鍵が明らかになります。 この場合、コインが XNUMX 枚しかなく、XNUMX 枚が他の XNUMX 枚より軽いとします。 それらのいずれかを他の XNUMX つのうちの XNUMX つと比較すると、バランスがとれるか、そうでないかのどちらかです。 そうでない場合は、どちらが軽いかがわかります。 バランスが取れている場合、XNUMX番目は軽いものです。 計量は XNUMX 回で済みます。
したがって、このパズルでは、最初の計量でライト コインを含む XNUMX つ (またはそれ以下) のグループを分離できれば、あと XNUMX 回計量するだけで済みます。 これを行うには、任意の XNUMX つを他の XNUMX つに対してバランスを取ります。 XNUMX つのグループのバランスが取れていない場合は、軽いグループを含むグループが見つかったので、上記のように XNUMX 回目の計量を行うことができます。 バランスがとれている場合は、残りの XNUMX 枚のコインを互いに重さを量ると、軽いコインが見つかります。
これは、計量されていないグループに XNUMX 枚ある場合にも機能することに注意してください。したがって、XNUMX 枚のコインから開始することもできます。 このロジックに従って、XNUMX 枚のコインから始めて、追加の計量ごとに、以前のコインの XNUMX 倍の数でライト コインを見つけることができます。 コインの最大数を与える式 n in w したがって、計量は n = 3w.
パズル2
あなたは12枚の同じように見えるコインを持っています。 XNUMXつは、同じ重みを持つ他のXNUMXつよりも重いか軽いかのどちらかです。
-
XNUMXつの計量で悪いコインを見つけます。
-
XNUMX回の計量で悪いコインを見つけることができるコインの最大数はいくつですか？ 偽のコインを見つける方法を説明してください。
このパズルの解決策は、 テッド、また、13回の計量でXNUMX枚のコインの中から不良コインを実際に検出できることも示しました。 Ted の解決策は次のとおりです (それぞれのケースで XNUMX つの重み付けを区切るためのくぼみがあります)。
4 コイン対 4 コインの重量を量ることから始めます。
ケース 1: バランスが取れていない場合、2 回目の計量では、重量の重い側を 1 つ、重量の軽い側を XNUMX つ、はかりの両側に置きます。
1a: バランスが取れていない場合、悪いコインはまだ重い側にある 2 枚のコインか、まだ軽い側にある XNUMX 枚のコインです。
考えられる 2 つの重いコインの重さを量ります。悪いコインは XNUMX つのうち重い方、またはバランスが取れている場合は XNUMX 枚の軽いコインです。
1b: 2 回目の計量でバランスがとれている場合、悪い硬貨は XNUMX 回目の計量で軽い方の XNUMX つの未使用コインのうちの XNUMX つです。
それらを互いに秤量してください。軽い方が悪いです。
ケース 2: バランスがとれている場合、悪いコインは残りの 5 枚のうちの 3 枚です。 それらのうちの 3 つを、すでに計量済みの XNUMX つに対して計量します (これは [良い] ことが知られています)。
ケース 2a: バランスが取れていない場合、不良コインがこれら 3 つのいずれかであり、軽いか重いかがわかります。
2 番目の計量は、それらのいずれか XNUMX つが互いに反対になっている場合です。バランスが取れていない場合は、悪いコインを識別し、バランスが取れている場合は、XNUMX つのうちの最後です。
ケース 2b: 2 番目の計量が均衡している場合、不良コインは残りの XNUMX つのコインの XNUMX つです。
それらのいずれかを、既知の良好な硬貨と比較して秤量します。 この結果がアンバランスである場合、この新しいコインは不良であり、重いか軽いかがわかります。 この結果が釣り合っている場合、13 番目のコインは悪いですが、重いか軽いかは不明です (これは知る必要がないので、これで完了です)。
テッド また、40 回の計量でのコインの最大数は XNUMX であることも示しました。このパズルの公式は次のとおりです。 n =（3w − 1)/2。
残りのパズルについては、一般化された公式はまだプロの数学者によって調査中であり、公開された論文の主題であり、その一部はによって引用されています 春のライナー. パズルで検討する少数のコインの解決策に限定し、これらのケースで使用される方法から自然に導かれる一般化についてのみ言及します。
パズル3
これはパズル1のバリエーションです。同じように見えるコインがXNUMXつあり、そのうちのXNUMXつは他のコインよりも軽いです。 ただし、現在はXNUMXつのスケールがあります。 XNUMXつのスケールは機能しますが、XNUMXつ目は壊れており、ランダムな結果が得られます（正しい場合と間違っている場合があります）。 どのスケールが壊れているかわかりません。 軽いコインを見つけるのに何回の計量が必要ですか？
問題 1 で見たように、これは XNUMX 回の計量でバランスが取れています。 また、XNUMX つの適切な天びんが常に一致することもわかっているため、読者が示唆したように、XNUMX つの天びんすべてでそれぞれの計量を繰り返すだけで、XNUMX 回の計量で答えが得られます。 計量回数を少なくしようとすると、少し難しくなります。 同じコインを XNUMX つのスケールで量っただけでは、良いスケールを特定することはできません。 (これはまた、誤った情報やランダムな情報がいかに簡単に真実を曖昧にするかを示しています。)
実際、この問題は非常に巧妙に、わずか XNUMX 回の計量で解決できます。 春のライナー は、このパズルのために作成されたと思われる新しい記法を使用してソリューションを投稿しました。 しかし、そこに行く前に、物事をより直感的にするためのシナリオを想像してもらいたい.
あなたが、0、1、2 の数字のみを使用した XNUMX 桁のナンバー プレートを持つ小さな国でひき逃げを調査している探偵だと想像してみてください。A、B、C の XNUMX 人が事件を目撃しました。 そのうちの XNUMX 人は XNUMX 択問題に常に正しく答え、XNUMX 人は完全にランダムに答えます。 ランダムな回答者が誰であるかはわかりません。 それぞれに XNUMX 択の質問を XNUMX つ尋ねてから、より多くの情報を得るために、間違いなく真実を語っている人を選ぶ必要があります。
方法は次のとおりです。 A に 0 桁目が 1、2、2 のいずれであるかを尋ねます。A が 0 と答えたとします。1 桁目が 2、1、または XNUMX のいずれかを B に尋ねます。B が XNUMX と答えたとします。次に、C に次の XNUMX つのステートメントのいずれかを選択してもらいます。
- Aだけが本当のことを言っている。
- Bだけが真実を語っています。
- どちらも真実を語っています。
C の言うことを信じて、もう一方の桁についてその人に質問することができます。 その理由を理解するために、A が嘘をついている場合、C は信頼でき、B が真実を語っていると言うと考えてみてください。 1 桁目は実際には 2 であり、XNUMX 桁目について B に質問することができます。 同様に、B が嘘をついている場合、C は再び信頼でき、A が真実を語っていると言うでしょう。 その場合、最初の桁は実際には XNUMX であり、XNUMX 番目の桁について A に質問できます。 最後に、C が嘘をついていても、A も B も信頼できるので、C の言うことを信じて選ぶことができます。 (そして、C が A と B の両方が真実を語っていると言うなら、どちらも真実であるに違いありません。) ここで重要なのは、質問の選択によって、C が A と B の両方に疑念を抱かせるような方法で嘘をつくことができないということです。 A と B の少なくとも XNUMX つが信頼できるものでなければならないため、ランダムな回答であっても、C が同意するものをいつでも選択できます。 XNUMX つすべてが一致する場合は、ナンバー プレートの両方の数字を既に持っています。
この話をパズルに戻す方法は次のとおりです。 スケールは A、B、C です。ナンバー プレートの 01 桁を次のようにコインに変換できます。1 はコイン 02、2 はコイン 10、3 はコイン 11、4 はコイン 12、5 はコイン 20、 6 はコイン 21、7 はコイン 22、8 はコイン 3 です。鋭い読者は、これが 00 進数 (または 1 進数) の数体系であることを認識するでしょう。 また、パズル XNUMX のように、このテクニックも機能する XNUMX 番目のコインに使用できる追加の数字 XNUMX があることに注意してください。
最初の計量では、コインを 3 桁目 (基数 1) で割ります。したがって、2 つのグループはコイン [3、4]、[5、6、7]、および [8、3、4] になります。 [5, 6, 7] と [8, 1, 1] をはかり A で量ります。A がうまく機能している場合、パズル 4 のように正しい最初の桁のグループが得られます。 [7, 2, 5]、[8, 3, 6]、[21, 6] の 7 桁目が同じものになります。 B が正常に機能していれば、正しい 8 桁目を取得できます。 1 回目の計量では、はかり C で、A が特定したグループと B が行ったグループを比較検討します。 この例に従うと、4 の場合、グループは [7, 7, 6] と [8, 1, 4] になります。 コイン 7 は同時に両面に置くことはできないので、[7, 6] と [8, 1] の重さを量ります。 A と B の両方が信頼できる場合、実際には 4 が正しい答えであり、C でどちらが軽くなったとしても問題ではないことに注意してください。たまたま C の重量が釣り合っている場合、XNUMX つのスケールすべてが一致し、わずか XNUMX 回の計量で答え (コイン XNUMX) が得られます。 A が信頼でき、B がそうでない場合、軽いコインは [XNUMX, XNUMX] にあり、スケール C が確認します。B が信頼でき、A がそうでない場合、軽いコインは [XNUMX, XNUMX] にあり、スケール Cも確認します。
したがって、XNUMX回の計量で、ライトコインを特定するか、XNUMXつのグループに絞り込み、作業スケールも特定しました. 残りは、はかり A またははかり B (いずれかのはかり C が同意した方) での XNUMX 回目の計量で行われます。
このソリューションは、驚くほど美しいと思います。
この方法を一般化して、3 つの中からライト コインを見つけることができます。2x コイン3枚x + 所定の天びんセットで 1 回の計量。 したがって、81 枚のコインには 1,000 回の計量が必要です。 コインの数が多い場合 (>~XNUMX)、さらに強力なソリューション 存在.
パズル4
あなたは16枚のコインを持っていますが、そのうちのXNUMX枚は重くて同じ重さです。 他のXNUMXつは軽量で同じ重量です。 どのコインが重いか軽いかわかりません。 コインは、特別なマーキングがあるものを除いて同じように見えます。 XNUMXつの良いスケールで、XNUMX回の計量で特殊コインが軽いか重いかを判断できますか？ あなたが始めて、XNUMXつの計量でこの問題を首尾よく解決することができるコインの最大数はいくつですか？
読者の XNUMX 人が結論付けたように、一見すると、このパズルを XNUMX 回の計量で行うのはほとんど不可能に思えます。 それにもかかわらず、ある程度の賢さでそれを行うことができます。 テッド & 春のライナー 正しい解決策を提供しました。 Ted は、注意を払う価値のある貴重な一般原則をいくつか提供しました。
まず、秤量からアンバランスな結果が得られるまで、特別なコインが重いか軽いかを判断するのに十分な情報が得られません。 したがって、不均衡な結果を強制しようとする必要があります。
第二に、バランスの取れた結果が得られた場合 (たとえば、特別なコイン A がコイン B のバランスを取るとします)、バランスが取れているコインを組み合わせて、さらに 4 つのコイン C と D と比較検討することができます。 そうしないと、類似したコインの数が 8 倍になり、次の計量でアンバランスな答えを得るのに役立つ可能性があります。 次の解決策に見られるように、最初の不均衡な結果が得られた場合は、XNUMX のべき乗 (XNUMX、XNUMX など) のコインの数でこのプロセスを逆に実行することもできます。
以下は、1回の計量ですべての場合に特殊コインAの種類を識別することができる全体的な手順です。 (B、C、D は計量 1 (W1) で A と同じ側に置かれた XNUMX 枚のコイン、X と Y は WXNUMX で使用されなかった XNUMX 枚のコインです。)
このパズルはロシアの数学者によって発明されました コンスタンチン・ノップ、コイン計量パズルの世界的権威。 彼の論文の多くはロシア語ですが、いくつかのコイン パズル (他の興味深いパズルの中でも) は、 ブログ 彼の協力者ターニャ・ホバノワの。
一般化については、32 枚の硬貨 (うち 16 枚は重い硬貨、16 枚は軽い硬貨) の中から特殊な硬貨の種類を見つけるのに同じ方法が機能するかどうかは、あなたにお任せします。
パズル5
あなたが持っている n 見た目が同じコインで、偽造されたものもあれば、他のものよりも軽いものもあります。 あなたが知っているのは、少なくともXNUMXつの偽造コインがあり、偽造コインよりも通常のコインが多いということだけです。 あなたの仕事は、すべての偽造コインを検出することです。
少なくとも XNUMX 枚のライト コインがあり、ライト コインよりも通常のコインの方が多いという事実により、このパズルは、少なくとも少数の場合、最初に表示されるよりも単純になります。 XNUMX枚からXNUMX枚までの計量回数を見てみましょう。
XNUMX 枚と XNUMX 枚のコインの場合、XNUMX 番目の条件ごとにライト コインが存在しない可能性があるため、計量は必要ありません。
コイン1枚：ライトコインXNUMX枚のみ。 パズル XNUMX につき XNUMX 回の計量が必要です。
XNUMX コイン: ライト コイン XNUMX 枚のみ。 追加の計量が XNUMX つ必要なので、 w = 2。
XNUMX コイン: ライト コイン XNUMX ～ XNUMX 枚。 これは最初の興味深いケースです。 問題は、コイン XNUMX 対 XNUMX、またはコイン XNUMX 対 XNUMX を比較検討する必要があるかどうかです。
XNUMX 対 XNUMX で比較検討すると、次のようになります。
- XNUMX つの不均衡な計量: XNUMX つの硬貨が発見されました。 完了です。
- XNUMX つのうちの XNUMX つのバランスの取れた計量: バランスの取れたコインは正常でなければならないため、最後のコインは別の計量が必要です。 w = 3。
- 5 回の秤量: XNUMX 回目の秤量では、前の各秤量から XNUMX 枚のコインを別の秤量します。 バランスが取れていれば、XNUMX つすべてが正常で、コイン XNUMX が軽いコインです。 これで完了です。 w = 3 です。 バランスが取れていない場合は、XNUMX 枚のライト コインが見つかったことになり、XNUMX 回の計量で完了です。
代わりに、XNUMX 対 XNUMX の重さを量る場合でも、XNUMX 回の重さを量る必要があります。これは、コインの両側が異なるか類似している可能性を区別する必要があるためです。 一緒にグループ化された少数の硬貨を使用した計量は、単一の硬貨を使用した計量よりも利点があるようには見えません.
これは、次の場合に当てはまります。
コイン XNUMX 枚: ライト コイン XNUMX ～ XNUMX 枚。 w = 4。
XNUMX コイン: ライト コイン XNUMX ～ XNUMX 枚。 w = 5。
XNUMX 枚のコイン: XNUMX ～ XNUMX 枚のライト コイン。 w = 6. このソリューションの構造は単純です。
- 最初に、XNUMX つのコインを次のコインに対して XNUMX 回計量します。 すべてのコインが使用されます。
- 最悪の場合: XNUMX つの計量値すべてのバランスがとれています (互いにバランスが取れている XNUMX つのライト コインがあります)。
- 次の 1 回の計量: 計量 2 のコインと計量 3 のコインを比較します。 同様に、重さ 4 のコインと重さ XNUMX のコインを比較します。
- これらの計量値の XNUMX つが不均衡になり、XNUMX つのライト コインが識別されます。 XNUMX回の計量で完了です。
申し訳ありませんが、0、0、1、2、3、4、5、6 のシーケンスは、 整数シーケンスのオンライン百科事典!
As ジョナス・トーゲルセン・シェルスタドリ 指摘された、解決策は w = n − 小さい数の場合は 2 ですが、これが大きな数の場合に変わらないことは証明されていません。 一部で n、複数のコインの計量を使用すると、より良い、またはより多くの計量を開始する可能性があります n − 2 が必要な場合があります。 2 枚のコインの解を XNUMX のすべての累乗に単純に一般化すると、次のようになります。 n − 2 のすべてのべき乗に対する重み付け回数の上限として 2。
Mark Pearson は、この問題とエラー訂正コードの類似性について議論し、可能な結果の数に基づく情報理論アプローチの使用を提案しました。 このようなアプローチを使用して、 マイク・ロバーツ より一般的なケースの下限を投稿しました。 春のライナー の近似値を導出しました。 ライナーも投稿 上界 公開された論文からですが、下限の境界はシャープではないことに注意してください n したがって、上記で検討した少数の場合は役に立ちません。 したがって、4 枚のコインの場合、引用された範囲は 16 から 5 の範囲であり、私たちの答えである XNUMX はその中間にあります。 J.ペイエット すべてのパズルに追加の数学的参照と境界を与えます。
参加された皆様、ありがとうございました。 今月の Insights 賞は Ted と Rainer aus dem Spring に贈られます。 おめでとう！
次回は新作でお会いしましょう 分析.
