المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۳

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

حداقل چند وزیر لازم است تا بتوان آن‌ها را طوری در صفحه چید که همه‌ی خانه‌ها را تهدید کنند؟

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

پاسخ

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

هر وزیر حداکثر دو خانه از خانه‌های غیر ستون خود را تهدید می‌کند٬ چون در هر ستون پنج خانه وجود دارد٬ پس در صورت موجود بودن وزیر در ستون‌های $i$ و $j$ خانه‌ای از ستون $k$ تهدید نشده باقی می‌ماند٬ بنابراین وجود حداقل ۳ وزیر الزامی است. با سه وزیر مطابق شکل زیر می‌توان تمام خانه‌ها را تهدید کرد:


ابزار صفحه