Игра в наперстки

[Nastasiya]

Показать скрытый текст

Возможно. Однако, наверное, второй круг следует начинать с третьего, а не пятого напёрстка.  Потому что в противном случае монетка может переместиться из-под второго под третий напёрсток. И мы её потеряем. Или нет?

[Nastasiya]

Показать скрытый текст

Вот беда, уснуть не могу из-за этих напёрстков!

И пришло мне в голову, что эпопея с поисками должна закончиться быстрее, задолго до конца второго круга.
Ведь смотрите, в ходе движения по первому кругу мы тотально проверяем все напёрстки: чётные открываем, а нечётные пропускаем только таким образом, что под ними не может находиться монетка. Если до конца первого круга (а Вы посчитали, что мы сделали 17 ходов) монета не обнаружилась, значит, она изначально находилась где-то в конце круга и успела перейти на второй круг. Нулевой (сотый) напёрсток мы проверяли, отсюда следует что в самой неблагоприятной для поиска ситуации она могла сначала лежать под 99-м напёрстком, а потом пошла вперёд, чтобы мы подольше её не нашли. Через 17 ходов она оказалась под 16-м напёрстком. Теперь, учитывая, что мы тотально проверяем напёрстки и движемся семимильными шагами, нам остаётся только догнать беглянку.
Итак, после проверки напёрстков 98, 0, 1, 3 открываем дальше: 3-5-7-9, 9-11-13-15, 15-17-19-21. Достаточно. Ведь через эти три хода монета, если не обнаружится раньше, будет лежать под 19-м напёрстком.

[BrainCollapsis]

Sirion вы кажется просили разъяснения в тексте. Я например после прочтения предложенных решений никак не могу понять ни авторскую версию, ни ее производные. зачем же так усложнять
Моя тактика нахождения монетки направлена на то, чтобы окружить ее (монетку) вернее, загнать в одну точку и при этом не запутаться (так как пронумеровать сто одинаковых наперстков стоящих вкруг и не запутаться очень даже сложно.)

Переворачиваем любые рядом стоящие четыре наперстка. монеты нет. первый ход сделан.
Мы предполагаем теперь что монетка могла быть в одном из соседних наперстков, которые мы не открыли, значит вторым ходом мы открываем по два смежных наперстка с каждой стороны, два наперстка, которые мы открывали в первом туре (для профилактики перемещений монеты) и два новых (по другу сторону от закрытых наперстков.) это второй ход, и по аналогии так открываем дальше.
Этим мы добиваемся того, что ровно за 25 ходов мы посмотрим все наперстки и при этом будем контролировать те, что открывали на шаг назад, чтобы монета не проскочила. То есть образно говоря ходы "наслаиваются один на другой" чтобы все это проделать нужно 25 ходов.
Это я так понимаю наименьшее значение попыток, удовлетворяет условиям, так может автор ошибся?

[Димыч]

Думаю, fortpost в своем решении забыл написать, что надо циклически сдвигать нумерацию каждый ход. Тогда первое решение работает.

[Nastasiya]

Моя тактика нахождения монетки направлена на то, чтобы окружить ее (монетку) вернее, загнать в одну точку и при этом не запутаться (так как пронумеровать сто одинаковых наперстков стоящих вкруг и не запутаться очень даже сложно.)

Переворачиваем любые рядом стоящие четыре наперстка. монеты нет. первый ход сделан.
Мы предполагаем теперь что монетка могла быть в одном из соседних наперстков, которые мы не открыли, значит вторым ходом мы открываем по два смежных наперстка с каждой стороны, два наперстка, которые мы открывали в первом туре (для профилактики перемещений монеты) и два новых (по другу сторону от закрытых наперстков.) это второй ход, и по аналогии так открываем дальше.
Этим мы добиваемся того, что ровно за 25 ходов мы посмотрим все наперстки и при этом будем контролировать те, что открывали на шаг назад, чтобы монета не проскочила. То есть образно говоря ходы "наслаиваются один на другой" чтобы все это проделать нужно 25 ходов.
Это я так понимаю наименьшее значение попыток, удовлетворяет условиям, так может автор ошибся?

Ваша тактика очень надёжна, но насчёт 25 ходов, думается, Вы ошибаетесь.

Ведь, чтобы загнать в угол монетку, требуется открыть по 50 напёрстков с каждой стороны. Первым ходом мы открываем по 2, а каждый последующий ход добавляет только по одному напёрстку.  Вы и сами это пишете: два наперстка, которые мы открывали в первом туре (для профилактики перемещений монеты) и два новых, т.е. как раз по одному новому с каждой стороны.

