Троичная доска

[Ktina]

(по мотивам задачи М. В. Масловой)

Есть доска $9\times 9$ клеток. В каждую клетку поставили число 0, 1 или 2 так, чтобы в каждом квадратике $2\times 2$ сумма была больше четырёх. Найдите наименьшее возможное значение суммы всех чисел на доске.

[Masik]

У меня получилось $9\cdot9 + 4\cdot9 - 5\cdot5 = 92$

[atlakatl]

Сумма 88.
PS. Извините, двойку с тройкой перепутал.

Вот как надо. И сумма действительно 92.

[covax]

atlakatl в сообщении #1159684 писал(а):

Сумма 88.

У вас тройки откуда-то.

$\begin{array}{ccccccccc}0&1&0&1&0&1&0&1&0 \\ 2&2&2&2&2&2&2&2&2\\ 0&1&0&1&0&1&0&1&0\\ 2&2&2&2&2&2&2&2&2\\ 0&1&0&1&0&1&0&1&0\\ 2&2&2&2&2&2&2&2&2\\ 0&2&0&1&0&1&0&2&0\\ 2&2&2&2&2&2&2&2&2\\ 0&1&0&1&0&1&0&1&0\end{array}$

$4\cdot9\cdot2+4\cdot5=92$

[Ktina]

Сумма, равная 92, является наименьшей из возможных или наименьшей из найденных?

[atlakatl]

Ktina
Сумма чисел любого квадрата 2х2 равна пяти. Меньше она быть не может, а больше - общая сумма будет больше 92-х.

[Ktina]

atlakatl
А если равна 5, почему не может быть, скажем, 89?

[DeBill]

Оценка.
Вырежем из нашего квадрата "центральный" квадрат $5\times5$. Оценим сумму чисел в оставшейся "рамке " . Для этого рассмотрим все квадратики два на два, лежащие в рамке. Их 28 штук, и сумма чисел в этих квадратиках не менее $28\cdot5 = 140$. При этом угловые клетки ($U$) покрываются одиножды, соседние с ними по диагонали $VU$ ("внутренние угловые") - трижды, а прочие - дважды. Поэтому для суммы $R$ всех чисел из рамки имеем $2R\geqslant 140 +U - VU\geqslant 140 +0 - 4\cdot2 = 132$, так что $R\geqslant 66$.
Выбросим из центрального квадрата $5\times5$ центральную клетку, и аналогично оценим сумму $R'$ чисел в оставшейся "рамочке":
$2R' \geqslant 5\cdot 12 +U' -VU' \geqslant 60 +0 - 4\cdot 2 = 52$, так что $R' \geqslant 26$. Итого уже получилось для двух рамок сумма не мене $66+26 = 92$.
(Для приведенного covax и atlakatl примера все неравенства - включая неотрицательность центральной клетки - будут равенствами.)

[covax]

Перебором для 5*5
[(26,[0,2,0,2,0,1,2,1,2,1,0,2,0,2,0,1,2,1,2,1,0,2,0,2,0]),(26,[0,1,0,1,0,2,2,2,2,2,0,1,0,1,0,2,2,2,2,2,0,1,0,1,0])]
т.е. получается такое
$\begin{array}{ccccc}0&1&0&1&0\\ 2&2&2&2&2\\ 0&1&0&1&0\\ 2&2&2&2&2\\ 0&1&0&1&0\\ \end{array}$