المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۹

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

  1. ۲
  2. ۳
  3. ۵
  4. ۷
  5. ۹

پاسخ

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

واضح است که هر عدد در حداکثر ۳ کارت قابل درج است، زیرا اگر عددی مانند $x$ در چهار کارت درج شود، تمام هشت عدد دیگر در این چهار کارت باید متمایز باشند که به دلیل وجود تنها ۷ عدد متمایز امکان پذیر نیست. در نتیجه تعداد کل کارت‌های قابل ساخت حداکثر $\frac{3 \times 7}{۳} = 7$ است. این ۷ کارت را می‌توان به شکل زیر ساخت: $$ (1, 2, 3), (1, 4, 5), (1, 6, 7), (2, 4, 6), (2, 5, 7), (3, 4, 7), (3, 5, 6) $$


ابزار صفحه