バランスパズル

バランスパズルまたは計量パズルは、限られた回数だけ天秤を使用してアイテム（多くの場合はコイン）のバランスを取り、どのアイテムが他のアイテムと重さが異なるかを判断する 論理パズルです。

最も一般的なパズルのバリエーションの解答は次の表にまとめられている: ^[1]

たとえば、3 回の計量 ( ⁠ ⁠${\displaystyle n=3}$ ) で異なるコインを検出する場合、分析できるコインの最大数は⁠ ⁠${\displaystyle {\tfrac {1}{2}}(3^{3}-1)=13}$です。⁠ ⁠ 回の${\displaystyle 3}$計量と⁠ ⁠${\displaystyle 13}$コインでは、最後のコインの性質 (他のコインより重いか軽いか) を常に判断できるわけではなく、他のコインがすべて同じであること (最後のコインが異なるコインであることを意味する) のみを判断することに注意してください。 一般に、⁠ ⁠回の計量では、コインが${\displaystyle n}$⁠ ⁠${\displaystyle {\tfrac {1}{2}}(3^{n}-3)}$以下であれば、常に 1 枚の異なるコインの正体と性質を判断できます。 ⁠ ⁠ 回の計量の場合、 ⁠ ⁠${\displaystyle 12}$コインのコレクションの中から 1 枚の異なるコインを見つけて説明することができます。

この12枚のコインを使った問題は、1945年には早くも印刷物として登場しており^{[2] [3} ] 、ガイとノワコウスキーは「第二次世界大戦中は大西洋の両側で人気があり、ドイツの戦争努力を妨害するために投下する案さえ提案された」と説明している^{[3] 。}

よく知られている例としては、コイン（またはボール）など、重さが 9 個まで同じで、1 個だけが他のものより軽い、つまり偽物（変わったもの）があるというものがあります。違いは秤で計量することによってのみ認識できますが、計量できるのはコイン自体だけです。2 回の計量だけで偽造コインをどうやって特定できるのでしょうか。

解決策を見つけるには、まず、1 回の計量で軽いコインを見つけることができるアイテムの最大数を検討します。可能な最大数は 3 です。軽いコインを見つけるには、3 つ目のコインを除いて任意の 2 つのコインを比較します。2 つのコインの重さが同じ場合、軽いコインは天秤に載っていないコインの 1 つである必要があります。そうでない場合は、天秤で軽いと示されたコインです。

ここで、9 枚のコインが 3 枚ずつ 3 段に積み重なっているところを想像してください。1 回の移動で、3 つの段のうちどれが軽いか (つまり、軽いコインが入っている段) がわかります。その後、その軽い段の中から軽いコインを特定するには、さらに 1 回の移動が必要です。つまり、2 回の計量で、3 × 3 = 9 枚のセットから 1 枚の軽いコインを見つけることができます。

拡張すると、27 枚のコインの中から珍しい軽いコインを見つけるには 3 回の計量しか必要ありませんが、81 枚のコインの中からそれを見つけるには 4 回の計量が必要になります。

より複雑なバージョンでは、12枚のコインのうち11枚が同じものになります。1枚でも違うものがあれば、それが他のコインより重いのか軽いのかはわかりません。今回は、天秤を3回使用して、ユニークなコインがあるかどうかを判断します。もしある場合は、それを分離して他のコインに対する相対的な重さを判断します。(このパズルとその解答は、1945年の記事で初めて発表されました。^[2] ) この問題には、2回の計量で3枚のコインを使用するより単純なバージョンと、4回の計量で39枚のコインを使用するより複雑なバージョンがあります。

