المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۹

$k$ عدد رخ را در یک صفحه‌ی شطرنجی $10×10$ طوری قرار داده‌ایم که تمام صفحه را تهدید کنند. یک رخ در خانه‌ی$(x,y)$، همه‌ی خانه‌های سطر $x$ و ستون $y$ را تهدید می‌کند. هم‌چنین می‌خواهیم که هر رخ دقیقاً توسط ۴ رخ دیگر تهدید شود. حداقل $k$ چند است؟

  1. ۹
  2. ۱۰
  3. ۱۳
  4. ۱۶
  5. ۲۴

پاسخ

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

معلوم است که اگر تعداد رخ‌ها کم‌تر از ۱۰ باشد همه خانه‌ها تهدید نخواهند شد زیرا در این صورت خانه‌ای وجود خواهد داشت که نه در سطرش مهره باشد و نه در ستونش. با ۱۰ رخ مطابق شکل زیر می‌توان به جواب رسید.


ابزار صفحه