А на схеме Вы почему-то нарисовали по обеим сторонам по два вновь открываемых напёрстка, и тут дело у Вас, конечно, быстро пошло. Но фактически-то в этом случае одновременно просматриваются 6 напёрстков, что, противоречит условию.
Поэтому, соблюдая установленное число - четыре напёрстка, для того, чтобы открыть их все Вам потребуется не 25, а 49 ходов, то есть, столько же, сколько и у меня в первом решении.

Получается, что наши с вами методы не имеют принципиальных отличий, но они не оптимальны.

[BrainCollapsis]

Пожалуйста, просто посмотрите) если в этой схеме и правда что-то не так, я очень хочу узнать, потому что просто не вижу другого решения. Цифрами обозначены ходы (симметрично с двух сторон, за один ход открывается 4 наперстка)

[Nastasiya]

Спасибо. Сейчас Ваше решение стало понятно: действительно, каждый раз открываются одновременно 4 напёрстка.
Очень хотелось бы с Вами согласиться, но, боюсь, что такой способ поиска всё же имеет слабые места.

Вот, к примеру, первым ходом открыты напёрстки, условно, № 1 и № 2 с левой и правой стороны. А монетка в это время находится под напёрстком № 4 (неважно - слева или справа). После этого открываем н-ки № 2 и № 4, а монетка уже переместилась под № 3. Следующим ходом идём дальше: № 4 и № 6, а монетка укатилась под № 2. Всё, мы её потеряли.
И так может получиться на любом этапе изображённой цепи. Достаточно монетке находиться через один напёрсток от последнего, открытого нами на n-ном ходу.
Согласны?

[BrainCollapsis]

Думаю Вы правы) решение неверное) спасибо за Вашу внимательность)

[Nastasiya]

И Вам спасибо.  Интересно было поломать голову. Хотя 100%-но верный ответ так и остался неизвестным.

[Blazzy]

Показать скрытый текст

Открываем подряд 4 первых напёрстка, потом три новых (четвёртый страховочный) подряд и т.д. За каждый ход – 3 новых. 100/3 = 33+1. За 33 хода наверняка будем знать где монетка..
123 456 789 …

[Nastasiya]

Не чувствую больше душевных сил говорить про напёрстки, и всё-таки - не могу молчать.
Лёлик, Вы не обратили внимание, что напёрстки расположены по кругу, поэтому Ваши надежды утопичны.
Увы!

[Димыч]

Судя по тому, что никто не обратил внимания на мой комментарий, никто его не понял. Выкладывать подробное решение?

[Smith]

Показать скрытый текст

http://nazva.net/forum/index.php/topic,297.msg1728.html#msg1728

зы: мой вариант - 31, если (как обычно) уж очень сильно невезет.. 

например: 1 3 5 7, 8 10 98 100, 11 13 95 97 и т.д. (итого 15), затем - контрольный для смены четности (1) и в обратную сторону снова (15).

[Nastasiya]

зы: мой вариант - 31, если (как обычно) уж очень сильно невезет.. 

Прошу прощения, если не права, но я бы перефразировала так: 31, если повезёт, и монетка окажется под каким-то из тех напёрстков, которые открыты.
Ведь задача, на которую Вы ссылаетесь, - совсем иная. Принципиальное отличие в том, что монетка здесь может перемещаться по кругу. Но зато и проверить можно сразу 4 объекта, а не один, как в той задачке.
Или я в чём-то ошибаюсь?

Думаю, fortpost в своем решении забыл написать, что надо циклически сдвигать нумерацию каждый ход. Тогда первое решение работает.

Мне решение Fortpost'а понравилось и показалось реальным, за исключением нюансов, о которых уже писала.
Вы хотите его оптимизировать? Очень интересно!

Судя по тому, что никто не обратил внимания на мой комментарий, никто его не понял. Выкладывать подробное решение?

Обязательно напишите!

[Smith]

Прошу прощения, если не права, но я бы перефразировала так: 31, если повезёт, и монетка окажется под каким-то из тех напёрстков, которые открыты.
Ведь задача, на которую Вы ссылаетесь, - совсем иная. Принципиальное отличие в том, что монетка здесь может перемещаться по кругу. Но зато и проверить можно сразу 4 объекта, а не один, как в той задачке.
Или я в чём-то ошибаюсь?

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