Наименьшее число разнообразий из зерен на доске 4 на 4

В каждую клетку доски 4×4 Аня положила по нескольку зерен и передала доску Боре (см. рис.). Трансверсалью доски называется набор из 4 клеток, любые две из которых расположены в разных строках и разных столбцах (см. примеры). Боря за один ход может снять одинаковое количество зерен с каждой клетки какой-либо одной трансверсали. За какое минимальное число ходов Боря может снять все зерна с доски?

• Решение

Решение

За один ход Боря может освободить не более 4 клеток. Следовательно, ему придется сделать минимум 4 хода (так как изначально среди 16 клеток нет ни одной пустой). Заметим, что есть клетка с 8 зернами, а в остальных клетках зерен меньше. Значит с этой клетки зерна придется снимать минимум дважды. Поэтому за 4 хода Боря не справится. Покажем как снять зерна за 5 ходов (серым отмечены трансверсали, с которых сняли зерна):


1 7 2 0 4 0 4 2 2 1 0 7 3 2 4 1

1 7 0 0 4 0 4 0 0 1 0 7 3 0 4 1

1 3 0 0 0 0 4 0 0 1 0 3 3 0 0 1

0 3 0 0 0 0 3 0 0 0 0 3 3 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0



• Ответ

Ответ

За 5 ходов.