s05.5
05.5. Какое наименьшее число клеток квадрата 10 х 10 необходимо отметить, чтобы в любом a) прямоугольнике 1 x 4, b) квадрате 3 x 3 - была отмечена хотя бы одна клетка?
Пример a). Ответ 24
Оценка. Рассмотрим разбиение квадрата 10 х 10 на 24 полосы 1х4. Получится 24 полоски. Это заготовки . Ответ 24.
Оценка. Предположим 23 отметки хватит. Тогда 23 отметки из моих 24 прямоугольников отметит не более 23. Тогда останется хотя бы 1 заготовка. В этой заготовке вполне может стоять неотмеченный прямоугольник. То есть 23 отметки не хватит.
Пример b). Давайте возьмём квадрат 10 х 10. Вырежем из него одну строчку и один столбец. А все остальное разрежем на квадраты 3 x 3. Получится 9 квадратов 3 x 3. В каждом из этих квадратов необходимо отметить клетку. Если не отметишь, то значит не в любом квадрате 3 x 3 есть отметка. Значит, я доказал, что ответ хотя бы 9.
Оценка. Давайте покрасим доску в 9 цветов вот таким образом. И так далее. То есть циклично. Тогда я утверждаю, что в любом квадрате 3 x 3 есть все цвета. Потому что вы берёте квадратик 3 x 3 какой угодно. Если вы на одну строчку его подвинете, без вот этих 3 клеток, то они будут такие же.
