164. Разместить 16 офицеров

В каждом из четырех полков выбрано по четыре офицера разных званий (полковник, майор, капитан, лейтенант). Требуется разместить эти шестнадцать офицеров в виде квадрата так, чтобы в каждом горизонтальном ряду и в каждом вертикальном ряду был офицер каждого звания и представитель каждого полка.

Решение. Обозначим для краткости звания офицеров буквами П, М, К, Л, а номера полков цифрами 1, 2, 3, 4. Очевидно, каждый офицер полностью характеризуется парой: (буква, цифра). Например, i (/С, 3)-капитан из третьего полка. Задача, следовательно, сводится к тому, чтобы в 16 клетках квадрата разместить по четыре буквы Я, М, К, Л и по четыре цифры 1, 2, 3, 4 так, чтобы в каждом горизонтальном и вертикальном ряду не было одинаковых букв и цифр. Кроме того, все пары (буква, цифра) должны быть различны.

Расположим сначала буквы (см. предыдущую задачу) так, как показано на рис. 169.

Рис. 169

Чтобы разместить цифры, мы сначала приставим к каждой букве соответствующую ей по порядку цифру (т.е. ко всем приставим 1, ко всем М приставим 2, ко всем К приставим 3, ко всем Л приставим 4), а затем переставим каждую цифру в клетку, симметричную относительно диагонали (П, К, Л, М). В результате получим рис. 170. Это расположение и является ответом к задаче.

Рис. 170