المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۳:سوال ۱۶

سوال ۱۶

در یک تورنمنت ۱۵ پینگ پنگ باز حضور دارند و هر دو نفر دقیقا یکبار با هم بازی می کنند. به یک ۳ تایی از این بازیکنان، «ضایع» می گوییم هرگاه اولی، دومی را برده باشد، دومی، سومی را برده باشد و سومی اولی را برده باشد. حداکثر چند ۳ تایی ضایع در این مسابقات وجود دارد؟

  1. ۱۴۰
  2. ۳۱۵
  3. ۴۵۵
  4. ۲۸۰
  5. ۴۲۰

پاسخ

گزینه‌ی ۱ درست است.

در صورتی که یک سه‌تایی ضایع نباشد دقیقا یکی از آن‌ها دو نفر دیگر را برده است (برنده) و دقیقا یکی از آن‌ها از دو نفر دیگر باخته است (چرا؟). به جای شمارش سه‌تایی‌های ضایع، متمم آن‌ها را می‌شماریم.

هر سه‌تایی غیرضایع با دو برد برنده‌اش مشخص می‌شود. پس کافیست که تعداد جفت پیروزی‌های ممکن در مسابقات را بیابیم.

فرض کنید که تعداد بردهای نفر اول تا پانزدهم به ترتیب d_1,…,d_15 باشد. می‌دانیم مجموع این اعداد برابر تعداد مسابقات است (چون هر مسابقه دقیقا یک برنده دارد). در نتیجه تعداد زوج‌ پیروزی‌ها برابر خواهد بود با:

$$\binom{d_1}{2}\times\binom{d_2}{2}\times⋯\times\binom{d_15}{2}$$

که می‌خواهیم این عدد را کمینه کنیم. تنها عدد غیرمعلوم در عبارت بالا مجموع مربعات این اعداد است که طبق نامساوی حسابی-مربعی مینیمم آن زمانی اتفاق می‌افتد که همگی آن‌ها با یک‌دیگر برابر باشند (هرکس ۷ برد و ۷ باخت داشته باشد).

از طرفی یک مثال نیز برای چنین اعدادی وجود دارد. در صورتی که ۱۵ نفر را به ترتیب دور دایره قرار دهیم، هرکسی از ۷ نفر جلوی خود ببرد و از ۷ نفر قبل از خود ببازد این کار میسر می‌شود. به ازای این حالت تعداد سه‌تایی‌های ضایع برابر می‌شود با:

$$\binom{15}{3}-15\times\binom{7}{2}=455-315=140$$


ابزار صفحه