バランスパズル

バランスパズル、または計量パズルとは、天秤を限られた回数使用して、複数の物（多くは硬貨）の重さを釣り合わせ、どれが他の物と重さが異なるかを判断する論理パズルである。

最も一般的なパズルのバリエーションの解決策は、次の表にまとめられています。^{[ 1 ]}

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

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

よく知られた例として、最大9個のコイン（またはボール）があり、そのうち1つだけが他のものより軽い偽物（異物）であるとします。この重さの違いは、天秤で重さを量ってみなければ分かりませんが、重さを量れるのはコイン自体だけです。たった2回の計量で、偽物コインをどのように見つけ出すことができるでしょうか？

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

13枚のコインがあり、そのうち1枚が他のコインと質量が異なることがわかっている場合、天秤と以下の3つのテストを使用すれば、どのコインが異なのかを理解するのは簡単です。

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

2) テスト1：4枚のコインからなる2つのグループを互いに比較する。

a. コインが釣り合っている場合、奇数のコインは5枚のうちの1枚なので、テスト2aに進みます。

b. 8枚のコインの中に異質なコインが含まれている場合は、12枚のコインの問題と同じように進めます。

3) テスト2a、5枚のコインのグループから選んだ3枚のコインと、8枚のコインの母集団から選んだ任意の3枚のコインとの比較：

a. 3枚のコインの合計が釣り合う場合、残りの2枚のコインの中に、釣り合わないコインが存在します。その2枚のコインのうち1枚を他のコインと比較します。釣り合う場合は、最後に試したコインが釣り合わないコインです。釣り合わない場合は、現在の試しているコインが釣り合わないコインです。

b. 3枚のコインの重さが釣り合わない場合、その3枚のコインの中に、重さが釣り合わないコインが1枚あります。天秤の揺れの方向（上向きは軽いコイン、下向きは重いコイン）に注意してください。3枚のコインのうち1枚を取り除き、もう1枚を天秤の反対側に移動させます（他のコインはすべて取り除きます）。重さが釣り合う場合は、取り除いたコインが重さが釣り合わないコインです。重さが釣り合う方向が変わる場合は、反対側に移動させたコインが重さが釣り合わないコインです。そうでない場合は、元の位置に残ったコインが重さが釣り合わないコインです。

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

\// 軽い /\\ 重い /\/ Bライト \/\ Bヘビー //\ Cライト \\/ Cヘビー \/– Dライト /\– Dヘビー –\/ E ライト –/\ E ヘビー /–\ F 軽い \–/ F 重い \\– Gライト //– Gヘビー –\\ H ライト –// H ヘビー －軽い／－重い /–– J ライト \–– J ヘビー –/– Kライト –\– Kヘビー ––/ L ライト ––\ L ヘビー ––– M より軽いか重いか (13 枚コインケース)、 または、すべてのコインの重さが同じ場合（12枚入りケース） 

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

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

この問題の一般化については、Chudnov ^{[ 7 ]で説明されている。}

させて$\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}}$離散的な [−1; 1]-立方体を で表す。 $\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}$th オブジェクトは標準重量です ${\displaystyle x_{i}=0;}$の重さ ${\displaystyle i}$th オブジェクトが定数 (未知の) 値だけ大きい (小さい) 場合 ${\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}$th の物体が計量に参加するのは、 ${\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}$ これらは許容される状況と呼ばれます。

それぞれの重量${\displaystyle \mathrm {h} }$集合の分割を誘導する${\displaystyle I^{n}}$平面（超平面）によって${\displaystyle [\mathrm {x}$ ;\mathrm {h} ]=0} を 3 つの部分に分割します ${\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}$第 1 ステップ、${\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 ${\displaystyle {\mathcal {A}}}$a) 一連の状況を特定すると言われている ${\displaystyle Z}$ 条件が ${\displaystyle |W(s|Z,{\mathcal {A}})|=1}$全員に満足 ${\displaystyle s\in S(Z{\mathcal {A}});}$ b) セット内のオブジェクトの種類を識別する ${\displaystyle Z}$ 条件が ${\displaystyle |W^{+}(s|Z{\mathcal {A}})|=1}$全員に満足 ${\displaystyle s\in S(Z{\mathcal {A}}).}$

^{[ 7 ]}では、いわゆる適切な集合に対して、${\displaystyle Z}$識別アルゴリズムは、タイプを識別するだけでなく、状況も識別します。${\displaystyle Z.}$

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

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

現時点では、状況を特定する他の完璧なWAが存在するかどうかは不明です。${\displaystyle I_{t}^{n}}$いくつかの値に対して${\displaystyle n,t}$さらに、一部の人にとって${\displaystyle t>2}$方程式には解が存在する ${\displaystyle \sum _{i=0}^{t}2^{i}C_{n}^{i}=3^{m}}$（3進符号のハミング限界 に対応）これは明らかに完全なWAの存在に必要である。${\displaystyle t=1}$完璧なWAはありません。${\displaystyle t=2}$この方程式は唯一の非自明な解を持つ${\displaystyle n=11,m=5}$これは、構築された完全なWAのパラメータを決定します。

• NRICHのグレートウェイトパズル