Комбинаторика на ИТМО: способы, графы, логика, клетки, комбигео

Число в белой клетке состоит из двух слагаемых: "горизонтального"и "вертикального". Рассмотрим отдельно сумму всех "горизонтальных"и отдельно сумму всех "вертикальных"слагаемых по всей таблице. Если мы максимизируем каждую из этих двух сумм по отдельности, общая сумма также будет наибольшей.

Рассмотрим сумму "горизонтальных"слагаемых. Если в строке находится чёрных клеток и белых, то сумма горизонтальных слагаемых в этой строке составляет . Просуммировав эту сумму по всем строкам, мы получаем

Нам нужно максимизировать это выражение, т.е. минимизировать сумму квадратов восьми чисел, сумма которых составляет 23. Как известно, сумма квадратов чисел уменьшается при сближении этих чисел к их среднему арифметическом, поэтому для целых чисел минимум достигается, когда семь из восьми чисел равны 3, а оставшееся равно 2.

Таким образом, мы получаем, что наименьшая возможная сумма "горизонтальных"слагаемых равна

Аналогичную оценку можно получить для суммы "вертикальных"слагаемых, что даёт нам итоговое значение 234.

Осталось убедиться, что существует раскраска таблицы, при которой обе суммы максимальны одновременно, то есть в которой в каждом столбце или строке по 2 или 3 закрашенных клетки.