В следующих четырех задачах мы будем заниматься составлением «волшебных квадратов». Так называются квадратные таблицы чисел, в которых 95 суммы чисел в каждой строке, каждом столбце и в каждой из двух диагоналей квадрата все равны между собой.

 

 

Расставить три числа

В каждой из 9 клеток квадрата (рис. 1) поставить одно из чисел 1, 2, 3 так, чтобы сумма чисел, стоящих в каждом вертикальном ряду, в каждом горизонтальном ряду, а также по любой диагонали равнялась 6.

Найти все расстановки.

 

 

Расставить 9 чисел

В квадрате, состоящем из 9 клеток, расставить числа 1, 2, 3, 4, 5, 6, 7, 8, 9 так, чтобы суммы чисел, стоящих в каждом вертикальном ряду, в каждом горизонтальном ряду, а также на любой диагонали были равны.

---

 

Расставить 25 чисел

Расположить 25 чисел, от 1 до 25, в квадрате из 25 клеток так, чтобы в каждой строке, в каждом столбце, а также по обеим диагоналям квадрата получились одинаковые суммы.

---

 

Расставить 16 чисел

В квадрате, состоящем из 16 клеток, расставить целые числа от 1 до 16 так, чтобы суммы чисел, стоящих в каждом вертикальном ряду, в каждом горизонтальном ряду, а также на любой диагонали были равны.

---

 

Расставить четыре буквы

В квадрате, состоящем из 16 клеток, расставить четыре буквы так, чтобы в каждом горизонтальном ряду, в каждом вертикальном ряду и в каждой диагонали встречалась только одна буква.

Как велико число решений этой задачи при одинаковых и разных буквах?

---

 

Расставить 16 букв

В квадрате, состоящем из 16 клеток, расставить 16 букв (четыре буквы а, четыре b, четыре с, четыре d) так, чтобы в каждом горизонтальном ряду и в каждом вертикальном ряду любая буква встречалась только один раз.

 

Аналогичный вопрос можно поставить для квадрата, состоящего из 25, 36 и в общем случае n² клеток. Квадратная таблица, в которой каждый ряд является перестановкой некоторого числа различных букв или цифр, причем в каждом столбце буквы или цифры различны, называется латинским квадратом. Такие квадраты впервые изучал Эйлер в 1782 году. Термин «латинские» связан с тем, что элементы квадрата обозначались латинскими буквами а, b, с, ... Количество различных латинских квадратов из n² клеток очень быстро растет с увеличением числа n. Условимся обозначать через k! произведение всех целых чисел от 1 до k, k! = 1 ٠ 2 ٠ 3 ٠ . . . ٠ k. Известно, что существует не менее чем n! • (n — 1) ! ... • 2! • 1! латинских квадратов размером n х n. Точное значение этого количества известно только при маленьких n.

---

 

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

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

---

 

Шахматный матч

В шахматном матче встречаются две команды, состоящие из четырех человек. Каждый участник должен сыграть по одной партии с каждым игроком противной команды. Требуется составить расписание турнира так, чтобы:

1) каждый шахматист сыграл две партии белыми и две партии черными фигурами;

2) в каждом туре обе команды играли две партии белыми и две черными фигурами.

 

Можно предлагать задачи, подобные двум последним, для любого числа n офицеров и полков и для команд с любым числом участников. Легко видеть, что при n = 2 первая задача неразрешима. Невозможно разместить четырех офицеров двух званий из двух полков так, как требуется в условии этой задачи. В 1782 году Эйлер предположил что задача неразрешима при n = 2, 6, 10, 14, . . . , т. е. при всех n, которые при делении на 4 дают в остатке 2. Это было подтверждено в 1900 году для n = 6. И, наконец, в 1969 году было установлено, что при всех n ≠ 2, 6 задачу решить можно. Оказалось, что при n > 6 предположение Эйлера неверно.

Он ошибся.