سوال ۲۰

۱۶ تیم در مسابقات جام حذفی و لیگ شرکت کرده‌اند. می‌دانیم که اگر تیم «الف» از تیم «ب» قوی‌تر باشد هربار که تیم «الف» با تیم «ب» بازی کند برنده خواهد شد. هم‌چنین می‌دانیم که اگر تیم «الف» از تیم «ب» قوی‌تر باشد و تیم «ب» از تیم «ج» قوی‌تر باشد در این صورت تیم «الف» نیز حتما از تیم «ج» قوی‌تر خواهد بود. مسابقات جام حذفی و لیگ به صورت زیر برگزار می‌شوند:

دقت کنید که نتیجه‌ی مساوی در این مسابقات نداریم. پایین‌ترین (بدترین) رتبه‌ای که تیم نایب قهرمان مسابقات جام حذفی در مسابقات لیگ می‌تواند داشته باشد چه رتبه‌ای است؟

  1. دوم
  2. سوم
  3. پنجم
  4. نهم
  5. سیزدهم

پاسخ

گزینه‌ی (۴) درست است.

باتوجه به شرایطی که مسئله توضیح داده است می‌توان تیم‌ها را به ترتیب قدرت مرتب کرد بطوری که هر تیمی رتبه‌اش بهتر باشد از تمامی تیم‌های با رتبه‌ی بالاترش قوی‌تر باشد و در بازی با آن برنده شود.

تیم نائب‌‌قهرمان از تمامی ۸ تیمی که از آن‌ها (مستقیما یا با واسطه‌ی تیم دیگری) برده قوی‌تر است. پس رتبه‌ی این تیم حداکثر نهم است. از طرفی اگر تیم‌های نهم تا شانزدهم را بصورتی بچینیم که تا فینال با هم مسابقه دهند، مثالی را ارائه کرده‌ایم که تیم نائب‌قهرمان نهم بوده است. پس جواب مسئله نهم است.