Про лжецов

[wpoms.]

В каждой единичной ячейке квадрата `2012 times 2012` стоит человек, который может быть либо честным человеком, который всегда говорит правду, или лжецом, который всегда лжёт. Каждый человек делает одно и то же заявление: "В моей шеренге стоит столько же лжецов, сколько их стоит в моей колонне". Определить минимальное количество честных людей, которые могут находиться в этом квадрате.

@темы: Комбинаторика

Comments

[All_ex]

Если поставить на место 1-1 честного, а все остальные места первых строки и столбца заполнить лжецами, то приходим к выводу, что в остальных строчках честных должно быть больше одного...
Теперь рассматриваем поле меньшего размера... и ставим на места 2-2, 2-3, 3-2, 3-3 честного а остальные места второго-третьего столбца и второй-третьей строки заполняем лжецами... Вывод: в остальных строчках честных должно быть не менее трёх...
И так далее...
Итого получаем, что честных можно расставить квадратами разного размера, расположенными по диагонали...
То есть ищем числа `N_1 + ... + N_m = 2012` с наименьшей суммой `N_1^2 + ... + N_m^2`...
Вроде, как получается, что минимум будет для чисел от 1 до 63 без 4... То есть `1^2 + 2^2 + 3^2 + 5^2 + 6^2 +... + 63^2 = {63*64*127}/6 - 16 = 85328`...

Ну, опять же минимальность такого алгоритма для меня не до конца очевидна...