المپدیا

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

ابزار کاربر

ابزار سایت


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

مستطیل‌های سیاه

خانه‌های یک جدول $m×n$ را با دو رنگ سفید و سیاه به‌ طور دل‌خواه رنگ کرده‌ایم. یک زیرمجموعه‌ی مستطیل شکل به ابعاد $a$ و $b$ ($1≤a≤m$ و نیز $1≤b≤n$) از خانه‌های جدول را یک زیر مستطیل سیاه می‌نامیم اگر تمامی $a×b$ خانه‌ی داخل آن، سیاه باشند. یک زیر مستطیل سیاه را «غیرقابل گسترش» می‌نامیم، هرگاه هیچ زیر مستطیل سیاه دیگری شامل تمامی خانه‌های آن نباشد. ثابت کنید تعداد زیر مستطیل‌های سیاهِ غیرقابل گسترش بیش‌تر از $mn$ نیست.


ابزار صفحه