لغز سكب الماء

ألغاز سكب الماء (وتُسمى أيضًا مسائل أباريق الماء ، ^أو مسائل الصب ^، أو ^ألغاز القياس ، أو ألغاز ^{فيلم "} داي هارد مع الانتقام" ⁾ هي نوع من الألغاز التي تتضمن مجموعة محدودة من أباريق الماء ذات سعات صحيحة معروفة (بوحدات قياس السوائل مثل اللتر أو الجالون ). في البداية، يحتوي كل إبريق على حجم صحيح معروف من السائل، ليس بالضرورة مساويًا لسعته.

تتساءل الألغاز من هذا النوع عن عدد خطوات سكب الماء من إبريق إلى آخر (حتى يفرغ أحدهما أو يمتلئ الآخر) اللازمة للوصول إلى حالة هدف محددة من حيث حجم السائل الذي يجب أن يكون موجودًا في إبريق أو أباريق معينة. ^{[ 3 ]}

بحسب متطابقة بيزو ، فإن مثل هذه الألغاز لها حلول إذا وفقط إذا كان الحجم المطلوب مضاعفًا للقاسم المشترك الأكبر لجميع سعات الأحجام الصحيحة للأباريق.

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

تعتمد هذه الأحجية القياسية على ثلاث أباريق سعتها 8 و5 و3 لترات. تُملأ هذه الأباريق في البداية بـ 8 و0 و0 لترات على التوالي. وفي المرحلة النهائية، يجب أن تُملأ بـ 4 و4 و0 لترات على التوالي. يمكن حل الأحجية في سبع خطوات، بالمرور عبر التسلسل التالي من الحالات (المُشار إليها بثلاثية بين قوسين تمثل أحجام الماء الثلاثة في الأباريق الثلاثة):

[8,0,0] → [3,5,0] → [3,2,3] → [6,2,0] → [6,0,2] → [1,5,2] → [1,4,3] → [4,4,0].

يكتب كولي (1926) أن هذا اللغز المحدد "يعود إلى العصور الوسطى" ويشير إلى ظهوره في كتاب الرياضيات المدرسي لباشيه في القرن السابع عشر.

بما أن القواعد لا تسمح إلا بالتوقف/الانعطاف على حدود الشبكة الديكارتية (أي عند السعة الكاملة لكل إبريق)، فإن الإجراءات القابلة للعكس الوحيدة (القابلة للعكس في خطوة واحدة) هي:

• نقل الماء من إبريق ممتلئ إلى أي إبريق آخر
• نقل الماء من أي إبريق إلى إبريق فارغ

الإجراءات الوحيدة التي لا رجعة فيها والتي لا يمكن عكسها في خطوة واحدة هي:

• نقل الماء من إبريق ممتلئ جزئياً إلى إبريق آخر ممتلئ جزئياً

باقتصارنا على العمليات العكسية فقط، يمكننا بناء حل المسألة انطلاقًا من النتيجة المرجوة. من النقطة [4,4,0]، لا يوجد سوى عمليتين عكسيتين: نقل 3 لترات من الإبريق سعة 8 لترات إلى الإبريق الفارغ سعة 3 لترات [1,4,3]، ونقل 3 لترات من الإبريق سعة 5 لترات إلى الإبريق الفارغ سعة 3 لترات [4,1,3]. لذا، يوجد حلان فقط لهذه المسألة.

[4,4,0] ↔ [1,4,3] ↔ [1,5,2] ↔ [6,0,2] ↔ [6,2,0] ↔ [3,2,3] ↔ [3,5,0] ↔ [8,0,0]

[4,4,0] ↔ [4,1,3] ↔ [7,1,0] ↔ [7,0,1] ↔ [2,5,1] ↔ [2,3,3] ↔ [5,3,0] ↔ [5,0,3] ↔ [8,0,0]

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

يوضح الرسم البياني طريقتين للحصول على 4 لترات باستخدام أباريق سعة 3 لترات و5 لترات، ومصدر مياه ومصرف على شبكة إحداثيات ديكارتية بخطوط قطرية ميلها -1 (بحيث${\displaystyle x+y=const.}$على هذه الخطوط القطرية، التي تمثل سكب الماء من إبريق إلى آخر. يمثل المحوران السيني والصادي كميات الماء في الإبريقين سعة 5 لترات و3 لترات على التوالي. بدءًا من النقطة (0، 0)، نتحرك على طول الخطوط في الشبكة، مع الانعطاف فقط عند حدودها، حتى نصل إلى الخط الأسود الذي يمثل 4 لترات في الإبريق سعة 5 لترات. تشير الخطوط المتصلة إلى السكب بين الإبريقين، وتشير الخطوط المتقطعة إلى ملء الإبريق، وتشير الخطوط المنقطة إلى تفريغه.

بدمج أي من الحلين، فإن اجتياز الخط 4L وعكس الحل الآخر يعيدنا إلى النقطة (0، 0)، مما ينتج عنه رسم بياني دوري . إذا وفقط إذا كانت أحجام الأباريق أولية فيما بينها ، تتم زيارة كل نقطة حدودية، مما يوفر خوارزمية لقياس أي كمية صحيحة تصل إلى مجموع الأحجام.

كما هو موضح في القسم السابق، يمكننا إيجاد حل للمسألة انطلاقًا من النتيجة المرجوة باستخدام العمليات العكسية فقط (إفراغ إبريق ممتلئ في الحوض وملء إبريق فارغ من الصنبور عمليتان عكسيتان). للحصول على 4 لترات باستخدام إبريقين سعة 3 لترات و5 لترات، نريد الوصول إلى النقطة (4، 0). من هذه النقطة، لا يوجد سوى عمليتين عكسيتين: ملء الإبريق الفارغ سعة 3 لترات من الصنبور (4، 3)، أو نقل 3 لترات من الماء من الإبريق سعة 5 لترات إلى الإبريق سعة 3 لترات (1، 3). لذلك، يوجد حلان فقط للمسألة:

(4, 0) ↔ (4, 3) ↔ (5, 2) ↔ (0, 2) ↔ (2, 0) ↔ (2, 3) ↔ (5, 0) ↔ (0, 0)

(4, 0) ↔ (1, 3) ↔ (1, 0) ↔ (0, 1) ↔ (5, 1) ↔ (3, 3) ↔ (3, 0) ↔ (0, 3) ↔ (0, 0)

يمكن تمثيل الرسم البياني للدورة بواسطة الأزواج المرتبة المتصلة بأفعال قابلة للعكس:

(0, 0) ↔ (5, 0) ↔ (2, 3) ↔ (2, 0) ↔ (0, 2) ↔ (5, 2) ↔ (4, 3) ↔ (4, 0) ↔ (1, 3) ↔ (1, 0) ↔ (0, 1) ↔ (5, 1) ↔ (3, 3) ↔ (3, 0) ↔ (0, 3) ↔ (0, 0)

والتي تحتوي على جميع الحالات الممكنة التي يمكن الوصول إليها باستخدام إبريق سعة 3 لترات وإبريق سعة 5 لترات. على سبيل المثال، من المستحيل الوصول إلى الحالة (1، 2) من الحالة الابتدائية (0، 0)، لأن الإبريقين في الحالة (1، 2) يكونان ممتلئين جزئيًا، ولا يمكن القيام بأي إجراء عكسي من هذه الحالة.

إبريق به ماء أولي

هناك صيغة أخرى ^{[ 6 ]} وهي عندما يكون لأحد الإبريقين حجم ماء معلوم في البداية؛ في هذه الحالة، تكون الأحجام الممكنة إما مضاعفات للقاسم المشترك الأكبر بين حجمي الإبريقين، بعيدًا عن الحجم المعلوم الموجود، أو من الصفر. على سبيل المثال، إذا كان أحد الإبريقين سعته 8 لترات فارغًا، والآخر سعته 12 لترًا ويحتوي على 9 لترات من الماء في البداية، فمع وجود مصدر (صنبور) ومصرف (حوض)، يمكن لهذين الإبريقين قياس أحجام 9 لترات، و5 لترات، ولتر واحد، وكذلك 12 لترًا، و8 لترات، و4 لترات، و0 لتر. أبسط حل لحجم 5 لترات هو (9، 0) ← (9، 8) ← (12، 5)؛ وأبسط حل لحجم 4 لترات هو (9، 0) ← (12، 0) ← (4، 8). يمكن تمثيل هذه الحلول بأسهم حمراء وزرقاء في شبكة إحداثيات ديكارتية بخطوط قطرية (ذات ميل -1 بحيث${\displaystyle x+y=const.}$على هذه الخطوط القطرية) متباعدة بمقدار 4 لترات، أفقيًا وعموديًا.

مرة أخرى، إذا اقتصرنا على العمليات العكسية فقط، فمن النقطة المطلوبة (5، 0)، لا يوجد سوى عمليتين عكسيتين: نقل 5 لترات من الماء من الإبريق سعة 12 لترًا إلى الإبريق سعة 8 لترات (0، 5)، أو ملء الإبريق الفارغ سعة 8 لترات من الصنبور (5، 8). لذلك، لا يوجد سوى حلين للمسألة:

(5, 0) ↔ (0, 5) ↔ (12, 5) ↔ (9, 8) ↔ (9, 0)

(5, 0) ↔ (5, 8) ↔ (12, 1) ↔ (0, 1) ↔ (1, 0) ↔ (1, 8) ↔ (9, 0)

بالنسبة لسؤال الـ 4 لترات، بما أن${\displaystyle 4\equiv 0\!\mod \!4}$يتطلب حل المسألة إجراءً واحداً لا رجعة فيه؛ قد يكون ذلك ببساطة سكب 9 لترات من الماء من الإبريق سعة 12 لترًا إلى الحوض (0,0)، أو ملؤه بالكامل إلى 12 لترًا من الصنبور (12,0). بعد ذلك، يمكننا بناء حلولنا عكسيًا كما في السابق.

(4, 0) ↔ (4, 8) ↔ (12, 0) ← (9, 0)

(4, 0) ↔ (0, 4) ↔ (12, 4) ↔ (8, 8) ↔ (8, 0) ↔ (0, 8) ↔ (0, 0) ← (9, 0)

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

يُظهر الرسم البياني المركزي على اليمين حلّين للغز 8 و5 و3 لترات. تشير المنطقة الصفراء إلى التركيبات الممكنة باستخدام الأباريق. بدءًا من المربع، تُظهر المسارات الحمراء المتصلة والزرقاء المتقطعة انتقالات الصب. عند وصول رأس الرسم البياني إلى المثلث الأسود المنقط، يكون قد تم قياس 4 لترات. صبٌّ آخر إلى المعين يُعطي 4 لترات في كلٍّ من إبريقَي 8 و5 لترات.

المسار الأزرق أقصر بخطوة واحدة من مسار لغز الإبريقين المزود بصنبور ومصرف، حيث يمكننا تجميع 4 لترات في الإبريق سعة 8 لترات، وهو غير موجود في نسخة الإبريقين.

• لغز حرق الحبل ، وهو نوع آخر من الألغاز التي تتضمن الجمع بين القياسات
• تأثير التثبيت

• كولي، إليزابيث ب. ( 1926). "ملاحظة حول معادلة ديوفانتية خطية". أسئلة ومناقشات. المجلة الرياضية الأمريكية الشهرية . 33 (7): 379-381 . doi : 10.2307/2298647 . JSTOR 2298647. MR 1520987 .  
• تويدي، إم سي كيه (1939). "طريقة بيانية لحل ألغاز قياس تارتاليان". المجلة الرياضية . المجلد  23، العدد 255.  الصفحات 278-282 . JSTOR 3606420 .  
• ساكسينا، جي بي (1968). “التوجيه الأمثل العشوائي”. Unternehmensforschung . 12 (1): 173-177 . دوى : 10.1007 / BF01918326 . S2CID 10064660 . 
• أتوود، مايكل إي.؛ بولسون، بيتر جي. (1976). "نموذج عملية لمشاكل إبريق الماء". علم النفس المعرفي . 8 (2): 191-216 . doi : 10.1016/0010-0285(76)90023-2 . S2CID 54388726 . 
• ريم، مارتن؛ تشو، يونغ (1982). "برنامج ذو مساحة ثابتة وتعقيد إخراج خطي لمسألة السفن الثلاث" . مجلة علوم برمجة الحاسوب . 2 (2): 133-141 . doi : 10.1016/0167-6423(82)90011-9 .
• توماس، جلانفرويد ب. (1995). "مسألة أباريق الماء: حلول من منظور الذكاء الاصطناعي والرياضيات". الرياضيات في المدرسة . المجلد  24، العدد  2. الصفحات 34-37 . JSTOR 30215221 .  
• موراي-لاسو، ماجستير (2003). "ألغاز الرياضيات، والأفكار القوية، والخوارزميات، والحواسيب في تعليم حل المشكلات" . مجلة البحوث التطبيقية والتكنولوجيا . المجلد  1، العدد  3. الصفحات 215-234 . 
• لالشيف، زدرافكو فوتوف؛ فاربانوفا، مارجريتا جينوفا؛ فوتوڤا، إيريرنا زدرافكوفا (2009). "طريقة بيرلمان الهندسية في حل مسائل صب السوائل" .
• جوتشالككس، مارك (2011). "توجيه التدفق الأحادي عبر الشبكة". هندسة سلسلة التوريد . السلسلة الدولية في بحوث العمليات وعلوم الإدارة. المجلد  161. الصفحات 155-180 . doi : 10.1007/978-1-4419-6512-7_6 . ISBN  978-1-4419-6511-0.