この問題には複数の解法がある。3進法の番号付けを使えば、より多くのコインに簡単に拡張できる。すなわち、各コインに3進法の3桁の異なる数字のラベルを付け、プレートのラベルと同じn桁目のラベルが付いたすべてのコインをn番目に計量する（プレートは3枚あり、スケールの両側に0と2のラベルが付いており、スケールから外れたところに1のラベルが付いている）。^[4]その他の段階的な手順は以下のとおり。この問題ではそれほど単純ではなく、2回目と3回目の計量は以前に何が起こったかによって決まるが、必ずしもそうである必要はない（下記参照）。

• それぞれの側に 4 枚のコインが置かれます。次の 2 つの可能性があります。

1. 片側がもう片側より重い。この場合、重い側から 3 枚のコインを取り除き、軽い側から 3 枚のコインを重い側に移動し、最初に計量しなかった 3 枚のコインを軽い側に置きます。(どのコインがどれであるかを覚えておいてください。) 3 つの可能性があります。

1.a) 最初に重かった側が、まだ重いです。これは、そこに留まったコインの方が重いか、軽い側に留まったコインの方が軽いかのどちらかを意味します。これらのうちの 1 つを他の 10 枚のコインの 1 つと比較すると、どちらが正しいかがわかり、パズルが解けます。

1.b) 最初に重かった側が、2 回目には軽くなります。つまり、軽い側から重い側に移った 3 枚のコインのうち 1 枚が軽いコインです。3 回目の試みでは、これらのコインのうち 2 枚を互いに重さを量ります。1 枚の方が軽い場合は、それが唯一のコインです。バランスが取れている場合は、3 枚目のコインが軽いコインです。

1.c) 両側が均等です。これは、重い側から取り除かれた 3 枚のコインのうち 1 枚が重いコインであることを意味します。3 回目の試みでは、これらのコインのうち 2 枚を互いに重さを量ります。1 枚の方が重い場合は、それが唯一のコインです。バランスが取れている場合は、3 枚目のコインが重いコインです。

2. 両側が同数の場合。この場合、8 枚のコインはすべて同じなので、別にしておけます。残りの 4 枚のコインのうち 3 枚を天秤の片側に置きます。8 枚の同じコインのうち 3 枚を反対側に置きます。次の 3 つの可能性があります。

2.a) 残りの 3 枚のコインの方が軽いです。この場合、3 枚のコインのうち 1 枚が異質で、より軽いことがわかります。3 枚のコインのうち 2 枚を取り、互いに重さを量ります。天秤が傾いたら、軽いコインが異質です。2 枚のコインのバランスが取れたら、天秤に載っていない 3 枚目のコインが異質で、より軽いです。

2.b) 残りの 3 枚のコインの方が重いです。この場合、3 枚のコインのうち 1 枚が異質で、より重いことがわかります。3 枚のコインのうち 2 枚を取り、互いに重さを量ります。天秤が傾いたら、重いコインが異質です。2 枚のコインがつり合ったら、天秤に載っていない 3 枚目のコインが異質で、より重いです。

2.c) 残りの 3 枚のコインのバランス。この場合、残りのコインを他の 11 枚のコインのいずれかと比較して重さを量るだけで、重いか、軽いか、同じかがわかります。

13 枚のコインのうち 1 枚が他のコインと異なる (質量が異なる) ことが分かっている場合、天秤と次の 3 つのテストでどのコインであるかを簡単に判別できます。

1) コインを 4 枚ずつ 2 つのグループに分け、残りの 5 枚を 3 番目のグループに分けます。

2) テスト 1、4 枚のコインの 2 つのグループを互いに比較してテストします。

a. コインのバランスが取れている場合は、奇数のコインは 5 個の母集団の中にあるため、テスト 2a に進みます。

b. 8 枚のコインの中に奇数のコインがある場合は、12 枚のコインの問題と同じ手順で進めます。

3) テスト 2a、5 枚のコインのグループからのコインと 8 枚のコインの母集団からの任意の 3 枚のコインとのテスト 3:

