المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۴

شکل مقابل را در نظر بگیرید. می‌خواهیم تعدادی نقطه‌ی اولیه در قسمت سفید شکل انتخاب کنیم٬ به قسمی که بتوان هر نقطه‌ای در قسمت سفید را با یک خط مستقیم به حداقل یکی از نقاط اولیه وصل کرد. این خط نباید از قسمت‌های سیاه شکل عبور کند.

حداقل تعداد نقاط اولیه چندتاست؟

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

پاسخ

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

اگر سه نقطه مطابق شکل (۱) در نظر بگیریم معلوم می‌شود که هیچ دوتایی از آن‌ها نقطه‌ي اولیه‌ی مشترک ندارند بنابراین وجود حداقل سه نقطه‌ی اولیه الزامی است. اگر سه نقطه‌ي اولیه مطابق شکل (۲) باشند آن‌گاه تمام نقاط سفید رنگ پوشش داده می‌شوند.


ابزار صفحه