Задача 7.
В очереди в школьную столовую стоят 16 школьников так, что мальчики и девочки среди них чередуются. (Первым стоит мальчик, за ним — девочка, за ней — снова мальчик и так далее.) Любой мальчик, за которым в очереди стоит девочка, может поменяться с ней местами. Через некоторое время оказалось, что все девочки стоят в начале очереди, а все мальчики — в конце. Сколько обменов было совершено?
Ответ на Задачу 7.
Ответ: 36 обменов.
Решение:
Заметим, что в конечном итоге каждый мальчик совершит по одному обмену с каждой девочкой, которая стоит в очереди после него. Т.е. первый мальчик совершит 8 обменов, второй — 7, третий — 6, и т.д. Тогда общее число обменов равно:
8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36
Нетрудно понять, что если каждый мальчик будет стремиться уступить место следующей за ним девочке, то рано или поздно все девочки окажутся в начале очереди. И вправду, предположим, что в какой-то момент никакой мальчик не может уступить место, но ещё не все девочки стоят в начале очереди. Тогда есть девочка, которая стоит среди мальчиков. Тогда есть мальчик, который может уступить ей очередь. Противоречие.
