12
1

Вот неплохая, на мой взгляд, олимпиадная задача.

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

задан 27 Апр '17 20:48

"пятнашки" напоминает...

(27 Апр '17 21:15) all_exist

@all_exist: а почему? Мне это напоминает серию задач о расстановке томов на полке, но с ограничениями.

(27 Апр '17 21:18) falcao

@falcao, ну, процесс перестановки "сидельцев" вызвал такую ассоциацию...

(27 Апр '17 21:23) all_exist

@all_exist: но ведь они в линию расположены, а не в "квадратик"!

(27 Апр '17 21:40) falcao

@falcao, "не принимайте близко к сердцу" - это просто ассоциация... ))) ... ну, может неверно назвал детскую забаву... были всякие другие, типа "ранжира"... в общем не суть важно... мой ассоциативный ряд двигался в этом направлении... ))) ...

(27 Апр '17 21:46) all_exist

ну в пятнашках начальная позиция кодируется перестановкой из 16 чисел, после чего к ней применяются какие-то перестановки. Там есть несложная теория как получить начальный набор, но я её не помню. В этом смысле там не важно квадратик или линия

(28 Апр '17 1:27) abc

Скорее это похоже на сортировку методом пузырька. Передвигаем человека с первым номером билета к своему месту. Если в некоторый момент обмен может произойти с тем, кто займет свое место, то предварительно отодвигаем такого соседа вверх, чтобы он не закупорил дорогу остальным "сидельцам"

(28 Апр '17 1:35) kadavr

@kadavr: а что если при описываемом отодвигании кто-то снова окажется на своём месте, и потом его будет уже не согнать?

(28 Апр '17 2:00) falcao

@falcao, а что если при описываемом отодвигании кто-то снова окажется на своём месте - вот этот момент и вызвал мои ассоциации... в алгоритмах "переставлялок" часто используется сдвигание элемента подальше от своего места, прежде чем вернуть его обратно...

(28 Апр '17 4:51) all_exist
показано 5 из 9 показать еще 4
10|600 символов нужно символов осталось
5

Индукция. Для двух зрителей всё очевидно.

Индуктивный переход. Достаточно доказать, что можно сделать несколько пересадок так, что зритель $%A$% с билетом на первое место передвинется ближе к первому месту и при этом либо все зрители далее не сидят на своих местах, либо несколько первых зрителей заняли свои места, а остальные зрители далее не сидят на своих местах. Рассмотрим два возможных случая:

  1. У зрителя сидящего непосредственно перед $%A$%, билет не на следующее место, тогда достаточно пересадить местами этих двух зрителей.
  2. Пускай $%k$% - наибольшее такое число, что у $%k$% зрителей сидящих непосредственно перед $%A$%, билеты на следующее место по отношению к месту, на котором сидят. Если такая цепочка зрителей начинается с первого места, то "двигаем" $%A$% до первого места, в противном случае "двигаем" зрителя перед первым зрителем в этой цепочке вплоть до пересадки с $%A$%.
ссылка

отвечен 28 Апр '17 11:46

изменен 28 Апр '17 13:48

@EdwardTurJ: я рассуждал фактически так же точно, только ставил сначала n-го на последнее место.

(28 Апр '17 16:03) falcao
10|600 символов нужно символов осталось
0

А как если доказать по мат индукции расположение чисел по возрастанию. Для начальных 2 или 3 зрителей по порядку расположить можно. Для n скажем верно. Для n+1: пусть на первом месте будет с номером k. Эту оставим, остальных n можно расположит по порядку (потому что, для n предположение верно), но здесь на своем месте находятся только начиная с k+1 до n+1. Номер k который находится на первом месте постепенно двигаем вправо до своего места. И все станут на свои места.

ссылка

отвечен 28 Апр '17 9:59

@Rams кого посадите на k-ое место, 1-го? А остальных на свои - как? И если всё это Вам удастся, то как Вы пересадите 1-го и k-го, если они оказались не рядом, то есть $%k\ne 2$%?

(28 Апр '17 10:53) bot

Для n+1: пусть на первом месте будет билет с номером k (k может принимать значения 2,3,.., n+1). Начиная со 2-го по n+1 местах находятся n зрителей. Их можно расположить по возрастанию номеров (так как, для n верно). После этого ряд станет таким k 1 2 3 ... k-1 k+1 k+2 ... n+1 ;

следующие шаги

1 k 2 3 ... k-1 k+1 k+2 ... n+1
1 2 k 3 ... k-1 k+1 k+2 ... n+1
.....
1 2 3 4 ... k k+1 k+2 ... n+1 Например для 4-х зрителей с номерами 3 1 4 2 (3 не трогаем по алгоритму, кот. описано выше, хотя есть и такой вариант решения)
1-шаг 3 1 2 4

2-шаг 1 3 2 4

3-шаг 1 2 3 4

(28 Апр '17 12:56) Rams

@Rams: в таком виде индукция не работает, поскольку утверждение "расставим всех по порядку" применимо к "сплошному" набору номеров. Если рассматривать относительные номера, то нарушается отношение "находиться на своём месте".

(28 Апр '17 16:07) falcao

Здесь А.Шаповалов предлагает другой подход к решению, если кому интересно http://sasja.shap.homedns.org/Knigi/Uzkoe/shapovalov-uzkoe.pdf

24-стр Задача 20.

(3 Май '17 9:02) Rams

@Rams: спасибо за ссылку. Теперь буду знать источник этой задачи. Но там идея решения в точности та же самая. Можно проводить индукцию сначала по числу участников, а потом по степени удалённости первого (или последнего) от своего места. Можно вместо этого рассматривать минимальный контрпример с теми же свойствами. Это фактически одно и то же (то есть равносильные формулировки принципа математической индукции).

(3 Май '17 9:23) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,114

задан
27 Апр '17 20:48

показан
7078 раз

обновлен
3 Май '17 9:23

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru