المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۸:سوال ۳۵

سوال ۳۵

در شکل روبه‌رو٬ ۵ عدد میخ مشاهده می‌کنید که با تعدادی کش به هم متصل شده‌اند. به چند طریق می‌توان ۵ تا از کش‌ها را انتخاب کرد٬ به طوری که هر میخ٬ دقیقا به دو کش انتخاب شده وصل باشد؟

  1. ۱۲
  2. ۶
  3. ۲۴
  4. ۸
  5. ۱۸

پاسخ

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

ابتدا کش $a$ که رسم نشده‌است را اضافه می‌کنیم و در نهایت تعداد حالت‌هایی که شامل کش $a$ هستند را از جواب کم می‌کنیم (متمم گیری). هر میخ باید به ۲ کش متصل باشد. برای انتخاب یکی از کش‌های میخ ۱، ۴ حالت داریم. فرض کنیم سر دیگر کش، میخ $i$ باشد. از بین کش‌هایی که به $i$ وصل‌اند یکی انتخاب شده پس ۳ انتخاب وجود دارد و برای میخ‌های دیگر به همین ترتیب ۲ و ۱ انتخاب داریم. ترتیب انتخاب کش‌ها اهمیتی ندارد پس کل حالت‌ها را تقسیم بر ۲ می‌کنیم. بنابراین $\frac{4×3×2×1}{2}=12$ حالت برای انتخاب کش‌ها وجود دارد.

کش $a$ در $۳×۲=۶$ تا از حالت‌ها انتخاب شده‌است. (۳ انتخاب برای کش متصل به میخ ۳ و ۲ انتخاب برای کش متصل به ۴)

بنابراین به $۱۲-۶=۶$ راه می‌توان کش انتخاب کرد.


ابزار صفحه