Архив задач олимпиады по математике и криптографии
Наименьшее число разнообразий из зерен на доске 4 на 4
В каждую клетку доски 4×4 Аня положила по нескольку зерен и передала доску Боре (см. рис.). Трансверсалью доски называется набор из 4 клеток, любые две из которых расположены в разных строках и разных столбцах (см. примеры). Боря за один ход может снять одинаковое количество зерен с каждой клетки какой-либо одной трансверсали. За какое минимальное число ходов Боря может снять все зерна с доски?
За один ход Боря может освободить не более 4 клеток. Следовательно, ему придется сделать минимум 4 хода (так как изначально среди 16 клеток нет ни одной пустой). Заметим, что есть клетка с 8 зернами, а в остальных клетках зерен меньше. Значит с этой клетки зерна придется снимать минимум дважды. Поэтому за 4 хода Боря не справится. Покажем как снять зерна за 5 ходов (серым отмечены трансверсали, с которых сняли зерна):