بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 14: راستگوها و دروغگوها Truth-Tellers and Liars

در قلعه‌ای که هر کس یا همیشه راست می‌گوید یا همیشه دروغ: فرض کن، دنبال تناقض بگرد، حالت‌ها را بشمار. معماهای کوچک، دایره‌ای از آدم‌ها، و جمله‌هایی درباره‌ی تعداد دروغگوها.

در این جلسه یاد می‌گیری

درس

قلعه‌ای با چهار نفر. هر کدام یا همیشه راست می‌گوید یا همیشه دروغ. روی هر نفر بزن و ببین با حرفش جور است یا نه. این قلعه چند جواب دارد؟

قانون طلایی: اگر کسی راستگو است، حرفش درست است؛ اگر دروغگو، حرفش غلط است. پس برای هر نفر: «راستگو بودن» = «درست بودنِ حرفش».
روش ۱، فرض و تناقض: فرض کن الف راستگوست، نتیجه‌ها را دنبال کن؛ اگر به تناقض رسیدی، الف دروغگوست.
روش ۲، شمردن: در قلعه‌ی بالا جمله‌ها درباره‌ی «تعداد» دروغگوهاست. حداکثر یکی از این جمله‌ها می‌تواند درست باشد (تعداد فقط یک عدد است!). اگر هیچ‌کدام درست نباشد، هر ۴ نفر دروغگو هستند و جمله‌ی ت درست می‌شود: تناقض. پس دقیقاً یکی راست می‌گوید و ۳ نفر دروغگو هستند: پ راستگوست.

دایره‌ی آدم‌ها: n نفر دور یک میزند و هر کس می‌گوید «نفرِ سمت راستم دروغگوست». اگر یکی راستگو باشد، بغلی‌اش دروغگوست؛ حرفِ آن دروغگو غلط است، پس نفرِ بعدی راستگوست؛ و همین‌طور یک‌در‌میان. پس راستگو و دروغگو یک‌در‌میان‌اند و n باید زوج باشد؛ دقیقاً نصفشان دروغگو هستند.
اشتباه رایج: فراموش کردنِ این‌که حرفِ دروغگو «کاملاً غلط» است. اگر دروغگو بگوید «هر دو همسایه‌ام دروغگو هستند»، یعنی دست‌کم یکی از همسایه‌هایش راستگوست، نه این‌که هر دو راستگو باشند.

چالش‌ها

  1. Three at the Well (آسان)
  2. Exactly One Liar (آسان)
  3. Four Guards (متوسط)
  4. Around the Table (متوسط)
  5. At Least One Liar Beside Me (سخت)
  6. Five Counting Statements (سخت)
  7. Try It in Python: Try Every Castle (سخت)

← جلسه‌ی 13: استقرا: از کوچک به بزرگ جلسه‌ی 15: بدترین حالت →