В таинственном лесу два мудреца в чёрном и белом колпаках раздают гномикам грибочки. К ним в две очереди выстроились 2n гномиков, n в чёрных и n в белых колпаках. Если к мудрецу подходит гномик с таким же цветом колпака, то гномик получает грибочек и удаляется, а иначе отправляется в конец очереди к другому мудрецу. За какое наименьшее количество направлений в другую очередь мудрецы могут раздать всем гномикам по грибочку, если в процессе раздачи мудрецы могут один раз поменяться колпаками? (Мудрецы сами решают, в какой момент и к кому из них подойдёт следующий гномик из соответствующей очереди. Очереди могут быть разной длины. Все грибочки совершенно одинаковы.)
Докажем, что можно обойтись n неправильными попаданиями в очередь. Допустим, мудрецы не меняются вообще, и тогда в неправильную очередь попадает k гномиков. Если мудрецы поменялись бы колпаками в самом начале, то в неправильной очереди оказались бы в точности все остальные, то есть 2n − k. Минимум из 2n − k и k не превосходит n.
Покажем, что существует изначальная расстановка, при которой получится не меньше n попаданий в неправильную очередь. Допустим, все гномики выстроились в очередь к белому мудрецу, при этом сначала все чёрные. Если белый мудрец не перенаправит всех чёрных, он будет вынужден до этого поменяться колпаками с коллегой, после чего ему придётся перенаправить всех белых, то есть в любом случае минимум n.
Ответ: n.