المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۶

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

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

راهنمایی

گرافی از بازی‌های بازیکنان بسازید. بدین نحو که به ازای هر بازیکن یک راس قرار دهید و اگر بازیکن $i$ در بازی با بازیکن $j$ برده باشد، یالی جهت‌دار از راس متناظر با $i$ به راس متناظر با $j$ رسم کنید. سعی کنید کران بالایی برای تعداد مثلث‌های این گراف بیابید.

راهنمایی

اگر دنباله‌ی درجات خروجی و ورودی رئوس گراف راهنمایی فوق به شما داده شده باشد، می‌توانید تعداد مثلث‌های آن را بشمارید؟

راهنمایی

سعی کنید نشان دهید اگر درجه‌ی خروجی راس $i$ برابر با ${d_i}^+$ و درجه‌ی ورودی راس $i$ برابر با ${d_i}^-$ باشد، آنگاه تعداد مثلث‌های این گراف برابر با $\frac{1}{2} \times (\sum_{i=1}^{15}{{d_i}^+ \times {d_i}^-} - \binom{15}{3} )$ خواهد بود.

راهنمایی

در راستای اثبات راهنمایی پیشین، دقت کنید سیگما، در حال شمارش تعداد مسیر‌های به طول دو است.

راهنمایی

در ادامه‌ی اثبات، بررسی کنید در میان هر سه راسی که تشکیل مثلث بدهند یا ندهند، چند مسیر به طول دو جهت‌دار وجود خواهد داشت.

راهنمایی

حال دقت کنید بیشینه‌ی مقدار عبارت داده شده زمانی رخ می‌دهد که درجه‌ی ورودی و درجه‌ی خروجی یک راس به یکدیگر نزدیک باشند.

راهنمایی

از طرفی تورنومنتی با مشخصات داده شده وجود دارد. راس‌ها را دور دایره بچینید و از هر راس به هفت راس جلوی خود (به طور ساعتگرد) یال جهت‌دار بگذارید.

پاسخ

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

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

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

فرض کنید که تعداد بردهای نفر اول تا پانزدهم به ترتیب $d_1, d_2, ..., 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$$


ابزار صفحه