|
|
 |
Условие
В очереди к стоматологу стоят 30 ребят: мальчиков и девочек. Часы на стене показывают 8:00. Как только начинается новая минута, каждый мальчик, за которым стоит девочка, пропускает её вперед. Докажите, что перестановки в очереди закончатся до 8:30, когда откроется дверь кабинета.
Решение
Докажем индукцией по n, что для очереди из n ребят через n – 1 минуту получится расстановка, которую назовём правильной: в начале очереди все девочки, а потом все мальчики. База для одного пациента очевидна – перестановок в очереди не будет вообще.
Шаг индукции. Если в очереди нет девочек, то утверждение очевидно. Пусть девочки есть. Рассмотрим самую первую девочку D в очереди. Если перед ней нет мальчиков, то она не участвует в перестановках, и по предположению индукции (D можно мысленно убрать) через n – 2 минуты получится правильная расстановка. Если же перед D есть мальчики, то рассмотрим ситуацию через минуту: за D будет стоять мальчик; далее D каждую минуту перемещается на одну позицию вперед, пока не окажется в начале очереди, а остальные девочки меняются так, как будто девочки D нет в очереди. (Действительно, D может помешать девочке D' поменяться с мальчиком только в случае, если D' стоит точно за D; но если за D стоит девочка, значит, в предыдущую минуту D не менялась местами, и они стоят в начале очереди.) Таким образом, по предположению индукции ещё через n – 2 минуты все остальные девочки выстроятся впереди мальчиков вслед за D, то есть получится правильная расстановка.
