سوال ۲۰
۱۶ تیم در مسابقات جام حذفی و لیگ شرکت کرده‌اند. می‌دانیم که اگر تیم «الف» از تیم «ب» قوی‌تر باشد هربار که تیم «الف» با تیم «ب» بازی کند برنده خواهد شد. هم‌چنین می‌دانیم که اگر تیم «الف» از تیم «ب» قوی‌تر باشد و تیم «ب» از تیم «ج» قوی‌تر باشد در این صورت تیم «الف» نیز حتما از تیم «ج» قوی‌تر خواهد بود. مسابقات جام حذفی و لیگ به صورت زیر برگزار می‌شوند:
- مسابقات جام حذفی: در این مسابقات در مرحله‌ی اول ۸ مسابقه انجام می‌شود و هر تیم در یک بازی شرکت می‌کند. تیم‌های بازنده از مسابقات حذف می‌شوند و ۸ تیم پیروز به مرحله‌ی بعد راه پیدا می‌کنند. در مرحله‌ی دوم٬ ۴ بازی انجام می‌شود و تیم‌های پیروز به مرحله‌ي بعد می‌روند. در مرحله‌ی سوم که مرحله‌ی نیمه نهایی است ۲ بازی انجام می‌شود و تیم‌های پیروز به فینال راه پیدا می‌کنند. تیم برنده‌ي فینال قهرمان جام حذفی و تیم بازنده‌ی فینال نایب قهرمان است.
- مسابقات لیگ: در این مسابقات هر دو تیم دقیقاً یک بار با هم بازی می‌کنند و به تیم برنده‌ی هر بازی ۳ امتیاز و به تیم بازنده ۰ امتیاز داده می‌شود. در انتها تیم‌ها را با توجه به امتیاز آن‌ها مرتب کرده و رتبه‌ی هر تیم معلوم می‌شود.
دقت کنید که نتیجه‌ی مساوی در این مسابقات نداریم. پایین‌ترین (بدترین) رتبه‌ای که تیم نایب قهرمان مسابقات جام حذفی در مسابقات لیگ می‌تواند داشته باشد چه رتبه‌ای است؟
- دوم
- سوم
- پنجم
- نهم
- سیزدهم
پاسخ
گزینه‌ی (۴) درست است.
باتوجه به شرایطی که مسئله توضیح داده است می‌توان تیم‌ها را به ترتیب قدرت مرتب کرد بطوری که هر تیمی رتبه‌اش بهتر باشد از تمامی تیم‌های با رتبه‌ی بالاترش قوی‌تر باشد و در بازی با آن برنده شود.
تیم نائبقهرمان از تمامی ۸ تیمی که از آن‌ها (مستقیما یا با واسطه‌ی تیم دیگری) برده قوی‌تر است. پس رتبه‌ی این تیم حداکثر نهم است. از طرفی اگر تیم‌های نهم تا شانزدهم را بصورتی بچینیم که تا فینال با هم مسابقه دهند، مثالی را ارائه کرده‌ایم که تیم نائبقهرمان نهم بوده است. پس جواب مسئله نهم است.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
