Только ходы не правильно подсчитаны. На 15 ходу будет 47, 49, 59, 61. Так что минимум все-таки 33.
Проще всего решать, если считать, что каждый ход наперстки сдвигаются на 1. Например, если номер наперстка каждый ход уменьшается на 1, то мы можем утверждать, что монетка или не меняет свой номер, или уменьшает его на 2 (по модулю 100). Теперь, когда варианты не расползаются в обе стороны, следить за ними гораздо проще. То что наперстки меняют номера никак не отражается на задаче, мы можем это игнорировать.
Сразу видно, что варианты распадаются на 2 не связанных между собой части — 50 четных наперстков и 50 нечетных. Теперь посмотрим на сколько увеличивается число вариантов после того как мы своим ходом исключаем 4. Для каждого ряда идущих подряд вариантов в любой из частей число вариантов увеличивается на 1, если только этот ряд не включает все 50 наперстков этой части. Поэтому мы должны держать число таких рядов минимальным. Для этого, во-первых, не надо проверять обе части одновременно, надо сначала исключить все варианты в 1 части и только потом взяться за вторую. Во-вторых, проверяя каждую часть, надо держать множество непроверенных вариантов в виде одного непрерывного ряда, т. е. проверять варианты только с края или с краев этого ряда. Какой именно порядок проверки выбрать — не важно, лишь бы выполнялось это условие. Тогда каждый раз после переворачивания наперстков и перемещения монеты число вариантов будет уменьшаться на 3, кроме случая, когда мы перевернули 4 последних непроверенных наперстка в какой-то части. Для 100 наперстков это произойдет 1 раз — на последнем, 33, ходу.
В общем случае для N наперстков понадобиться (2N-1)/6 ходов с банковским округлением
