Есть идея! - [7]
При этом вы сдвинете с места 100 стаканчиков. Предложенное профессором Квибблом шуточное решение позволяет вдвое уменьшить число стаканчиков, сдвигаемых с места.
Существует одна классическая головоломка, очень похожая на только что рассмотренную нами задачу, но несколько более трудную. Начнем с 2n предметов, выстроенных в ряд. Пусть по-прежнему n предметов, составляющих первую половину ряда, будут одного типа, а n предметов, составляющих вторую половину ряда, будут другого типа. (Как и прежде, их можно «моделировать» стаканчиками, фишками, игральными картами и т. п.) Требуется переместить предметы так, чтобы предметы одного типа чередовались с предметами другого типа, но в отличие от предыдущей задачи слову «переместить» придается строго определенное значение. На этот раз слово «переместить» означает, что любые два соседних предмета разрешается, не изменяя их последовательности, изъять из ряда и пристроить к любому свободному концу (после одного или нескольких ходов ряд может распасться на несколько звеньев).
Вот как это делается, например, при n = 3:
Как выглядит общее решение? При n = 1 решение тривиально. При n = 2 задача, как нетрудно выяснить, неразрешима. При всех n > 2 головоломка допускает решение не менее чем за n ходов.
Найти решение при n = 4 не так-то просто, и поиск его, несомненно, доставит вам немало удовольствия. Может быть, вам удастся сформулировать алгоритм решения головоломки за n ходов при любом n > 3.
Не меньший вызов любознательному читателю таят в себе многие необычные варианты той же головоломки. Приведем лишь некоторые из них.
1. Правила перемещения пар остаются теми же за одним исключением: если пара образована предметами различных типов, то перед тем, как пристроить ее к свободному концу, последовательность предметов в паре следует изменить. Например, перемещая две фишки, первая из которых (левая) красная, а вторая (правая) черная, их необходимо поменять местами, после чего первой станет черная, а второй красная фишка, и лишь после этого пристраивать к свободному концу. При 8 фишках существует решение в 5 ходов. При 10 фишках 5 ходов также оказывается достаточно. Общее решение неизвестно. Может быть, вам удастся найти его.
2. Правила такие же, как в исходной задаче, но фишек одного цвета на 1 меньше, чем другого, то есть фишек одного цвета n, а фишек другого n + 1. Доказано, что при любом n задачу можно решить за n² ходов, причем это число минимально.
3. Имеются фишки трех различных цветов. Пары соседних фишек перемещаются по обычному правилу с тем, чтобы фишки каждого цвета оказались выстроенными подряд. При n = 3 (всего 9 фишек) существует решение в 5 ходов. И в этом, и во всех предыдущих вариантах головоломки предполагается, что после последнего перестроения фишки стоят в ряд «сомкнутым строем» (без пробелов). Если ряд может содержать пробелы, то существует необычное решение всего лишь в 4 хода.
Напрашиваются и другие варианты головоломки. Насколько известно, их никто ранее не предлагал и уж конечно не решал. Например, в каждом из приведенных нами вариантов головоломки за один ход можно перемещать не по две, а по три (и более) соседние фишки.
Что произойдет, если на первом ходу переместить фишку, на втором — 2 фишки, на третьем — 3 фишки и т. д.? Если в ряд выстроены n фишек одного цвета и затем п фишек другого цвета, то всегда ли правильного чередования цветов можно добиться за n ходов?
Дороги, которые мы выбираем
Маленькая Сьюзен в большом затруднении. Дело в том, что по дороге в школу ее то и дело подстерегает скверный мальчишка Станки.
Станки. Эй, Сьюзен! Можно, я пойду с тобой?
Сьюзен. Нет, очень тебя прошу, уйди!
Сьюзен. Я придумала, что мне делать. Буду ходить в школу каждое утро другой дорогой. Тогда Станки ни за что не догадается, где меня можно подстеречь.
На этой карте показаны все улицы между домам Сьюзен и ее школой. Направляясь в школу по намеченному маршруту, Сьюзен идет либо строга на восток, либо на юг.
Здесь вы видите Сьюзен, идущую в школу по другой дороге. Разумеется, ей не хотелось бы удаляться от школы. Сколькими способами можно добраться от дома Сьюзен до школы?
Сьюзен. Хотела бы я знать, сколько различных дорог ведет от моего дома к школе. Подумаем! Сосчитать их, должно быть, не просто. Впрочем… Есть идея! Сосчитать дороги совсем не трудно! Очень даже просто!
Какая идея пришла в голову Сьюзен?
Вот как она рассудила.
Сьюзен. У того перекрестка, возле которого я живу, поставлено на карте число 1: выйти из дома я могу лишь одним способом. У перекрестков, расположенных в одном квартале к востоку и к югу от дома, я поставлю по 1, потому что до каждого из них можно добраться только одним способом.
