Есть идея! (Гарднер) - страница 12
Поскольку следить за 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.
Не меньший вызов любознательному читателю таят в себе многие необычные варианты той же головоломки. Приведем лишь некоторые из них.