لغز التوازن

لغز التوازن أو لغز الوزن هو لغز منطقي يتعلق بموازنة العناصر - غالباً العملات المعدنية - لتحديد أي منها له وزن مختلف عن البقية، وذلك باستخدام موازين التوازن لعدد محدود من المرات.

يلخص الجدول التالي حلول أكثر أنواع الألغاز شيوعاً: ^{[ 1 ]}

معروف	هدف	الحد الأقصى للعملات المعدنية لعدد n  من عمليات الوزن	عدد عمليات وزن العملات المعدنية من الفئة ج
سواء كانت العملة المستهدفة أخف أو أثقل من غيرها	تحديد العملة	${\displaystyle 3^{n}}$	${\displaystyle \lceil \log _{3}(c)\rceil }$
العملة المستهدفة تختلف عن غيرها	تحديد العملة	${\displaystyle {\tfrac {1}{2}}(3^{n}-1)}$	${\displaystyle \lceil \log _{3}(2c+1)\rceil }$
العملة المستهدفة تختلف عن العملات الأخرى، أو أن جميع العملات متشابهة	حدد ما إذا كانت هناك عملة فريدة، وما إذا كانت أخف وزناً أم أثقل	${\displaystyle {\tfrac {1}{2}}(3^{n}-3)}$	${\displaystyle \lceil \log _{3}(2c+3)\rceil }$

على سبيل المثال، في اكتشاف عملة معدنية مختلفة في ثلاث عمليات وزن (${\displaystyle n=3}$) ، الحد الأقصى لعدد العملات التي يمكن تحليلها هو${\displaystyle {\tfrac {1}{2}}(3^{3}-1)=13}$لاحظ أنه مع${\displaystyle 3}$عمليات الوزن و${\displaystyle 13}$في حالة العملات المعدنية ، لا يمكن دائمًا تحديد طبيعة العملة الأخيرة (سواء كانت أثقل أو أخف من البقية)، ولكن يُكتفى بالقول إن العملات الأخرى متشابهة، مما يعني أن العملة الأخيرة هي العملة المختلفة. بشكل عام، مع${\displaystyle n}$من خلال عمليات الوزن، يمكن دائمًا تحديد هوية وطبيعة عملة معدنية واحدة غير متشابهة إذا كانت هناك${\displaystyle {\tfrac {1}{2}}(3^{n}-3)}$أو أقل من العملات المعدنية. في حالة ثلاث عمليات وزن، من الممكن العثور على عملة معدنية واحدة مختلفة ووصفها ضمن مجموعة من العملات المعدنية.${\displaystyle 12}$عملات معدنية .

ظهرت هذه النسخة المكونة من اثنتي عشرة قطعة نقدية من المسألة مطبوعةً في وقت مبكر من عام 1945 ^{[ 2 ] [ 3 ]} ، ويشرح غاي ونوفاكوفسكي أنها "كانت شائعة على جانبي المحيط الأطلسي خلال الحرب العالمية الثانية؛ حتى أنه تم اقتراح إسقاطها فوق ألمانيا في محاولة لتخريب مجهودها الحربي". ^{[ 3 ]}

من الأمثلة المعروفة وجود تسعة عناصر، كعملات معدنية (أو كرات)، متطابقة في الوزن باستثناء واحدة أخف وزنًا من البقية - وهي عملة مزيفة (قطعة شاذة). لا يُمكن ملاحظة الفرق إلا بوزنها على الميزان ، ولكن لا يُمكن وزن سوى العملات المعدنية نفسها. كيف يُمكن تحديد العملة المزيفة بوزنين فقط؟

تتضمن نسخة أكثر تعقيدًا اثنتي عشرة قطعة نقدية، إحدى عشرة منها متطابقة. إذا كانت إحداها مختلفة، فلا يمكننا تحديد ما إذا كانت أثقل أم أخف من البقية. في هذه الحالة، يمكن استخدام الميزان ثلاث مرات لتحديد ما إذا كانت هناك قطعة نقدية فريدة، وإذا وُجدت، يتم عزلها وتحديد وزنها بالنسبة إلى القطع الأخرى. (ظهر هذا اللغز وحله لأول مرة في مقال عام 1945. ^{[ 2 ]} ) للمسألة صيغة أبسط بثلاث قطع نقدية في عمليتي وزن، وصيغة أكثر تعقيدًا بتسع وثلاثين قطعة نقدية في أربع عمليات وزن.

إذا كان لدينا مجموعة من 13 قطعة نقدية، ومن المعروف أن واحدة منها تختلف (في الكتلة) عن البقية، فمن السهل تحديد أي قطعة نقدية هي باستخدام ميزان و3 اختبارات كما يلي:

1) قسّم العملات المعدنية إلى مجموعتين من 4 عملات ومجموعة ثالثة تحتوي على العملات الخمس المتبقية.

2) الاختبار 1، اختبر مجموعتي العملات المعدنية المكونة من 4 عملات مقابل بعضها البعض:

أ. إذا كانت العملات متوازنة، فإن العملة الفردية تقع ضمن مجموعة من 5، ثم ننتقل إلى اختبار 2أ.

ب. إذا كانت العملة الفردية من بين مجموعة من 8 عملات، فتابع بنفس الطريقة كما في مسألة 12 عملة.

3) الاختبار 2أ، الاختبار 3 للعملات المعدنية من مجموعة مكونة من 5 عملات معدنية مقابل أي 3 عملات معدنية من مجموعة مكونة من 8 عملات معدنية:

