Falcão (falcao) wrote,
Falcão
falcao

  • Mood:
  • Music:

перекладывание карт

Что-то я давно не писал никаких "эссе" на математические темы. Этот пост у меня будет открытым, как и почти все предыдущие из той же серии. Сразу же хочу предупредить, что слово "математика" никого не должно "обескураживать". Я стараюсь писать максимально "популярно", и эти посты адресованы всем, у кого есть хоть какой-то интерес. Но при этом не требуется никакой подготовки. Если кто-то считает, что "забыл всё по школьной программе", то это ничему не препятствует.

Я хочу рассмотреть здесь одну задачу, о которой однажды уже писал в подзамочном посте. Сейчас я приведу подробное её решение под "катом", причём для общего случая. А сейчас -- формулировка.

У игрока на руках имеется 13 карт одной масти, расположенных в порядке от туза до двойки. За один ход разрешается извлечь несколько карт, идущих подряд (можно всего одну), и вставить эти карты в таком же порядке в другое место (то есть между какими-то двумя картами, или в самое начало, или в самый конец). Требуется за минимальное число ходов расположить карты в противоположном порядке, то есть от двойки до туза.

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

Т К Д В 10 9 8 7 6 5 4 3 2

Т К 10 9 8 7 6 Д В 5 4 3 2

В таких задачах обычно надо сделать две вещи. Во-первых, предъявить сам способ перекладывания, приводящий к нужному ответу. Сразу хочется отметить, что таких способов может быть очень много, и они вовсе не обязаны совпадать в разных решениях. Во-вторых, и это здесь наиболее трудно -- надо доказать, что за меньшее число ходов справиться с той же задачей нельзя, подтвердив тем самым, что предложенный способ в самом деле приводит к минимально возможному числу ходов.

Понятно, например, что в данной задаче очень легко справиться за 12 ходов, перекладывая карты по одной: на первом ходу двойку переносим в самое начало, на втором -- вставляем вслед за ней тройку, затем ставим на нужное место четвёрку, и так вплоть до переноса короля. Однако это количество ходов слишком велико, и хватает гораздо меньшего числа операций.

Задачу можно решить самостоятельно, а можно ознакомиться с приводимым далее решением. У меня есть только просьба к комментаторам -- не помещать ничего непроверенного. Допустим, кому-то увиделся способ решения за число ходов, которое меньше того, что заявлено у меня. В этом случае полезно "семь раз отмерить", то есть проверить правильность предлагаемого решения. Здесь есть ещё такой "подводный камень", что данный тип задач довольно часто встречается на олимпиадах, и возможны разные правила перекладывания с разными ответами. Например, иногда разрешается менять местами любые две карты. Или любые две стоящие рядом карты. Такие задачи тоже имеют смысл, но они отличаются от сформулированной выше.


Для удобства будем считать, что вместо карт у нас имеется n чисел. Мы рассмотрим самый общий случай, а сформулированная задача будет представлять собой частный случай, где n=13.

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

Очевидно, что f(1)=0, а также что f(2)=1. Поэтому будем далее считать, что n не меньше 3. Рассмотрим случай нечётного числа n, полагая n=2k+1, где k>=1. Покажем, как справиться при этом за k+1 ход. Тем самым будет установлено неравенство f(2k+1)<=k+1.

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

k+1 k+2 ... 2k 1 2 ... k 2k+1

При этом мы сможем на последнем, то есть (k+1)-м ходу перенести группу чисел от 1 до k в самое начало, располагая всё в порядке возрастания.

Чтобы получить указанную выше конфигурацию за k ходов, мы будем k раз передвигать влево группу из двух стоящих рядом чисел. А именно, сначала мы возьмём числа с номерами k+1 и k, которые изначально расположены подряд, и перенесём их в крайнее левое положение. В этот момент карты с номерами k+2 и k-1 станут соседними, и их мы следующим ходом вставим между только что перенесёнными картами. В итоге наша конфигурация будет начинаться с такого расположения: k+1 k+2 k-1 k, а карты k+3 и k-2 станут соседними. На третьем ходу их надлежит вставить между перенесёнными ранее двумя картами, в результате чего слева расположатся карты k+1 k+2 k+3 k-2 k-1 k, и так далее. На шаге с номером k мы перенесём числа 2k и 1, в результате чего наша цель будет достигнута.

В частности, мы доказали, что f(13)<=7, то есть семи ходов нам достаточно. Но пока остаётся открытым вопрос о том, а нельзя ли справиться быстрее?

Это был случай нечётного числа, а теперь предположим, что n чётно, полагая n=2k. То же самое рассуждение показывает, что k+1 хода здесь достаточно, то есть f(2k)<=k+1. Во всех описанных действиях достаточно просто считать число 2k+1 "невидимым".

