Олимпиадная задача по комбинаторике: очередь к стоматологу, Мурашкин М.В., 8–10 класс

  Докажем индукцией по n, что для очереди из n ребят через  n – 1  минуту получится расстановка, которую назовём правильной: в начале очереди все девочки, а потом все мальчики. База для одного пациента очевидна – перестановок в очереди не будет вообще.

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