سؤال ۱۲
در بازی « سیب‌زمینی داغ »، ۵ بازیگر هستند با یک سیب‌زمینی داغ. زیرِ پای هر بازیگر یک شماره است. هر بازیگر مجبور است سیب‌زمینی داغ را یک ثانیه نگه دارد و سپس آن را به بازیگری که شماره‌اش زیر پای اوست بدهد. در این بازی شما با شماره‌ی ۱ شرکت کرده‌اید و در ابتدا سیب‌زمینی نزد شماست. برای چند تا از حالت‌های زیر ممکن است شماره‌ی زیر پای شما طوری باشد که دیگر سیب‌زمینی به دست شما برنگردد؟
• ۳ زیر پای ۲، ۴ زیر پای ۳، ۱ زیر پای ۴ و ۱ زیر پای ۵
• ۳ زیر پای ۲، ۴ زیر پای ۳، ۱ زیر پای ۴ و ۴ زیر پای ۵
• ۳ زیر پای ۲، ۱ زیر پای ۳، ۵ زیر پای ۴ و ۴ زیر پای ۵
• ۳ زیر پای ۲، ۲ زیر پای ۳، ۲ زیر پای ۴ و ۳ زیر پای ۵
- ۰
- ۱
- ۲
- ۳
- ۴
پاسخ
گزینه (؟) درست است.
گراف‌ّهای جهت‌دار متناظر به هر یک از حالات داده شده به ترتیب از چپ به راست به شکل زیر می‌باشد:
با توجه به گراف‌های فوق معلوم می‌شود که عدد زیر پای ۱ هرچه باشد در حالت اول٬ دوم و چهارم سیب‌زمینی به شماره ۱ برخواهد گشت ولی در حالت سوم این چنین نیست. در حالت سوم اگر عدد زیر پای ۱ یکی از دو عدد ۴ و یا ۵ باشد٬ آن‌گاه سیب‌زمینی بین آن دو نفر خواهد چرخید و هرگز به خود ۱ برنمی‌گردد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