Можно теперь записать два неравенства в одном и том же виде, а именно в виде f(n)<=[n/2]+1. Квадратные скобки означают здесь так называемую "целую часть числа", то есть результат округления до целого в меньшую сторону. Например, согласно этому определению, [3,8]=3.

Сейчас мы докажем что на самом деле f(n)>=[n/2]+1 при n>=3, то есть найденная оценка является оптимальной. Тем самым будет доказано то, что f(13)=7, то есть сформулированная в тексте задача решается за 7 ходов.

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

Т К Д В 10 9 8 7 6 5 4 3 2

Т К 10 9 8 7 6 Д В 5 4 3 2

Таким образом, происходит следующее: мы раскрашиваем в синий и красный цвет две группы карт, расположенные друг за другом вплотную (последнее важно!), а затем просто меняем эти группы местами. Понятно, что группы могут состоять из одного, двух и более чисел, а также то, что при переносе группы карт вправо, а не влево, возникает полностью аналогичная ситуация.

Далее мы будем обращать внимание на пары чисел, которые в наших расположениях идут подряд, и их мы подразделим на две категории. Если за числом x следует число y, и при этом x меньше y, то такую пару мы будем называть хорошей, а если x больше y, то назовём эту пару плохой. Ясно, что в начальном расположении чисел, то есть n n-1 n-2 ... 2 1, все пары являются "плохими", и их количество равно n-1. А в конечном расположении, которого мы хотим достичь, то есть 1 2 ... n-1 n, все n-1 пар стали "хорошими".

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

... ab...cd...ef ...
... ad...eb...cf ...

Поясним использованные нами обозначения. Пусть b -- самое первое число из левой (синей) группы карт до преобразования, а с -- самое последнее число той же группы. Мы при этом допускаем, что b=c в случае, если синяя группа состоит всего из одной карты. Аналогично, d и e суть первое и последнее число соответственно для красной группы чисел. Через a и f соответственно мы обозначем здесь числа, примыкавшие слева к синей группе карт или справа к красной группе карт, соответственно. В принципе, могло так оказаться, что эти числа отсутствуют.

После преобразования у нас возникает максимум три новых пары, которых не было раньше. Это означает, что "прирост" количества "хороших" пар не может составить больше трёх в результате осуществления одного хода. Но может ли так быть, что он будет равен трём? Оказывается, нет.

Представим себе, что возникли три новых пары, и все они "хорошие". Тогда числа a и f оба присутствуют, и должны выполняться сразу три неравенства: a<d, e<b, c<f. При этом каждая из трёх "исчезнувших" пар должна быть "плохой", что означает выполнение трёх дополнительных неравенств: a>b, c>d, e>f.

Решающий момент состоит в том, что условий получается слишком много, и данные неравенства, взятые вместе, приводят к противоречию: a<d<c<f<e<b<a.

Таким образом, в результате одного хода "прирост" числа "хороших" пар составляет не больше двух. Уже отсюда следует, что "приблизительно" число f(n) составит около n/2, а для получения точной оценки нам осталось сделать одно несложное наблюдение. Дело в том, что после самого первого хода могла возникнуть только одна "хорошая" пара, так как порядок следования соседних чисел изменился только для пары на границе красного и синего участков. То же самое можно сказать и о самом последнем ходе, после которого все числа расположились по порядку, но здесь уже верным будет то, что до преобразования лишь одна пара (на границе синего и красного участка) могла быть "плохой".

То есть за первый ход наш "прирост" числа "хороших" пар составил всего 1, и то же было на последнем ходу, который при n>=3 не совпадает с первым. Между первым и последним ходом было ещё какое-то количество ходов, которое мы обозначим через s (возможно, что s=0). И на каждом из этих промежуточных ходов, у нас количество "хороших" пар могло увеличиться не более чем на 2. В результате же мы сделали 1+s+1=s+2 хода, а число "хороших" пар увеличилось на n-1 (с нуля). Значит, справедливо неравенство n-1<=1+2s+1, то есть s>=(n-3)/2. А это означает, что общее количество сделанных ходов удовлетворяет неравенству s+2>=(n+1)/2.

Итак, нами теперь установлено, что f(n)>=(n+1)/2 при всех n>3. При n=2k+1 это сразу даёт f(2k+1)>=k+1, а при n=2k и установленного факта, что f(2k)>=k+1/2, сразу имеем неравенство f(2k)>=k+1, поскольку число ходов принимает целые значения.

В заключение хотел бы отметить, что это рассуждение мне повстречалось в статье шведских авторов. Статья достаточно "современная", то есть опубликована она уже в XXI веке!
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 9 comments