|
|
 |
Условие
По кругу стоят 100 напёрстков. Под одним из них спрятана монетка. За один ход разрешается перевернуть четыре напёрстка и проверить, лежит ли под одним из них монетка. После этого их возвращают в исходное положение, а монетка перемещается под один из соседних с ней напёрстков. За какое наименьшее число ходов наверняка удастся обнаружить монетку?
Решение
После каждого нашего хода и перемещения монетки будем поворачивать все напёрстки (вместе с монеткой) по ходу часовой стрелки на одну позицию.
Тогда можно считать, что после каждого хода монетка либо остаётся на месте, либо перемещается на две позиции по часовой стрелке.
Пронумеруем все наперстки против часовой стрелки по порядку числами от 0 до 99. Понятно, что чётность номера наперстка, под которым лежит монетка, не изменяется. Назовём напёрсток пустым, если под ним в данный момент монетки быть не может (вначале пустых напёрстков нет). Очевидно, что после каждого нашего хода количество пустых напёрстков увеличивается не более чем на 4. Заметим, что если после нашего хода пустых напёрстков с номерами какой-то чётности не 0 и не 50, то найдётся пустой напёрсток с номером этой же чётности, через один от которого (против часовой стрелки) находится непустой напёрсток, а значит, после перемещения монетки этот напёрсток также становится непустым. Ясно, что в процессе поиска могло встретиться лишь две ситуации, в которых количество пустых напёрстков не увеличивается: первая – когда 50 напёрстков с номерами одной чётности пустые, а 50 другой чётности – все непустые (можно считать, что такая ситуация встречалась лишь один раз!), и вторая – конечная ситуация, когда пусты все наперстки. После каждого из остальных ходов и перемещения монетки количество пустых напёрстков увеличивается, но не более чем на 3.
Оценка. Пусть сделано не более чем 32 хода, но монетка еще не найдена. Тогда пустых напёрстков к этому моменту не более чем 30·3 + 2·4 = 98, значит, есть ещё не менее двух наперстков, под которыми может быть монетка. Поэтому поиск не закончен. Значит, требуется не меньше 33 ходов.
Алгоритм. Поднимем напёрстки с номерами 0, 2, 4, 6. Если монетки под ними нет, то после перемещения она не может оказаться под напёрстками 0, 2, 4, так как все их соседи были пустыми. (Далее мы всегда будем предполагать, что очередным ходом мы не нашли монетку – в противном случае всё уже сделано.)
Пусть после некоторого хода (и последующего перемещения монетки) у нас оказались пустыми напёрстки с номерами 0, 2, 4, ..., 2s. Тогда следующим ходом мы поднимем напёрстки с номерами 2s + 2, 2s + 4, 2s + 6, 2s + 8; после перемещения монетка не сможет оказаться под напёрстками с номерами 0, 2, 4, ..., 2s + 6. Таким образом, количество пустых напёрстков увеличилось на 3.
Итак, после 16 ходов 16·3 = 48 чётных напёрстков окажутся пустыми. Семнадцатым ходом мы проверим оставшиеся два чётных наперстка: 98 и 100, а также два нечётных: с номерами 1 и 3. После этого хода (до перемещения монетки) все чётные наперстки будут пусты и, следовательно,
останутся пустыми до конца.
Далее мы действуем по той же схеме. После 17-го хода и перемещения монетки остался пустым один нечётный наперсток; значит, после еще 15 ходов будут пустыми 1 + 3·15 = 46 нечётных наперстков (и все чётные). Тогда последним, 33-м ходом, мы можем проверить оставшиеся четыре напёрстка и гарантированно найдём монетку (если, конечно, мы не нашли её до того).
