المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۰

حداکثر چندتا از نقطه‌های توپر در شکل مقابل را می‌توان با سفید رنگ کرد تا نقطه‌های سفید رئوس٬ یک مثلث متساوی‌الاضلاع را تشکیل ندهند.

  1. ۴
  2. ۵
  3. ۶
  4. ۷
  5. ۸

پاسخ

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

توجه داشته باشید که مثلث متساوی‌الاضلاع می‌تواند به هر طول ضلعی و هر زاویه‌ای تشکیل شود و لزومی ندارد که موازی خطوط باشد.

می‌دانیم از هر مثلث به طول یک در گوشه‌های مثلث بزرگ، یک نقطه نباید انتخاب شود. در نتیجه جواب حداکثر ۷ خواهد بود.

ثابت می‌کنیم جواب برابر ۷ نیز نمی‌تواند باشد: فرض کنید ۷ نقطه انتخاب کرده‌ایم. طبق فرض بالا نقطه‌ی وسط مثلث انتخاب شده است. حال ۶ نقطه‌ی اطراف آن را در نظر بگیرید. اگر ۴ نقطه در بین آن‌ها انتخاب شده باشد دو نقطه یافت می‌شود که مجاور باشند و با نقطه‌ی وسط تشکیل مثلث متساوی‌الاضلاع می‌دهند. پس حداکثر ۳ نقطه از بین آن‌ها انتخاب شده است. حال از ۳ نقطه‌ی گوشه نیز باید حداکثر دو نقطه انتخاب شود. در نتیجه حداکثر ۶ نقطه انتخاب شد.

برای ۶ نقطه نیز مثال زیر وجود دارد:


ابزار صفحه