Question

Пожалуйста, Какое наименьшее количество клеток доски 67×67 можно закрасить так, чтобы в каждом квадрате 4×4 было закрашено не меньше половины клеток?

Answer 1

Ответ:

2211 клеток.

Пошаговое объяснение:

Нужно покрасить столбцы или строки через один.

1 столбец - это 67 клеток.

Красим 2, 4, 6,..., 64, 66 столбцы.

Всего (67-1) : 2 = 33 столбца.

Это 67*33 = 2010 + 201 = 2211 клеток.

Если хоть одну клетку не покрасить, то найдется квадрат 4*4, в котором будет покрашено только 7 клеток.

Answer 2

Для решения этой задачи можно воспользоваться методом перебора, чтобы найти наименьшее количество клеток, которые нужно закрасить.

Идея состоит в том, чтобы начать с минимально возможного количества клеток и постепенно увеличивать его, пока не будет выполнено условие задачи.

1. Начнем с самого маленького возможного квадрата, который состоит из 4 клеток (2x2). В таком квадрате нам нужно закрасить хотя бы 2 клетки (половину от 4).

2. Увеличим размер квадрата до 3x3. В таком квадрате нам нужно закрасить хотя бы 5 клеток (половину от 9).

3. Перейдем к размеру 4x4. В таком квадрате нам нужно закрасить хотя бы 8 клеток (половину от 16).

4. Продолжим увеличивать размер квадрата и количество клеток, которые нужно закрасить, будет увеличиваться по следующей последовательности: 2, 5, 8, 12, 17, 23, 30, 38, 47, 57, 68, 80, 93, 107, 122, 138, 155, 173, 192, 212, 233, 255, 278, 302, 327, 353, 380, 408, 437, 467, 498, 530, 563, 597, 632, 668, ...

5. Как видно из последовательности, наименьшее количество клеток доски 67x67, которые нужно закрасить, чтобы в каждом квадрате 4x4 было закрашено не меньше половины клеток, составляет 668.

Таким образом, чтобы выполнить условие задачи, необходимо закрасить 668 клеток на доске размером 67x67.