a. 3 枚のコインのバランスが取れている場合、奇数コインは残りの 2 枚のコインの集団の中にあります。2 枚のコインのうち 1 枚を他のコインと比較してテストします。バランスが取れている場合、奇数コインはテストされていない最後のコインです。バランスが取れていない場合、奇数コインは現在のテスト コインです。

b. 3 枚のコインのバランスが取れていない場合、この 3 枚のコインの集団から奇数コインが選ばれます。天秤の揺れの方向に注意してください (上向きは奇数コインが軽いこと、下向きは重いことを意味します)。3 枚のコインのうち 1 枚を取り除き、もう 1 枚を天秤の反対側に移動します (他のすべてのコインを天秤から取り除きます)。天秤が均衡した場合、奇数コインは取り除かれたコインです。天秤の方向が逆転した場合、奇数コインは反対側に移動されたコインです。それ以外の場合、奇数コインはそのままの位置に残ったコインです。

参照用の本物のコインが 1 枚ある場合、疑わしいコインは 13 枚になります。コインに 1 から 13 までの番号を付け、本物のコインに 0 の番号を付け、任意の順序で次の計量を実行します。

• 0、1、4、5、6対7、10、11、12、13
• 0、2、4、10、11対5、8、9、12、13
• 0、3、8、10、12対6、7、9、11、13

秤のバランスが崩れたのは 1 回だけであれば、1、2、3 のコインのうちの 1 枚であるはずです。これらのコインは 1 回の計量でしか現れません。バランスが取れていない場合は、すべての計量で現れる 10 ～ 13 のコインのうちの 1 枚です。27 の結果のそれぞれに対応する偽造コインを 1 枚選ぶことは常に可能です (13 枚のコインのうち 1 枚が重すぎるか軽すぎる場合は 26 通りの可能性があります)。ただし、すべての計量がバランスが取れている場合は偽造コインはありません (または重量が正しい)。これらの計量からコイン 0 と 13 を削除すると、12 枚のコインの問題に対する一般的な解決方法が 1 つ得られます。

2 枚のコインが偽造である場合、この手順では通常、どちらか一方ではなく、本物のコインが選択されます。たとえば、コイン 1 と 2 の両方が偽造である場合、コイン 4 または 5 のいずれかが誤って選択されます。

このパズルの緩やかなバリエーションでは、偽造コインを見つけるだけでよく、他のコインに対する相対的な重量を必ずしも知る必要はありません。この場合、明らかに、以前にすべてのコインをある時点で計量したソリューションは、1 枚の余分なコインを処理するために適応できます。このコインは秤に載せられることはありませんが、すべての計量が均衡している場合は、偽造コインとして選択されます。ある時点で秤に載せられ、偽造コインとして選択されたコインには、常に他のコインに対する相対的な重量を割り当てることができるため、これ以上のことはできません。

結果に関係なく同じコインセットを計量する方法では、

1. （12枚のコインA～Lのうち）重さがすべて同じかどうかを判断したり、珍しいコインを見つけてそれが軽いか重いかを判断したりできます。
2. (13枚のコインA～Mの中から) 奇数のコインを見つけ、12/13の確率で、それが軽いか重いかを判定します (残りの1/13の確率では、単に異なるだけです)。

各計量で起こり得る 3 つの結果は、左側が軽い場合は「\」、右側が軽い場合は「/」、両側が同じ重さの場合は「–」で表すことができます。計量を表す記号は、順番に並べられています。たとえば、「//–」は、1 回目と 2 回目の計量では右側が軽く、3 回目の計量では両側が同じ重さであることを意味します。3 回の計量では、次の 3 ³ = 27 の結果が得られます。「–––」を除き、セットは、右側の各セットに「/」があり、左側のセットに「\」があるように分割され、その逆も同様です。

/// \\\

\// /\\
/\/ \/\
//\ \\/

\/– /\–
–\/ –/\
/–\ \–/

\\– //–
–\\ –//
\–\ /–/

/–– \––
–/– –\–
––/ ––\

