Как-то раз продавец прохладительных напитков Барни предложил двум покупателям следующую задачку.

Барни. Перед вами 10 бумажных стаканчиков, расставленных в ряд. В первые 5 стаканчиков я наливаю кинки-колу, остальные 5 стаканчиков остаются пустыми. Можно ли переставить 4 стаканчика так, чтобы пустые и полные стаканчики чередовались?

Барни. Правильно! Стоит лишь переставить второй стаканчик с седьмым, а четвертый с девятым, как задача будет решена.

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

Проф. Квиббл. Переставлять 4 стаканчика совсем не обязательно. Я берусь решить задачу, переставив лишь 2 стаканчика. Как, по-вашему, это возможно?

Проф. Квиббл. Мое решение проще простого. Я беру второй стаканчик и переливаю его содержимое в седьмой, а содержимое четвертого стаканчика — в девятый.

Глубокая мысль

Хотя предложенное профессором Квибблом шуточное решение основано на неоднозначном толковании слова «переставить» (означающего не только «поменять местами», как полагал Барни, но и «поставить по-другому», чем и воспользовался профессор Квиббл), исходная задача не столь тривиальна, как может показаться. Рассмотрим, например, аналогичную задачу для случая, когда из 200 стаканчиков, выстроенных в ряд, в первые 100 налита кинки-кола, а 100 остальных оставлены пустыми. Сколько пар стаканчиков следует поменять местами, чтобы пустые и полные стаканчики чередовались?

Поскольку следить за 200 стаканчиками довольно трудно, разберем сначала ту же задачу при меньших значениях n, где n — число полных (или пустых) стаканчиков, и попытаемся подметить общую закономерность. Стаканчики можно «моделировать» фишками двух цветов, игральными картами, выложенными на столе рубашкой либо вверх, либо вниз, монетами и тому подобными предметами, наделенными каким-нибудь «двузначным» признаком. При n = 1 для решения задачи не требуется переставлять ни одной пары стаканчиков. При n = 2 решение очевидно и сводится к перестановке одной пары стаканчиков. Возможно, вы удивитесь, когда узнаете, что при n = 3 чередование пустых и полных стаканчиков достигается перестановкой одной пары стаканчиков. Еще немного усилий, и вам откроется довольно простая общая закономерность. При четном n для решения задачи требуется поменять местами n/2 пар, а при нечетном n соответственно (n − 1)/2 пар стаканчиков. Следовательно, если имеется 100 пустых и 100 полных стаканчиков, то задачу можно решить, переставив 50 пар стаканчиков.

При этом вы сдвинете с места 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 ходов?