You are not allowed to perform this action

سوال ۳

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