–––

各計量で意味のある結果が得られるのは、左側のコインの数が右側の数と等しい場合のみであるため、最初の行は無視して、各列に同じ数の「\」記号と「/」記号（それぞれ 4 つ）が含まれるようにします。行にはラベルが付けられ、コインの順序は関係ありません。

\// 軽い /\\ 重い
/\/ B ライト \/\ B ヘビー
//\ C ライト \\/ C ヘビー

\/– D ライト /\– D ヘビー
–\/ E ライト –/\ E ヘビー
/–\ F 軽い \–/ F 重い

\\– G ライト //– G ヘビー
–\\ H ライト –// H ヘビー
\–\ 私は軽い /–/ 私は重い

/–– J ライト \–– J ヘビー
–/– K ライト –\– K ヘビー
––/ L ライト ––\ L ヘビー

––– M 軽いまたは重い（13枚入りケース）、
    またはすべてのコインの重さが同じ（12枚入りケース）

上記の結果のパターンを使用して、各計量におけるコインの構成を決定できます。たとえば、「\/– D light」というセットは、コイン D が最初の計量では左側にあり (その側が軽くなるようにするため)、2 回目では右側にあり、3 回目では使用されていないことを意味します。

1回目の計量：左側：ADGI、右側：BCFJ
2回目の計量：左側：BEGH、右側：ACDK
3回目の計量：左側：CFHI、右側：ABEL

その後、結果がテーブルから読み上げられます。たとえば、最初の2回の計量で右側が軽く、3回目の計量で両側の重さが同じだった場合、対応するコード「//– G 重い」は、コインGが奇数であり、他のコインよりも重いことを意味します。^[5]

この問題の別の一般化では、並行して使用できる2つの天秤があります。たとえば、1枚のコインが他のコインと異なることはわかっているが、それが通常のコインよりも重いか軽いかはわからない場合、ラウンドでは最大でコインの数で問題を解くことができます。^[6]${\displaystyle n}$${\displaystyle (5^{n}-5)/2}$

この問題の一般化についてはChudnovによって説明されている。^[7]

を- 次元ユークリッド空間とし、をからの ベクトルと のベクトル の内積とします。ベクトル と部分集合 に対して、 演算とがそれぞれ  ; 、、 で における離散 [-1; 1] 立方体 、すなわち、アルファベット上の 長さのすべてのシーケンスの集合を表すものとします。 集合は 、点 を中心とする 半径 (ハミング計量) の離散球です。オブジェクトの相対的な重さは 、オブジェクトの重さの構成を定義するベクトルによって与えられます。つまり、 番目のオブジェクトの重さが (それぞれ)の場合に定数 (未知) だけ大きい (小さい) 場合、 番目のオブジェクトは標準の重さを持ちます 。ベクトルは、 オブジェクトのタイプ、つまり標準タイプ、非標準タイプ (つまり、タイプの構成) を特徴付けますが、非標準オブジェクトの相対的な重さに関する情報は含まれていません。 ${\displaystyle \mathbb {R} ^{n}}$${\displaystyle n}$${\displaystyle [\mathrm {e} ^{1},\mathrm {e} ^{2}]}$ ${\displaystyle \mathrm {e} ^{1}}$${\displaystyle \mathrm {e} ^{2}}$${\displaystyle \mathbb {R} ^{n}.}$${\displaystyle \mathrm {e} =(e_{1},\dots ,e_{n})\in \mathbb {R} ^{n}}$${\displaystyle E=\{\mathrm {e} ^{j}\}\subseteq \mathbb {R} ^{n},}$${\displaystyle (\cdot )^{*}}$${\displaystyle (\cdot )^{+}}$${\displaystyle \mathrm {e} ^{*}=(sign(e_{i}))_{i}}$${\displaystyle E^{*}=\{(\mathrm {e} ^{j})^{*}\}}$${\displaystyle \mathrm {e} ^{+}=(|sign(e_{i})|)_{i}}$${\displaystyle E^{+}=\{(\mathrm {e} ^{j})^{+}\}.}$${\displaystyle I^{n}}$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle n}$${\displaystyle I=\{-1,0,1\}}$${\displaystyle I_{t}^{n}=\{\mathrm {x} \in I^{n}|w(\mathrm {x} )\leq t\}\subseteq I^{n}}$${\displaystyle t}$ ${\displaystyle w()}$${\displaystyle \mathrm {0} .}$${\displaystyle n}$${\displaystyle \mathrm {x} =(x_{1},\dots ,x_{n})\in I^{n},}$${\displaystyle i}$${\displaystyle x_{i}=0;}$${\displaystyle i}$${\displaystyle x_{i}=1}$${\displaystyle x_{i}=-1}$${\displaystyle \mathrm {x} ^{+}}$

