poluskinda

Известная головоломка, которую придумал французский математик Эдуард Люка в 1883. Башня представляет из себя восемь дисков, нанизанных в порядке уменьшения размеров на один из трех колышков

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

Чтобы решить этот вопрос, нам следует чуть-чуть усложнить нашу задачу, а точнее обобщить ее, посмотрим, что будет в случае n дисков. Обозначим за T(n) - минимальное число перекладываний, необходимых для перемещения n дисков с одного колышка на другой. Очевидно, что T(1)=1, а T(2)=3.

Давайте найдем T(3), для этого надо перенести два верхних диска на средний колышек, затем перенести третий диск и на него перенести два других. Получаем 2*T(2)+1=7 перекладываний. Это легко обобщить на случай n дисков: сначала надо перенести n-1 меньших дисков на средний колышек, затем перенести большой диск и на него перенести n-1 меньших. Таким образом n дисков можно перенести за 2*T(n-1)+1 перекладываний. Но мы не доказали, что необходимо 2*T(n-1)+1 перекладываний

Действительно, нет ли более короткого пути? Оказывается нет. На некотором этапе мы переносим самый большой диск. Когда мы его переносим n-1 меньших дисков должны находиться на одном колышке, а для того чтобы собрать их вместе, потребуется по меньшей мере T(n-1) перекладываний. После перемещения самого большого диска в последний раз (его могут перемещать и больше одного раза) мы обязаны переместить n-1 меньших дисков обратно. Это требует T(n-1) перекладываний. Следовательно T(n) не меньше, чем 2*T(n-1)+1

Хорошо, мы получили равенство T(n)=2T(n-1)+1, кроме того мы знаем, что T(1)=1, совокупность таких равенств называется рекуррентностью. В данном случае легко угадать решение методом пристального взгляда: T(1)=1, T(2)=3, T(3)=7, T(4)=15, T(5)=31, T(6)=63. T(n)=2^n - 1? Это равенство легко проверить с помощью метода математической индукции.

Представьте себя на месте чиновника, который отвечает за дороги в регионе. И у вас есть проблемный участок - это связь между городом A и B. Есть две дороги - верхняя и нижняя. На первом участке верхней дороги есть ограничение скорости, на максимальной допустимой скорости этот участок можно проехать за 2 часа, после этого идет участок без ограничения скорости, но зато там бывают пробки, на нижнем участке все с точностью до наоборот.

Каждое утро из города A в город B едет одно и тоже количество людей. Каждый человек сам выбирает где ему ехать, он может поехать по верхней дороге и тогда его путь займет 3+y часа, где y - доля людей, которые выбрали верхнюю дорогу, для нижней дороги путь займет 3+x часа, где x - доля людей, которые выбрали нижнюю дорогу (например, если вся люди выбрали верхнюю дорогу, то путь по ней займет 4 часа, а по нижней - 2 часа).

Люди имеют доступ в интернет, а поэтому знают о загруженности дорог, выбирая наиболее свободную. Несложно понять, что тогда люди будут затрачивать на дорогу 3,5 часа. (Человек выбирает менее загруженную дорогу, на ней меньше половины, а тогда время 3+x, где x-меньше 0,5)

И тут к вам приходит помощник, который придумал план: соединить мостом участки, где происходит смена скоростного режима, причем, время пересечения моста занимает всего несколько секунд.

И тут перед вами стоит выбор, строить его или нет. Какое решение вы примете? (после картинки ответ)

Давайте теперь вернемся на место обычного человека. Если дорогу построят, то как нам лучше всего ехать? Самый хороший маршрут, который мы только можем себе представить: поехать по нижней дороге до моста, свернуть на верхнюю дорогу и уже по ней приехать в город. B. Этот маршрут займет 2+x+y часа, звучит лучше, чем 3+x или 3+y, учитывая, что x и y - это доли. Но если все выберут этот маршрут, а все его и выберут, так как он оптимальный, то из-за пробок время поездки займет 4 часа!!! Мы построили дорогу, а среднее время в пути увеличилось!!!

Описаная ситуация является парадоксом Браеса.