Из доски 100-100 вырезаны 4 угловых клетки. Какое наименьшее количество клеток надо ещё вырезать, чтобы из оставшейся части нельзя было бы вырезать квадрат 2:2?

Размер доски 100x100. Из доски уже вырезаны 4 угловые клетки.

Чтобы нельзя было вырезать квадрат 2x2, нужно сделать так, чтобы в любом квадрате 2x2 была вырезана хотя бы одна клетка. Представим себе шахматную раскраску доски. Если мы вырежем все клетки одного цвета, то квадратов 2x2 не останется. На доске 100х100 всего 10000 клеток, ровно половина из них будет одного цвета (5000), а вторая половина – другого (тоже 5000).

Однако, мы уже вырезали 4 угловые клетки. Предположим, что эти 4 клетки были одного цвета, значит, осталось вырезать 5000-4 = 4996 клеток этого цвета, чтобы не осталось ни одного квадрата 2x2.

Но можно ли сделать лучше? Представим себе, что мы вырезаем не все клетки одного цвета, а вырезаем полосками. Т.е. вырезаем первую полоску через одну клетку, потом следующую полоску, и т.д. Тогда, если мы вырежем каждую вторую линию, то мы тоже не сможем вырезать квадрат 2х2. Сколько клеток нам придется вырезать в этом случае? У нас 100 линий, и в каждой линии надо вырезать каждую вторую клетку. Т.е. в каждой линии надо вырезать 100 / 2 = 50 клеток. А всего линий 100, значит всего надо вырезать 50 × 100 = 5000 клеток.

Вспомним, что у нас уже вырезано 4 угловых клетки. Эти угловые клетки могли попасть в нашу схему вырезания полосками или не попасть. В худшем случае они не попали в нашу схему, тогда нам нужно будет вырезать 5000 клеток. В лучшем случае они попали в нашу схему, тогда нам нужно будет вырезать 5000 - 4 = 4996 клеток.

Теперь попробуем другой подход. Нам нужно, чтобы в каждом квадрате 2x2 была вырезана хотя бы одна клетка. Представим, что мы вырезаем каждую клетку через одну по диагонали. Это тоже не даст нам вырезать квадрат 2x2. Но сколько нам придется вырезать клеток в этом случае? Если мы вырежем диагональ, в которой 100 клеток, потом вторую диагональ, в которой 99 клеток, потом третью, и так далее, то это будет очень много.

Таким образом, наиболее оптимальным является вырезание клеток одного цвета. В этом случае необходимо вырезать 5000 клеток. Учитывая, что 4 клетки уже вырезаны, нам необходимо вырезать еще 4996 клеток.

Ответ: 4996