計量（チェック）はベクトルで指定され、 状況に対する計量の結果は、ベクトルで指定される計量には、次の解釈があります。特定のチェックについて 、の場合、 番目のオブジェクトが計量に参加します 。 の場合、このオブジェクトは左の天秤皿に置かれ、 の場合、このオブジェクトは右の皿に置かれます。各計量 について、両方の皿には同じ数のオブジェクトが含まれている必要があります。いずれかの皿のオブジェクトの数が本来あるべき数よりも少ない場合、この皿はいくつかの参照オブジェクトを受け取ります。計量の結果は、次のケースを表します。 の場合、天秤、 の場合、左の皿が右の皿より重く、 の場合、右の皿が左の皿より重くなります。 オブジェクトのグループの重量の分布に関する初期情報の不完全性は、オブジェクトの重量の許容分布の集合によって特徴付けられます。これは許容状況の集合とも呼ばれ、 の要素は 許容状況と呼ばれます。 ${\displaystyle \mathrm {h} \in I^{n};}$${\displaystyle \mathrm {x} \in I^{n}}$${\displaystyle s(\mathrm {x} ;\mathrm {h} )=sign([\mathrm {x} ;\mathrm {h} ]).}$${\displaystyle \mathrm {h} =(h_{1},\dots ,h_{n})}$${\displaystyle i}$${\displaystyle h_{i}\neq 0}$${\displaystyle h_{i}<0}$${\displaystyle h_{i}>0.}$${\displaystyle \mathrm {h} }$${\displaystyle r(\mathrm {h} )=[\mathrm {h} ;1,\dots ,1]}$${\displaystyle s(\mathrm {x} ;\mathrm {h} )}$${\displaystyle s(\mathrm {x} ;\mathrm {h} )=0}$${\displaystyle s(\mathrm {x} ;\mathrm {h} )=-1}$${\displaystyle s(\mathrm {x} ;\mathrm {h} )=1.}$${\displaystyle Z\subseteq I^{n},}$${\displaystyle z\in Z}$

各重み付けは、平面（超平面）による集合の3つの部分へ の分割を誘導し、 集合の対応する分割を定義します 。 ${\displaystyle \mathrm {h} }$${\displaystyle I^{n}}$${\displaystyle [\mathrm {x} ;\mathrm {h} ]=0}$${\displaystyle W(s|I^{n};\mathrm {h} )=\{\mathrm {x} \in I^{n}|s(\mathrm {x} ;\mathrm {h} )=s\}}$${\displaystyle s\in I,}$${\displaystyle Z=W(0|Z,\mathrm {h} )+W(1|Z,\mathrm {h} )+W(-1|Z,\mathrm {h} ),}$${\displaystyle W(s|Z,\mathrm {h} )=W(s|I^{n},\mathrm {h} )\cap Z.}$

