هفته‌ی گذشته در سیسیل ایتالیا، جزیره‌ی خانواده‌های مافیایی، پسر دون کورلئونه به قتل رسید. دون کورلئونه همه‌ی پدرخوانده‌های خانواده‌های مافیایی را به یک جلسه‌ی اضطراری دعوت کرده است. از آن‌جایی که همه‌ی آن‌ها مشارکت در قتل را تکذیب کرده‌اند؛ دون کورلئونه یک آزمون برای شناسایی دروغ‌گوها از راست‌گوها طراحی کرده است. پس از آن ‌که تمامی پدرخوانده‌ها دور میز $n$ نفره نشستند، دون کورلئونه از هر فرد می‌خواهد روی کاغذی بنویسد که نفر سمت راست او دروغ‌گو است یا راست‌گو. از کنار هم قرار دادن نوشته‌های پدر‌خوانده‌ها (به ترتیب نشستن دور میز) یک دنباله‌ی $n$تایی ساخته می‌شود. به این دنباله معتبر می‌گوییم، اگر حداقل به یک روش بتوان راست‌گو یا دروغ‌گو بودن را به $n$ نفر نسبت داد به طوری که:

• اگر فرد $x$ راست‌گو است، دروغ‌گویی یا راست‌گویی نفر سمت راست او همانند اظهار نظر فرد $x$ باشد.
• اگر فرد $x$ دروغ‌گو است، دروغ‌گویی یا راست‌گویی نفر سمت راست او مخالف اظهار نظر فرد $x$ باشد.

اگر دنباله معتبر نباشد دون کورلئونه از مافیای سیسیل ناامید شده و به زندگی همه پایان می‌دهد. چه تعدادی از دنباله‌ها معتبر هستند؟

1. $2^{n-1}$
2. $2^n$
3. 1
4. 2
5. $n$

• سوال قبل
• سوال بعد