المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی اول:دوره‌ی ۹:سوال ۶

سوال ۶

در یک مسابقه‌ي پینگ پنگ بین دو دبیرستان $A$ و $B$ ، هر دانش‌آموز دبیرستان $A$ با هر دانش‌آموز دبیرستان $B$ یک مسابقه برگزار می‌کند.(مسابقه‌ی پینگ پنگ تساوی ندارد.) یک دانش‌آموز «برنده‌ی مطلق» محسوب می‌شود اگر او هر دانش‌آموز $X$ از هر دو دبیرستان را یا مستقیما ببرد٬ یا از دانش‌آموز دیگری مانند $Y$ ببرد و $Y$ از $X$ برده باشد.

کدام یک از گزینه‌های زیر صحیح است؟

  1. ممکن است برنده مطلق وجود نداشته باشد.
  2. برنده‌ی مطلق تمام بازی‌هایش را برده است.
  3. اگر برنده‌ي مطلق وجود داشته باشد حداکثر یک نفر است.
  4. به هیچ وجه برنده‌ي مطلق وجود ندارد.
  5. ۱ و ۲ و ۳

پاسخ

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

برای صحت گزینه‌ی ۱ شکل مقابل وجود دارد :

اگر بازیکن $i$ از $A$ از بازیکن $j$ از $B$ باخته باشد آن‌گاه $i$ نمی‌تواند برنده‌ی مطلق شود زیرا بازیکن‌هایی که $j$ را برده‌اند از دبیرستان $A$ بوده و با $i$ بازی نکرده‌اند. پس بازیکنی که حتی یک باخت داشته باشد نمی‌تواند برنده مطلق باشد. اگر بازیکن‌های $i$ و $j$ هر دو برنده‌ی مطلق باشند آن‌گاه $i$ و $j$ نمی‌توانند در دو دبیرستان متفاوت باشند زیرا اگر $i$ از $j$ برده باشد آن‌گاه $j$ حداقل یک باخت داشته و نمی‌تواند برنده‌ی مطلق باشد. و اما اگر $i$ و $j$ از یک دبیرستان باشند و هر دو تای آن‌ها همه‌ی دانش‌آموزان دبیرستان دیگر را برده باشند آن‌گاه بازیکن $i$ بازیکن $j$ را به واسطه نبرده است و نمی‌تواند برنده‌ی مطلق محسوب شود.


ابزار صفحه