定義 1 。長さ の 重み付けアルゴリズム (WA)は、前のステップでの重み付け の結果からアルゴリズムの 各 ステップでのチェックを決定する関数 である シーケンスです (は与えられた初期チェックです)。 ${\displaystyle {\mathcal {A}}}$${\displaystyle m}$${\displaystyle {\mathcal {A}}=<\mathrm {A} _{1},\dots ,\mathrm {A} _{m}>,}$${\displaystyle \mathrm {A} _{j}:I^{j-1}\to I^{n}}$${\displaystyle \mathrm {h} ^{j}=\mathrm {A} _{j}(s^{j-1});\mathrm {h} ^{j}\in I^{n},}$${\displaystyle j}$${\displaystyle j=1,2,\dots ,m,}$${\displaystyle \mathrm {s} ^{j-1}=(s_{1},\dots ,s_{j-1})\in I^{j-1}}$${\displaystyle \mathrm {h} ^{1}=\mathrm {A} _{1}()}$

をすべての- 症候群 の集合とし 、 を同じ症候群の状況の集合とします 。 つまり、${\displaystyle S(Z,{\mathcal {A}})}$${\displaystyle (Z,{\mathcal {A}})}$${\displaystyle W(s|{\mathcal {A}})\subseteq I}$${\displaystyle s}$${\displaystyle W(s|{\mathcal {A}})=\{\mathrm {z} \in I^{m}|s(z|{\mathcal {A}})=s\}}$${\displaystyle W(s|Z;{\mathcal {A}})=W(s|{\mathcal {A}})\cap Z.}$

定義2 . WAは 、次のことをすると言われています。a) 条件 がすべて満たされている 場合、セット内の状況を識別する b) 条件がすべて満たされている 場合、 セット内のオブジェクトのタイプを識別する ${\displaystyle {\mathcal {A}}}$${\displaystyle Z}$${\displaystyle |W(s|Z,{\mathcal {A}})|=1}$${\displaystyle s\in S(Z{\mathcal {A}});}$${\displaystyle Z}$${\displaystyle |W^{+}(s|Z{\mathcal {A}})|=1}$${\displaystyle s\in S(Z{\mathcal {A}}).}$

^[7]では、いわゆる適切な集合に対して、型を識別するアルゴリズムが、${\displaystyle Z}$${\displaystyle Z.}$

例として、^[7]では、完全な3値ゴレイコード（Virtakallio-Golayコード）のパラメータに対応するパラメータを持つ完全な動的（2カスケード）アルゴリズムが構築されています。同時に、同じパラメータを持つ静的WA（つまり重み付けコード）は存在しないことが確立されています。 ${\displaystyle n=11,m=5,t=2}$

5 回の計量を使用するこれらのアルゴリズムはそれぞれ、11 枚のコインの中から、本物より同じ値だけ重いか軽い可能性のある偽造コインを最大 2 枚見つけます。この場合、不確実性領域 (許容される状況の集合) には状況が含まれます。つまり、構築された WA はハミング境界上にあり、この意味では完璧です。 ${\displaystyle 1+2C_{11}^{1}+2^{2}C_{11}^{2}=3^{5}}$${\displaystyle t=2}$

現在までに、のいくつかの値が の場合にの状況を識別する他の完全な WA が存在するかどうかはわかっていません。さらに、 のいくつかに対して、完全な WA の存在に明らかに必要な方程式 (3 値符号のハミング境界 に対応) の解が存在するかどうかもわかっていません。 については完全な WA が存在せず、 についてはこの方程式に、構築された完全な WA のパラメータを決定する 唯一の非自明な解があることだけがわかっています。${\displaystyle I_{t}^{n}}$${\displaystyle n,t}$${\displaystyle t>2}$${\displaystyle \sum _{i=0}^{t}2^{i}C_{n}^{i}=3^{m}}$${\displaystyle t=1}$${\displaystyle t=2}$${\displaystyle n=11,m=5}$

• 2番目のパズルのプレイ可能な例
• 2皿天秤と一般化偽造硬貨問題