المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۲

شکل زیر یک پنج‌ضلعی منتظم به همراه یک نقطه در مرکز آن است:

می‌خواهیم بین برخی از شش نقطه‌ی شکل، پاره‌خط‌هایی بکشیم، طوری که شرایط زیر برقرار باشد:

  • هیچ دو پاره‌خطی هم‌دیگر را قطع نکنند (مگر در خود نقاط شکل).
  • سطح داخل شکل به تعدادی مثلث افراز شود، طوری که هر کدام از نقاط شکل، رأس حداقل یکی از مثلث‌ها باشند.

شکل نهایی چند حالت دارد؟

  1. ۱
  2. ۱۰
  3. ۱۲
  4. ۱۱
  5. ۵

پاسخ

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

به قطری از پنج‌ضلعی که دو رأس نامجاور را به هم وصل کند، \textbf{قطرک} می‌گوییم. با حالت‌بندی بر روی تعداد قطرک‌ها داریم:

  • اگر قطرک نداشته باشیم، تمام رأس‌ها باید به رأس وسط وصل شوند که یک حالت دارد.
  • اگر یک قطرک داشته باشیم، رأس وسط درون یک چهارضلعی قرار می‌گیرد و باید به تمام چهار رأس آن وصل شود. انتخاب قطرک گفته شده پنج حالت دارد.
  • اگر دو قطرک داشته باشیم، باید این دو قطرک در یک رأس مشترک باشند که پنج حالت برای انتخاب‌شان وجود دارد. در ادامه رأس وسط درون یک مثلث قرار می‌گیرد و باید به سه رأس آن وصل شود.

پس در کل $5+5+1=11$ حالت داریم.


ابزار صفحه