Форум умных людей

По кругу расположены 100 напёрстков. Под одним из них спрятана монетка. За один ход разрешается перевернуть четыре наперстка и проверить, лежит ли под одним из них монетка. После этого их возвращают в исходное положение, а монетка перемещается под один из соседних с ней напёрстков. За какое наименьшее число ходов наверняка удастся обнаружить монетку?

Но можно и меньше.

и действительно, Показать скрытый текст

Можно еще меньше.

ну, тогда Показать скрытый текст
сомневаюсь, что можно быстрее

А вот есть доказательство, что можно!

доказательство - в смысле, стратегия?

Да, именно.

25 ходов. что то не припомню как залить картинку на форум? может подскажет кто)

Хорошо, но много.

Это как? Расскажите способ.
А картинки можно тут заливать.
http://www.radikal.ru/ и http://savepic.org/

(http://s019.radikal.ru/i601/1205/df/ba32daef28d8.jpg)

ошибочка ) в рисунке: справа фиолетовая стрелка на один наперсток вверх по кругу. деление в столбик это для смеха, конечно,) на самом деле все проверено мной на листке) хотя гарантий нет

С сотней ходов можно даже по 4 колпачка не переворачивать, а всегда вертеть один и тот же

Очень хотелось бы подождать пока Вы вспомните, но т.к. врядли
Сначала на любой сторонний сайт, большинство пользует
http://www.radikal.ru/
потом уже
---------------------------------
(http://ссылка)
---------------------------------
Т.к. коды активные написать в постинге это нереально. Лучше нажмите над моим сообщение надпись цитировать и рассмотрите отчеркнутую сверху-снизу строку

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

ну так как мой вариант?

Вариант интересный, но не совпадает с авторским. Желаете на него взглянуть?

В. Дольников XXXV Всероссийская олимпиада  ???
А посмотреть не удаётся :girlcry: :girlcry: :girlcry:
 :whiteflag: :whiteflag:

Не беспокойтесь, скоро покажу.

вот я, например, ничего не понял из рисунка мозгоколлапса
реквестирую формальное описание

Наконецто удалось добраться
Здесь в принципе именно аффтарский атвет
Получается 25 от коллапса+ проверка после каждого хода для вылавливания переползающей монетки - итого = 34
Показать скрытый текст
На фсякий случай первоисточник
http://www.postupivuz.ru/vopros/154.htm

)))))))))

Извините моё занудство. Здесь задача тоже решается так, словно монета поступательно движется по кругу, а ведь в условии оговаривается только, что монета перемещается под один из соседних с ней наперстков. То есть, пока мы открываем последовательно все напёрстки, она могла путешествовать туда-сюда, в любой момент имея возможность избежать погони.
К примеру, открываем 1-4 напёрстки, а монетка в это время под пятым. Дальше открываются 5-8, а монетка уже ускользнула под четвёртый. Или так: открыли 97-100 напёрстки, после чего монетка из-под первого переходит под сотый, а дальше уже движется потихонечку следом за нами.

Или я в чём-то не права?

Тот же вопрос почему и сунул линк - я там не регился

А вот решение, которое мне удалось накропать.
Показать скрытый текст

Погодите, если представить эту ситуацию, то, мне кажется, монетка после перемещения не может оказаться под нечётными напёрстками 1, 3, 5, поскольку соседние с ними напёрстки 0, 2, 4, 6 были пустыми. Почему же, находясь, к примеру, сначала под первым напёрстком (мы его не поднимали и монетку не видели), она не может переместиться под второй?
Что-то тут не так!
Сдаётся мне, что разгадка - это секрет напёрсточников, который они ни за что не выдадут.

Похоже, в решении хде-то опечатка. Видимо, должно быть так.
Показать скрытый текст

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

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

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

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

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

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

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

(http://i020.radikal.ru/1205/e0/14558ddec5e5.jpg)
Пожалуйста, просто посмотрите) если в этой схеме и правда что-то не так, я очень хочу узнать, потому что просто не вижу другого решения. Цифрами обозначены ходы (симметрично с двух сторон, за один ход открывается 4 наперстка)

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

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

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

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

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

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

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

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

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

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

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

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

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

Да-да-да! Спасибо за пояснение, всё правильно. Поняла.
 :bravo:

Только ходы не правильно подсчитаны. На 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 ходов с банковским округлением :)

правильно  :bravo2:

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

Спасибо, ребята, всё стало ясно с этими напёрстками.

Настасья, в том и дело, что Димыч считает, что за 33 хода, а я пытаюсь показать, что за можно и за 32.. только нет времени щас расписывать, может, через часик..

нет, 32 не получается, 16 ход 50/52/56/58, а 17 - 53/54/55. если не поймали - тогда с 16 к 1 в обратной последовательности, итого - 33 хода :good:

25 ходов - только после открытия наперстки больше не трогать - профилактика переползаний.

я не понял  :tormoz:

Перевернуть и пускай так и лежит, а кто поползет - тапком

кстати, поставлю спасибку тому, кто укажет 17 ход исходя из первого (1) указанного - 1/3/5/7 и шестнадцатого 50/52/56/58  :-*

ой, я с тапкам намаялся та уж.....  :yesgirl:

Оффтопик- другое искал, а тут попалось такое
(http://votrube.ru/uploads/posts/2011-09/1316034882_-(www.votrube.ru)1.jpg)