Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳۵

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

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

پاسخ

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

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

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

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


ابزار صفحه