Задача к ЕГЭ на тему «Оценка + пример» №2

Просмотров 7 Комментарии 0

Какое наименьшее число клеточек на доске $8 × 8$ можно закрасить в черный цвет так, чтобы была хотя бы одна закрашенная клетка

а) в любом квадратике $2 × 2$

б) в любом уголке из трёх клеточек?

а) Разобьем шахматную доску на $16$ клеток $2 × 2$ как показано на рисунке

$PIC$

Так как всего квадратов $2 × 2$ 16 штук, то минимальное количество закрашенных клеток 16 (так как если мы закрасим всего 15 клеток, то в каком то из 16 квадратов $2 × 2$ не будет закрашенной клетки).

Это была оценка, то есть доказательство того, что меньше 16 клеток закрасить мы не сможем.

Пример того, как это можно сделать ниже:

$PIC$

б) Воспользуемся разбиением шахматной доски из пункта а).

Заметим, что если в каком-то из 16 квадратов будет закрашена только 1 клетка, то в этом квадрате $2 × 2$ обязательно будет уголок из трех клеточек, в котором не будет закрашенной клетки. Поэтому в каждом из 16 квадратов $2 × 2$ должно быть как минимум 2 закрашенные клетки, то есть всего 32 закрашенные клетки.

Это была оценка, то есть доказательство того, что меньше чем 32 клетки закрасить нам не удастся.

Пример для 32 на рисунке ниже:

$PIC$