Про две армии мирных ферзей
В группе математиков обсуждали вариации задачи про волка, козу и капусту. Вы, конечно, знаете про затруднения крестьянина, которому нужно было их переправить через реку. Автором этой задачи считают Алкуина, средневекового поэта и богослова.
День рождения
Вариаций задачи известно великое множество, но вот Андрей Саускан предложил поместить её героев на шахматную доску — и это первый шаг в создании новой задачи. Соединили в одну задачу волка, козу, капусту и шахматную доску:
Допустим, на клетках шахматной доски располагаются волки, козы и капусты; волки козам или козы капустам угрожают как ферзи. Можно ли разместить на доске 6 коз, 7 волков и 7 капуст?
«Причешем» задачу
— это будет второй этап в жизни задачи. Волков и капусту совершенно необязательно различать в такой постановке; все равно они друг другу не угрожают. В сущности, в условии участвуют не три, а две группы фигур, причем угрожают они друг другу как ферзи. От персонажей остались
только рожки, ножки и кочерыжки, но задача стала естественней и проще для восприятия:
На шахматной доске выстроились две армии ферзей, причем так, что белые и чёрные ферзи не угрожают друг другу (армии мирные). В чёрной армии 6 ферзей. На рисунке приведен пример такого расположения шести черных ферзей, что осталось место для 12 мирных белых ферзей.
Вопросы по возрастанию сложности. Показать, что:
1) можно так разместить 6 черных ферзей, что останется место для 14 мирных белых ферзей;
2) можно так разместить 6 черных ферзей, что останется место для 15 мирных белых ферзей;
3) нельзя так разместить 6 черных ферзей, что останется место для 16 мирных белых ферзей.
Решение
Первый естественный подход — подбор. Я спрашивала разных людей, как они подбирали решение. И почти все сказали, что они сужали пространство вариантов. Решение найти было проще, поставив себе разумные ограничения, например:
- начать расставлять 6 черных ферзей, а белые ставить куда останется место;
- сгрудить черных ферзей в уголочке, убирать их оттуда по одному и смотреть что получится;
- начать с симметричного расположения ферзей.
Сузить поле для перебора — идея, которая кажется контринтуитивной, но работает во многих задачах, далеких от расстановки ферзей.
Второй естественный подход — перебрать все возможные варианты на компьютере. Быстро, эффективно, хотя и не даст жизненного опыта с плюсами самоограничения :).
Павел Хворых показал, что вариантов расположения 6 черных и 15 белых мирных ферзей всего два:
Отсюда уже легко вывести, что 6 черных и 16 белых мирных ферзей на доску поставить нельзя.
Семейство
Четвертый этап — посмотреть, как задача вписывается в существующий задачный корпус, с какими областями математики связана, есть ли похожие задачи.
Задача о мирных ферзях известна давно: шахматный композитор Макс Беззель опубликовал головоломку "Восемь ферзей" в 1848 году. Требовалось на шахматной доске расположить 8 мирных ферзей так, чтобы они не угрожали друг другу. Задачу быстро обобщили на случай доски произвольного размера. А в В 1972 году Эдсгер Дейкстра на примере этой задачи проиллюстрировал мощь структурированного программирования: Дейкстра очень подробно описал эффективный алгоритм, который находит все расположения ферзей при любом размере доски.
Еще одно обобщение — расставить на шахматной доске размера NxN две равные по численности армии мирных ферзей, когда черные ферзи не угрожают белым, а белые не угрожают черным; причем найти наибольшее число А(N) ферзей в такой расстановке. Это уже близкий родственник нашей задачи. Последовательность А(N) построена до N=15:
0, 0, 1, 2, 4, 5, 7, 9, 12, 14, 17, 21, 24, 28, 32.
У неё очень красивый номер «четверть миллиона» в энциклопедии последовательностей Нила Слоуна. Симпатичного кандидата на этот номер выбирали голосованием; эта задача показалась избирателям самой достойной.