Перестановки фишек

[wpoms.]

`2*k` фишек расположены в один ряд. За один ход разрешается поменять местами две соседние фишки. За какое наименьшее количество ходов можно добиться того, чтобы каждая фишка побывала на первом и последнем месте?

@темы: Комбинаторика

Comments

[Trotil]

Предлагаю алгоритм для начала:
Разбиваем ряд пополам и ставим задачу правой кучке посетить самое правое место, левой наоборот.
Очевидно, что число ходов равно 2*(0+1+2+...(2^(k-1)-1))=2^(k-1)(2^(k-1)-1)

Далее пусть правая сторона будет стремиться попасть на крайнее левое поле: 2^(k-1)+(2^(k-1)+1)+(...)+(2^k-1) - начиная с самой ближайшей к крайнему левому полю фишки.
При этом кучки поменяются местами, половина фишек побывает на первом и последнем месте, половина - только на одной из нужных мест.
Завершает балет последовательное посещение новой правой кучкой самое правое место - 1*(0+1+2+...(2^(k-1)-1)).

В сумме что-то типа 2^(k-2) (3*2^k-4)

Наверняка неэффективное решение.
Кто лучше?

[All_ex]

Разбиваем ряд пополам... самая левая фишка стремится в правую половину, а самая правая в левую половину... `(2*k-1)` перестановок...
Повторяем эту процедуру `k` раз... При этом все фишки левой половины побываю в крайнем левом положении и переберутся направо... а фишки правой половины переберутся налево и побывают в крайнем правом положении
Затем повторяет тоже самое `(k-1)`, что и завершит процедуру... ИТОГО: `(2*k-1)^2` перестановок.

Для наглядности... на примере `k = 3`
первый прогон:
123|456 - начальное положение
236|145
365|214
654|321
второй прогон:
541|632
412|563
конец алгоритма

Правда как доказать минимальность - не знаю...

[Adjirranirr]

Еще вариант.

Разобьем пополам и пронумеруем фишки. Для того, чтобы фишка из левой половины на позиции `i` (`1 <= i <= k`) добралась до крайней левой позиции, всегда требуется не менее `i - 1` перестановок (очевидно, любая перестановка, не продвигающая фишку «вперед» (к цели =), либо сохраняет ее абсолютное положение, либо сдвигает ее «назад». Таким образом, для каждой фишки потребуется по меньшей мере `i - 1` ходов). Для всех `k` фишек это `sum_{i = 1}^{k} (i - 1) = 1/2 k (k - 1)`. При этом, за это количество ходов можно добиться того, чтобы каждая фишка побывала на крайней левой позиции — смещая поочередно, слева направо.
Иллюстрация.
`1234 -> 2134 -> 2314 -> 3214 -> 3241 -> 3421 -> 4321` (всего `6 = 1/2 * 4 * 3` ходов).

Аналогично (с учетом симметрии) поступим и с правой половиной; тогда, после `k (k - 1)` ходов каждая фишка из левой половины побывает в крайней левой, а каждая из правой половины — в крайней правой позициях.
Теперь заметим, что чтобы перевести любую фишку из левой половины в крайнюю правую позицию, или из правой — в крайнюю левую, потребуется по меньшей мере `k` ходов. Но при этом для двух фишек из разных половин потребуется, по меньшей мере, `2k - 1` ходов, так как первый ход для левой фишки, если они стояли рядом, совпадает с первым ходом для правой. Таким образом, для всех `2k` фишек потребуется `k * (2k - 1)` ходов.
Складывая, получим `k (k - 1) + k (2k - 1) = 3k^2 - 2k`.

Иллюстрация:
`123|456`
`213|465` (+2 хода)
`231|645` (+2 хода)
`321|654` (+2 хода)
`326|154` (+1 ход)
`632|541` (+4 хода)
`635|241` (+1 ход)
`563|412` (+4 хода)
`564|312` (+1 ход)
`456|123` (+4 хода)
Итого 21 ход (т.е. лучше, чем у All_ex =)

Про минимальность, правда, опять вопрос открытый.

[Trotil]

У меня тоже 21 ход.
И конечная расстановка совпадает с расстановкой Adjirranirr.

Изначально в условии было написано 2^k.
Формула моя, если заменить 2^k на 2*k, будет равна k (3 k - 2), совпадает с Adjirranirr,

[Гость]

Se tienen 2k fichas ubicadas en una fila. Una movida consiste en intercambiar dos fichas vecinas. Se deben realizar varias movidas de modo que cada ficha visite la primera y la última posición. ¿Cuál es el menor número de movidas necesarias para lograr esto?

2k фишек расположены в один ряд. За один ход разрешается поменять местами две соседние фишки. За какое наименьшее количество ходов можно добиться того, чтобы каждая фишка побывала на первом и последнем месте?

[All_ex]

лучше, чем у All_ex =) - Ну, да... я в концовке лишних ходов понаделал...