Биография одной задачи: от рождения до решения

<100 full reads
142 story viewsUnique page visitors
<100 read the story to the endThat's 56% of the total page views
2,5 minutes — average reading time

Про две армии мирных ферзей

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

Биография одной задачи: от рождения до решения

День рождения

Вариаций задачи известно великое множество, но вот Андрей Саускан предложил поместить её героев на шахматную доску — и это первый шаг в создании новой задачи. Соединили в одну задачу волка, козу, капусту и шахматную доску:

Допустим, на клетках шахматной доски располагаются волки, козы и капусты; волки козам или козы капустам угрожают как ферзи. Можно ли разместить на доске 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.

У неё очень красивый номер «четверть миллиона» в энциклопедии последовательностей Нила Слоуна. Симпатичного кандидата на этот номер выбирали голосованием; эта задача показалась избирателям самой достойной.