المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۲۰:سوال ۴

سوال4

در یک شبکه‌ی $۳ \times ۳$ نقطه‌ای، بین هر دونقطه‌ی مجاور می‌توان یک پاره‌خط به طول ۱ رسم کرد (حداکثر ۱۲ پاره‌خط). یک زیرمجموعه از ۱۲ پاره‌خط را «اشباع شده» می‌نامیم اگر:

  1. با رسم پاره‌خط‌های این زیرمجموعه هیچ مربع واحدی ($۱ \times ۱$) ایجاد نشود، و همچنین
  2. اگر هر پاره‌خطی که در این زیرمجموعه نیست را اضافه کنیم، حداقل یک مربع $۱ \times ۱$ به وجود آید.

تعداد زیرمجموعه‌های مختلف اشباع شده چند تا است؟ یکی از آن‌ها در شکل دیده می‌شود.

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

پاسخ

گزینه $(4)$ صحیح است


ابزار صفحه