Процессы и алгоритмы

Докажем, что меньшего количества ходов может не хватить. Положим первую монету решкой вверх, вторую — орлом вверх, третью — снова решкой вверх, и так далее. Предположим, что в такой ситуации нам хватит меньше ходов. Заметим, что каждая пара соседних монет имеет один из типов: либо они лежат одинаково, либо по-разному, причем мы также считаем парами границы ряда (то есть между крайними монетами и концами, границы считаем решками). Заметим, что за один ход мы меняем тип ровно пар. С другой стороны пар второго типа у нас изначально ровно для четных и для нечетных Тогда нам потребуется хотя бы ходов.

Осталось показать, что такого количества ходов нам всегда хватит. Разобьем монеты на блоки подряд идущих, повернутых одинаково (сначала блок орлов, потом решек, затем снова орлов и так далее, или наоборот). Заметим, что блоков каждого типа не больше (иначе некоторые два одинаково повернутых блока стояли подряд). Тогда можно перевернуть все блоки, которые повернуты решкой вверх.