جلسهی 14: راستگوها و دروغگوها Truth-Tellers and Liars
در قلعهای که هر کس یا همیشه راست میگوید یا همیشه دروغ: فرض کن، دنبال تناقض بگرد، حالتها را بشمار. معماهای کوچک، دایرهای از آدمها، و جملههایی دربارهی تعداد دروغگوها.
در این جلسه یاد میگیری
- با فرض کردن و رسیدن به تناقض، راستگو و دروغگو را مشخص میکنی.
- جملههای «دقیقاً k نفر دروغگوییم» را با شمردن حل میکنی.
- در دایرهای از آدمها کمترین و بیشترین تعداد دروغگو را پیدا میکنی.
درس
قلعهای با چهار نفر. هر کدام یا همیشه راست میگوید یا همیشه دروغ. روی هر نفر بزن و ببین با حرفش جور است یا نه. این قلعه چند جواب دارد؟
قانون طلایی: اگر کسی راستگو است، حرفش درست است؛ اگر دروغگو، حرفش غلط است. پس برای هر نفر: «راستگو بودن» = «درست بودنِ حرفش».
روش ۱، فرض و تناقض: فرض کن الف راستگوست، نتیجهها را دنبال کن؛ اگر به تناقض رسیدی، الف دروغگوست.
روش ۲، شمردن: در قلعهی بالا جملهها دربارهی «تعداد» دروغگوهاست. حداکثر یکی از این جملهها میتواند درست باشد (تعداد فقط یک عدد است!). اگر هیچکدام درست نباشد، هر ۴ نفر دروغگو هستند و جملهی ت درست میشود: تناقض. پس دقیقاً یکی راست میگوید و ۳ نفر دروغگو هستند: پ راستگوست.
دایرهی آدمها: n نفر دور یک میزند و هر کس میگوید «نفرِ سمت راستم دروغگوست». اگر یکی راستگو باشد، بغلیاش دروغگوست؛ حرفِ آن دروغگو غلط است، پس نفرِ بعدی راستگوست؛ و همینطور یکدرمیان. پس راستگو و دروغگو یکدرمیاناند و n باید زوج باشد؛ دقیقاً نصفشان دروغگو هستند.
اشتباه رایج: فراموش کردنِ اینکه حرفِ دروغگو «کاملاً غلط» است. اگر دروغگو بگوید «هر دو همسایهام دروغگو هستند»، یعنی دستکم یکی از همسایههایش راستگوست، نه اینکه هر دو راستگو باشند.
چالشها
- Three at the Well (آسان)
- Exactly One Liar (آسان)
- Four Guards (متوسط)
- Around the Table (متوسط)
- At Least One Liar Beside Me (سخت)
- Five Counting Statements (سخت)
- Try It in Python: Try Every Castle (سخت)
← جلسهی 13: استقرا: از کوچک به بزرگ جلسهی 15: بدترین حالت →