В клетки таблицы n × n (n > 3) вписаны числа 0 и 1 так, что в клетках каждого квадрата 2 × 2 стоит ровно три одинаковых числа. Какое максимальное значение может принимать сумма всех чисел в этой таблице?
Очевидно, что если k — минимально возможное число нулей в таблице, то искомая сумма достигает максимума, равного числу
В любой таблице можно выделить непересекающихся квадратов, где через обозначена целая часть числа если n четно; если n нечетно). В каждом таком квадрате содержится либо три нуля, либо один нуль, то есть не менее одного нуля. Тогда во всей таблице n × n найдется не менее нулей, а значит искомое число Приведем пример таблицы с минимальным числом нулей, равным
1 | 1 | 1 | 1 | ... |
1 | 0 | 1 | 0 | |
1 | 1 | 1 | 1 | |
1 | 0 | 1 | 0 | |
... |
В приведенной таблице нули находятся лишь на пересечении строки и столбца с четными номерами.
Таким образом, максимальное значение суммы всех чисел в таблице равно
Ответ: