چنگیزخان در شهر $A$ زندگی می‌کند. ۱۰ نفر از دوستان او از ساکنان شهر $B$ مدتی در شهر $A$ مهمان او هستند. او دوست ندارد که همه‌ی آن‌ها به شهرشان بازگردند. به همین دلیل٬ به روش عجیبی برایشان بلیط هواپیما می‌خرد. در کشور آن‌ها چند شرکت هواپیمایی هست و هرکدام تعدادی خط پرواز دارد. هر خط پرواز٬ بین دو شهر مشخص ($A$٬ $B$ یا شهرهای دیگر) است و رفتن از هر یک از آن دو را به دیگری میسر می‌کند. برای استفاده از یک خط پرواز باید بلیطی از شرکت ارائه‌کننده‌اش داشت و هر بلیط تنها برای یک بار استفاده اعتبار دارد. برای رفتن از یک شهر به شهر دیگر می‌توان با پرواز‌های مستقل از چند شهر میانی نیز عبور کرد٬ به شرطی که بلیط برای پرواز به شهر میانی را هم داشت.

چنگیز‌خان از هر شرکت هواپیمایی تنها یک بلیط می‌خرد و آن‌ها را به دوستانش می‌دهد. او ادعا می‌کند که بلیط‌هایی که خریده است خاصیت‌های زیر را دارند و این را به دوستانش توضیح می‌دهد:

• با این بلیط‌ها همه با هم نمی‌توانید از اینجا (شهر $A$) به شهر $B$ بازگردید.
• اگر از این‌ها دوتا بلیط را به دل‌خواه پس بگیرم (هر زوج بلیط ممکن)٬ با بلیط‌های ممکن حتما دست‌کم یک نفر از شما می‌تواند به شهر $B$ برسد.

آیا ممکن است چنگیزخان راست گفته باشد؟ آیا او حتماً دروغ گفته است؟ اگر امکان راست گفتن برای چنگیزخان وجود دارد٬ مثالی بزنید که با حرف‌های او سازگار باشد. در غیر این صورت٬ اثبات کنید این اتفاق هیچ‌گاه امکان‌پذیر نمی‌باشد.

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