Question

В клетках таблицы 17×17 расставлены натуральные числа, не превосходящие 4, таким образом, что в каждом квадрате 2×2 сумма чисел равна 7. Какое наибольшее значение может принимать сумма чисел во всей таблице?

Answer 1

Оценка:

Разобьём наш квадрат 17 на 17 на квадрат 16 на 16, два прямоугольника 1 на 16 и одну клетку. Затем квадрат 16 на 16 разобьём на 64 квадрата 2 на 2, а каждый прямоугольник разобьём на 8 прямоугольников 1 на 2.  В каждом квадрате 2 на 2 сумма цифр равна 7, в каждом прямоугольнике 1 на 2 сумма цифр не больше 5 (из-за достроения его до квадрата), а в оставшейся клетке цифра не более 4, потому сумма всех чисел не больше 64 * 7 + 8 * 2 * 5 + 4 = 532.

Пример:

Пронумеруем все строки и столбцы по порядку от 1 до 17. Выберем все клетки которые находятся в столбце и в строке с нечётными номерами и поставим в них "4", а в остальные клетки поставим "1". Условие (сумма цифр в каждом квадрате равна 7) выполнено, а сумма всех чисел в таблице равна 81 * 4 + 289 - 81 = 532.

Ответ: 532.

Answer 2

Рассмотрим произвольный квадрат 2×2 в таблице. Пусть числа в этом квадрате равны a, b, c и d (см. рисунок ниже).

cssCopy code
a b
c d

Так как сумма чисел в каждом квадрате 2×2 равна 7, то a+b+c+d=14.

Рассмотрим теперь произвольный столбец или строку таблицы длиной 17. Пусть числа в этой строке (или столбце) равны x₁, x₂, ..., x₁₇. Разобьем эту строку (или столбец) на 8 непересекающихся квадратов 2×2 (см. рисунок ниже).

markdownCopy code
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17
     q1     q2     q3     q4     q5     q6     q7     q8

Тогда сумма чисел в этой строке (или столбце) равна 7·8=56.

Теперь рассмотрим всю таблицу. Разобьем ее на 8 строк (или столбцов) длиной 17. Тогда сумма чисел в таблице равна 56·8=448.

Мы доказали, что сумма чисел в таблице не может превосходить 448. Это значение достигается, если в каждом квадрате 2×2 стоят числа 1, 2, 2 и 2 (в любом порядке), а таблица выглядит следующим образом:

Copy code
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
2 1