Задача о ряде шашек№ 1
Автор: Большой Грызь
Дата : 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

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


Вы не зарегистрированы либо не вошли в портал!!!
Регистрация или вход в портал - в главном меню.



 Просмотров:   003929    Постингов:   000007