Cool Folders ® :: Форум Игротека :: Задача о ряде шашек

Задача о ряде шашек

Автор: Большой Грызь
Дата : 15-12-02, Вск, 04:22:31

N белых и N черных шашек расположены в ряд (без определенного порядка).
За один ход разрешается поменять две шашки местами, между которыми расположено не более, чем N-1 шашка.
За какое минимальное количество ходов можно гарантированно добиться того, чтобы слева стояли все белые шашки, а справа - все черные из любого начального расположения.

С доказательством, пожалуйста

--------------------------------------------------------
All things good to know are difficult to learn.

[ 15-12-02, Sun, 11:23:53 Отредактировано: Большой Грызь ]

Задача о ряде шашек

№ 2

Автор: Паша
Дата : 15-12-02, Вск, 05:01:51

Послушаюсь собственного совета и напишу решение на Пейджер. Только простая она, меньше минуты над ней думал...

Задача о ряде шашек

№ 3

Автор: Урод и мразь
Дата : 15-12-02, Вск, 05:19:23

Заменим белые шашки пустыми местами. Тогда условия задачи будут следующими: в ряду из 2*N позиций стоит N шашек. За один ход мы можем передвинуть любую шашку не более чем на N позиций и поставить её на свободное место. За сколько ходов мы можем поставить шашки на левые N мест?

Ответ очевиден: за N. Ставим самую левую шашку на 1 место слева, затем следующую на 2 место и т.д. Меньше, чем за N, мы не можем, если все шашки стоят на N правых позициях.

[ 15-12-02, Sun, 12:21:03 Отредактировано: Урод и мразь ]

Задача о ряде шашек

№ 4

Автор: Большой Грызь
Дата : 15-12-02, Вск, 05:24:57

УиМ, ответ не совсем верен, ибо нет прямого док-ва того, что ты всегда сможешь переставить K-тую шашку на К-тое свободное место - это не очевидно, что расстояние будет меньше N.

--------------------------------------------------------
All things good to know are difficult to learn.

Задача о ряде шашек

№ 5

Автор: Урод и мразь
Дата : 15-12-02, Вск, 05:26:19

К-я шашка не более чем на N+K - м месте, поскольку справа от неё N-K шашек.

[ 16-12-02, Mon, 22:16:14 Отредактировано: Урод и мразь ]

Задача о ряде шашек

№ 6

Автор: Willy
Дата : 15-12-02, Вск, 05:28:59

Не понятно зачем давать решение через час после условия? Надо хотя бы пару дней дать на раздумье.

Задача о ряде шашек

№ 7

Автор: Урод и мразь
Дата : 15-12-02, Вск, 05:42:09

Задача слишком простая для пары дней, имхо. Впрочем, Грызь может стереть моё решение, если хочет..