سوال ۸
هفت کشور از جمله ایران برای میزبانی مسابقات جهانی المپیاد کامپیوتر در سال ۲۰۱۷ نامزد شده‌اند. برای انتخاب کشور میزبان، هیئت داوران در هر مرحله دو کشور از میان کشورهای باقی‌مانده را به‌طور تصادفی انتخاب می‌کند و بر اساس نظر داوران، کشور بازنده را از دور خارج می‌کند. این کار تا زمانی ادامه پیدا می‌کند که تنها یک کشور باقی بماند. تنها کشور باقی‌مانده میزبان مسابقات خواهد شد. فرض کنید از قبل نظر هیئت داوران را به ازای هر دو کشور انتخاب‌شده می‌دانیم. نظر هیئت داوران در جدول مقابل آمده است. به ازای $1\leq i \neq j \leq 7$ اگر عددی که در ردیف $i$ام و ستون $j$ام آمده است برابر ۱ باشد، کشور $i$ برنده
خواهد شد (یعنی نظر هیئت دواران با کشور $i$ است). در غیر این‌صورت، کشور $j$ برنده خواهد شد.
با توجه به این جدول چند کشور شانس میزبانی را خواهند داشت؟
- ۱
- ۳
- ۵
- ۶
- ۷
راهنمایی
جدول را به یک گراف جهتدار تبدیل کنید.
پاسخ
گزینه‌ی ۲ درست است.
یک گراف کامل ۷ راسی با شماره راس‌های ۱ تا ۷ را در نظر بگیرید. اگر بین دو کشور $i$ و $j$، نظر هیئت داوران با کشور $i$ بود، یال بین این دو راس را از $j$ به $i$ جهتدار می‌کنیم. به سادگی می‌توان ثابت کرد کشور $i$ شانس میزبانی دارد اگر و فقط اگر از همه‌ی راس‌های گراف فوق به راس $i$ مسیر وجود داشته باشد. مولفه‌های قویا همبند گراف فوق را پیدا می‌کنیم. کشورهایی که رئوس متناظرشان در مولفه‌‌ی قویا همبندی قرار دارند که یال خروجی ندارد، شانس میزبانی خواهند داشت.