July 2nd, 2011

тигр

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

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

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

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

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

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

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

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

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

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

Collapse )
  • Current Music
    Eliane Elias -- Crystal and Lace