Программирование игр и головоломок

последовательность всех целых чисел от 1 до n(n ? 1)/2.

Это — еще и проблема трансформатора (см. рис. 30), Если включить во вторичную обмотку 4 выхода так, чтобы число витков между первым и другими выходами находилось в отношениях 1, 4 и 6, то можно получить 6 напряжений на выходе, образующих арифметическую прогрессию.

Опустим другие физические задачи, порождающие такие последовательности. Четырехчленная последовательность 0—1—4—6, по-видимому, является наибольшей последовательностью, обладающей свойством порождать последовательность первых целых чисел, не пропуская и не повторяя дважды ни одного из них, при попарном вычитании членов этой последовательности.

Так, для 5 целых можно образовать 10 разностей. Поэтому крайние члены должны быть a₁ = 0, a₅ = 10. Чтобы получить в виде разности 9 из двух членов последовательности, нужно, чтобы либо было a₂ = 1, и тогда a₅ ? a₂ = 9, либо a₄ = 9. Эти два решения легко получаются одно из другого операцией симметрии, Поэтому положим a₂ = 1.

К этому моменту мы получили уже a₁ = 0, a₂ = 1, a₅ = 10. Чтобы получить разность, равную 8, нужно взять

— либо a₃ = 2, но тогда разность, равная 1, получается дважды:

a₃ ? a₂ = a₂ ? a₁

— либо a₄ = 8,

— либо a₄ = 9, но тогда снова дублируется разность 1. Следовательно, a₁ = 0, a₂ = 1, a₄ = 8, a₅ = 10.

Достаточно теперь пересмотреть одно за другим возможные значения а₃ и удостовериться, что каждое ив них дублирует какую-то разность.

Для a₃, равного 2, дублируется разность 1:

3 2

4 4

5 5

6 2

7 1

Таким образом, нет последовательности из 5 целых, попарные разности которых порождают 10 первых натуральных чисел. Допустим теперь возможность повторений в последовательности разностей. Можно ли с помощью 5 членов породить — с помощью их разностей — 9 первых натуральных чисел?

Об этих последовательностях ничего не известно. Пусть дано число n членов последовательности; каково наибольшее число последовательных целых чисел, начиная с 1, которые можно получить с помощью попарных разностей членов последовательности?

Запрограммировать это не очень трудно. Но берегитесь чересчур долгих вычислений!

?** Головоломка 24. Прогулка королевы.

Нет, не в Булонском лесу, если говорить серьезно… Прогулки фигур на шахматной доске — классический сюжет для головоломок. Эйлеровский конь должен обойти всю шахматную доску и вернуться на поле, с которого отправился в путь, не попадая дважды ни на одну клетку. Это настолько общеизвестно, что это уже и не головоломка. Но если вы не знаете решения, я не мешаю вам попробовать.

Случай «королевы» (ферзя) — немного другой. Эта фигура может перемещаться по горизонтали, по вертикали или по диагонали. Назовем «движением» перемещение на некоторое число полей в определенном направлении, Разрешается много раз проходить по одному и тому же полю. Но требуете пройти все поля эа наименьшее возможное число движений, причем, конечно, нужно вернуться на исходное поле. Так как число движений не дано, то не попытаетесь ли вы сначала проделать все вручную, чтобы угнать верхнюю границу…

???* Головоломка 25. Девушки ив пансиона Киркмана.

Пансион Киркмана — это колледж для девушек из высшего общества. Надзирательницей там — мисс Фармер. Каждую среду после полудня она сопровождает класс на прогулку. В своей нарядной униформе, в соломенных шляпках они медленно вышагивают по трое в три ряда. Мисс Фармер несговорчива: «Я не хочу маленьких компаний; вы должны располагаться так, чтобы не оказаться с той же подругой в вашем ряду до тех пор, пока вы не проведете этих прогулок со всеми остальными». На это наши девушки заявили, что поступать так очень трудно. Поэтому мисс Фармер решила сама организовать ряды. Для начала она веяла класс с 9 ученицами. Ей удалось быстро организовать ряды. У каждой ученицы было 8 подружек, и она должна была находиться с двумя новыми подружками каждую неделю, так что мисс Фармер предусмотрела цикл в 4 недели.

Затем мисс Фармер был поручен класс с 15 ученицами. Поэтому было необходимо ввести цикл в 7 недель для того, чтобы каждая ученица была за это время в одном ряду с 14 остальными. Тогда мисс Фармер поняла, в какое ужасное предприятие она оказалась вовлеченной.

Хотите ей помочь? Но заметьте: это вы сами пускаетесь в это ужасное предприятие. Всячески желаю, чтобы вашему микрокомпьютеру было больше нечего делать. Попытайтесь, если все предыдущее не будет отнимать долгие часы…

Эта задача принадлежит Т. П. Киркману и была впервые опубликована в Lady?s and Gentleman?s Diary за 1850 год. Для ее решения нужно пролить немало чернил, и вы можете рассмотреть значения, отличные от 9 и 15. Но выглядит вполне правдоподобным, что 15 — патологическое число, и Роуз Болл [BAL] предложил геометрический подход к решению, если число девочек не равно 15. Может быть, подход с точки зрения информатики позволит вам получить в этой задаче новые результаты…

*** Головоломка 26. Пентамино.

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

Все они приведены на рис. 31. Эти двенадцать шашек, каждая из которых имеет площадь 5, могут быть собраны в прямоугольник с площадью 60. Есть много решений для прямоугольника 6 ? 10, а также 5 ? 12. Меньше решений для прямоугольника 4 ? 15 и только два для прямоугольника 3 ? 20, если, конечно, не различать решения, отличающиеся только симметрией. Можете ли вы найти их за разумное время на вашем компьютере, проверив, что их действительно именно 2?

Есть много путей подхода к этой задаче, даже если все они действуют согласно одной и той же стратегии: перебрать все возможные попытки. Но есть ходы, которые ни к чему не могут привести. Вы не можете начать с того, чтобы поставить Т в левый нижний угол, как на рис. 32. Ни одна шашка не может замкнуть две заштрихованные области рядом с Т… Здесь есть необходимость и для хорошего представления позиций, но также и немного — для хитрости…

* Головоломка 27. Песенка почти спета.

Знаменитая игра Армана Жаммо уже была упомянута выше (игра 12). Но сейчас мы еще не описываем ее полностью; она довольно трудна для программирования. Вот другая форма, которую проще реализовать и которая еще не лишена интереса. Я верю также, что для любителей математических развлечений здесь есть что делать.

Возьмем случайным образом p двузначных чисел. Возьмем случайным образом также двузначное число s. Соединим эти p чисел между собой сложениями или вычитаниями. Все числа должны быть использованы. Можно ли таким образом получить число s?