المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۹:تئوری:سوال ۳

سوال ۳

یک جدول ‎$n \times n$‎ داریم که هر کدام از ‎$n^2$‎ خانه‌اش با یکی از دو رنگ سیاه یا سفید رنگ شده است. می‌دانیم تعداد خانه‌های سفید این جدول حداکثر ‎$cn$‎ است. یک بلوک یک زیرمستطیلِ این جدول است همه‌ی خانه‌هایش سیاه است. ثابت کنید با حداکثر ‎$(c+1)n$‎ بلوک می‌توان تمام خانه‌های سیاه این جدول را پوشاند. همچنین ثابت کنید که این جدول می‌تواند طوری باشد که نتوان با کمتر از ‎$cn$‎ بلوک تمام خانه‌های سیاه جدول را پوشاند.


ابزار صفحه