المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۲

یک جدول $۱۰ \times ۴$ خالی مانند شکل سمت چپ داریم. به ۴ خانه‌ی سیاه که ۴ گوشه‌ی یک مستطیل قرار بگیرند٬ «چهارخونه» می‌گوییم (مانند شکل سمت راست). حداکثر چند خانه از جدول خالی سمت چپ را می‌توانیم سیاه کنیم به طوری که٬ در آن هیچ «چهارخونه»ای مشاهده نشود؟

  1. ۱۰
  2. ۱۳
  3. ۱۶
  4. ۱۸
  5. ۲۰

پاسخ

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

تعداد روش‌های جفت‌کردن خانه‌های یک سطر و ساختن جفت ستون$\binom{4}{2}=6$ است. اگر جفت ستون‌های دو سطر برابر باشند، یک چهارخونه تولید می‌شود. هر سطر حداقل یک خانه‌ی مشکی دارد(10 خانه). هر خانه‌ی مشکی که به یک سطر اضافه کنیم، حداقل یک جفت ستون می‌سازد. پس حداکثر می‌توانیم 6 خانه‌ی مشکی دیگر به جدول اضافه کنیم تا هیچ جفت تکراری و در نتیجه هیچ چهارخونه‌ای ساخته نشود(اگر در سطری 3 خانه سیاه شود، 3 جفت ستون ساخته می‌شود و تعداد خانه‌های سیاه را کم می‌کند.). یعنی حداکثر 16 خانه‌ی جدول سیاه می‌شود.


ابزار صفحه