أ. إذا توازنت العملات الثلاث، فإن العملة المختلفة هي من بين العملتين المتبقيتين. اختبر إحدى العملتين مقابل أي عملة أخرى؛ إذا توازنتا، فإن العملة المختلفة هي آخر عملة لم تُختبر، وإذا لم تتوازنا، فإن العملة المختلفة هي عملة الاختبار الحالية.

ب. إذا لم تتوازن العملات الثلاث، فإن العملة الفردية هي من بين هذه العملات الثلاث. انتبه إلى اتجاه تأرجح الميزان (لأعلى يعني أن العملة الفردية خفيفة، ولأسفل يعني أنها ثقيلة). أزل إحدى العملات الثلاث، وانقل عملة أخرى إلى الجانب الآخر من الميزان (أزل جميع العملات الأخرى من الميزان). إذا استقر الميزان، فإن العملة الفردية هي العملة التي أُزيلت. إذا تغير اتجاه الميزان، فإن العملة الفردية هي التي نُقلت إلى الجانب الآخر، وإلا فإن العملة الفردية هي العملة التي بقيت في مكانها.

/// \\\ // /\\ \\/ \\/ //\ \\/ □ □ □ –\/ –/\ /–\ \–/ \\– //– –\\ –// ← /← /–– \–– –/– –\– ––/ ––\ ––– 

// خفيف /\\ ثقيل // خفيف B // ثقيل B //\ C خفيف \\/ C ثقيل ☆– D خفيف / ☆– D ثقيل -/ E خفيف -// E ثقيل /–\ F خفيف \–/ F ثقيل \\– G خفيف //– G ثقيل –\\ خفيف H –// ثقيل H أنا خفيف / أنا ثقيل /–– J خفيف \–– J ثقيل –/– K خفيف –\– K ثقيل خفيف -–/ خفيف -–\ ثقيل ––– M إما أخف أو أثقل (علبة تتسع لـ 13 قطعة نقدية)، أو أن جميع العملات المعدنية لها نفس الوزن (علبة تحتوي على 12 عملة معدنية) 

الوزن الأول: الجانب الأيسر: ADGI، الجانب الأيمن: BCFJ الوزن الثاني: الجانب الأيسر: BEGH، الجانب الأيمن: ACDK الوزن الثالث: الجانب الأيسر: CFHI، الجانب الأيمن: ABEL 

في تعميم آخر لهذه المسألة، لدينا ميزانان يمكن استخدامهما بالتوازي. على سبيل المثال، إذا كنت تعرف بالضبط أن عملة واحدة مختلفة ولكنك لا تعرف ما إذا كانت أثقل أو أخف من عملة عادية، فعندئذٍ في${\displaystyle n}$يمكنك حل المشكلة في أكثر من جولة واحدة.${\displaystyle (5^{n}-5)/2}$العملات المعدنية. ^{[ 6 ]}

تم وصف تعميم هذه المشكلة في تشودنوف. ^{[ 7 ]}

يترك${\displaystyle \mathbb {R} ^{n}}$كن${\displaystyle n}$الفضاء الإقليدي ذو الأبعاد 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}$يكون للجسم وزن قياسي إذا ${\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}$يشارك الجسم رقم 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}$ إذا كان (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} إلى ثلاثة أجزاء ${\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. أ وا ${\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.}$

كمثال على ذلك، الخوارزميات الديناميكية المثالية (ذات المسارين المتتاليين) ذات المعلمات${\displaystyle n=11,m=5,t=2}$تم بناء هذه القيم في المرجع ^{[ 7 ]} ، وهي تتوافق مع معلمات كود غولاي الثلاثي المثالي (كود فيرتاكاليو-غولاي). وفي الوقت نفسه، تم إثبات عدم وجود كود ترجيح ثابت (أي كود ترجيح) بنفس المعلمات.

كل خوارزمية من هذه الخوارزميات، باستخدام 5 عمليات وزن، تجد من بين 11 عملة معدنية ما يصل إلى عملتين مزيفتين قد تكونان أثقل أو أخف من العملات الحقيقية بنفس القيمة. في هذه الحالة، يحتوي نطاق عدم اليقين (مجموعة الحالات المقبولة) على${\displaystyle 1+2C_{11}^{1}+2^{2}C_{11}^{2}=3^{5}}$في هذه الحالات، أي أن منطقة WA المُنشأة تقع على طريق هامينغ المتجه إلى${\displaystyle t=2}$وبهذا المعنى فهو مثالي.

حتى الآن، لا يُعرف ما إذا كانت هناك نماذج أخرى مثالية لتحديد المواقف في${\displaystyle I_{t}^{n}}$لبعض قيم${\displaystyle n,t}$علاوة على ذلك، من غير المعروف ما إذا كان الأمر كذلك بالنسبة للبعض${\displaystyle t>2}$توجد حلول للمعادلة ${\displaystyle \sum _{i=0}^{t}2^{i}C_{n}^{i}=3^{m}}$ (الموافق لحد هامينغ للرموز الثلاثية) وهو أمر ضروري، بطبيعة الحال، لوجود WA مثالي. من المعروف فقط أنه بالنسبة لـ${\displaystyle t=1}$لا توجد كلمات مفتاحية مثالية، و${\displaystyle t=2}$لهذه المعادلة حل وحيد غير تافه${\displaystyle n=11,m=5}$والتي تحدد معايير الشبكة البلورية المثالية المُنشأة.

• لغز الأوزان العظيم في NRICH