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

3 пояснения:

1. Как должен выглядеть порядок?

1_2_3_4_5_6_7_8_9


2. Как перставляется выбранный том?

2_3_5_1_9_7_4_6_8

Если выбран том 4, то:

а) том 4 снимается с книжной полке и держится в руке. (2_3_5_1_9_7___6_8)
б) все тома, начиная с 4-ой позиции сдвигаются на 1 вправо (2_3_5___1_9_7_6_8)
в) том 4 ставится на своё место. 2_3_5_4_1_9_7_6_8

Если выбран том 5, то:

а) том 5 снимается с книжной полке и держится в руке. (2_3___1_9_7_4_6_8)
б) все тома, начиная с 5-ой позиции сдвигаются на 1 влево (2_3_1_9___7_4_6_8)
в) том 5 ставится на своё место. 2_3_1_9_5_7_4_6_8


3. Запрещено пользоваться теорией вероятности, иначе задача становится тривиальной: вероятность, что когда-нибудь (за бк-шагов) 1-ый том встанет на своё место равно 1 (больше со своего места он не уходит). И далее по индукции.

9й тож станет на свое место и не двинется) и так же по индукции)
Библиотекари тупят а нам тут думай))

Конечно лучше вопрос задавать в виде "Всегда ли библиотекарь сможет расставить тома в правильном порядке?"

Будем доказывать, что сможет от противного (вряд ли такой глупый библиотекарь приятный )
Пусть он нашел способ двигать эти тома бесконечно, тогда есть набор томов в котором каждое из изданий он бесконечное число раз ставит на свое место Рассмотрим том с наименьшим номером из этого набора Для того что бы бесконечное число раз ставить его на свое место он должен бесконечное число раз менять свое положение на неправильное, но этого не может быть поскольку не может быть никогда

Действительно том может поменять положение не неправильное в двух случаях

1)Перед ним на правильное место вставляют том с меньшим номером - такое сможет случиться только конечное число раз так как наш том имеет минимальный номер из всех томов что переставляются неустанно

2)Перед ним стоит том сбольшим номером и его ставят на правильное место - это тоже сможет случиться только конечное число раз После последнего из случаев 1 том с большим номером ну никак не сможет оказаться перед нашим томом.

Ну а раз с томом который должен был бесконечно ставиться на свое место может быть лишь конечное число раз это произведено то мы получили противоречие и можем со спокойной совестью оставить библиотекаря за его конечным занятием

При случайном выборе тома теоретически возможно, хоть и маловероятно, что книгочей будет постоянно брать один и тот же том (например 1) и ставить его на одно и то же место (например 1). И никогда не тронет и не расставит другие книги.
Так что при постановке Богача ответ: неизвестно. Да и нет, как повезет.
Уточнить условие требуется.
Или изменить: Например расстановка случайна, а выбор тома всегда со сдвигом вправо. Тут уже другая задача получается.
Согласен, невнимательно прочитал условие.

Это сообщение отредактировал Michael_13 - 23/09/2005, 20:34

В условиях уже сказано, что он берет том НЕ СТОЯЩИЙ на своем месте.

Всё время один том нельзя брать по условию