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

   Вы точно знаете, что в одной из 10000 пещер находится клад. Но вы не знаете в какой. Зато есть оракул, который  правдиво отвечает только на вопросы типа: «есть ли клад в 6704-ой  пещере». Очевидно, что за 9999 вопросов вы наверняка узнаете местонахождение клада. Существует ли устройство, которое может узнать номер искомой пещеры с  вероятностью не менее 50% за не более чем 250 обращений к оракулу?

веревка и расколенное железо у глаза оракула

14 вопросов и вероятность 100%

  Спрашивать можно лишь про одну пещеру за один раз.

за 250 обращений мы проверим только 250 пещер
с вероятностью 2.5% мы узнаем
с вероятностью 97.5% мы не узнаем
и это не зависит от устройства

думаю, есть какая-то ошибка в условии задачи (неточный перевод с английского?)

с этим вы согласны?

  Безусловно.

хорошо.  Следующий шаг.  согласны ли вы, что:

после 250 вопросов окажется:
с вероятностью 2.5% мы угадали где клад
с вероятностью 97.5% мы не угадали

  Если ничего другого не делается, тогда --- да. Но устройство может выполнять некие действия или вычисления.

хорошо.  следующий шаг.  согласны ли вы, что

в случае, если мы не угадали за 250 вопросов, то максимум, что можем сделать - ткнуть наугад в любую из оставшихся 9750 пещер
и вычисления тут не помогут - все эти 9750 вариантов равновероятны

итого вероятность угадывания с учётом обоих случаев = 2.51%


а какие действия может выполнять устройство?  :o

  Например, колесико покрутить внутри самого устройства.

:o

а вопросы "номер пещеры с кладом меньше 1987?" задавать нельзя?

ну и что?  :)
оставшиеся 9750 пещер всё равно останутся равновероятными


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


вы так и не сказали, согласны ли вы с моими рассуждениями
укажите ошибку в них или согласитесь, что правильный ответ равен 2.51% независимо от устройства

  Как раз задачка про это. Про квантовые эффекты и их применение.

очевидно, автор считает указание на ошибку очень весомой подсказкой

  Нет, нельзя. Спрашивать за один раз можно лишь за одну пещеру.

Камень Азарта  :yesgirl:

  А что это такое?

http://nazva.net/forum/index.php/topic,4428.msg88140.html#msg88140

Умник прав: переводим 10000 в двоичную систему счисления и спрашиваем Оракула о каждом знаке в отдельности. вуаля: 14 вопросов, и если "повар нам не врет" пещера наша :bye:

Смит, так низзя

кто сказал?  :read:  ???

это как с математиками, только так и никак иначе  :tianchik:

  За один раз можно спрашивать у оракула лишь про одну пещеру.

а больше/меньше?

  Ладно, так и быть. Можно спрашивать про нулевое количество пещер. :)

устройство - металлоискатель?

:o :o :o

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

Я не буду проходить по ссылке и читать, у меня вопрос: То есть Вы хотите сказать, что если что-то поделать (пусть даже на квантовом уровне) в каком-то аппарате, то вероятность нахождения клада в пещере (а его не перекладывают, он по-любому там) будет меняться?

:)

  Я могу лишь посоветовать поискать ссылки на квантовый алгоритм Гровера.

Значит вы ошиблись разделом ???

  Количество разделов ограничено, идеально подобрать раздел невозможно. Для доказательства эффективности алгоритма применяется математика.

Для данной задачи подойдет "Помогите решить"

  Не подходит.

Вы не можете объяснить решение - очень даже подходит.

   Я могу объяснить решение, но это займет много времени. Зачем это делать, если есть источники со всей информацией?

С разделом все в порядке. Можно название изменить, чтобы было понятно, о чем речь ;)

Мне не надо объяснять работу устройства. Я все равно не пойму :)
Я задал конкретный вопрос.

Um_nik, раздел менять нет смысла - на форуме всё равно нет раздела "знаю, но вам не скажу"  :)

нашёл какую-то формулу пи/4*корень(N), но по ней получается вовсе не 250
автор, хотя бы объясни, откуда такие числа взялись

   От того, что устройство вычисляет номер искомой пещеры, клад в другую пещеру не переместится (если, конечно, его за это время не выкопают). Вероятности найти клад в пещере равны 0 для всех кроме одной пещеры (в ней --- 1). Но мы не знаем этого номера. А вот вероятность того, что машина угадает превышает 50 %.


  На форуме также нет раздела "вы мне все расскажите, а я послушаю, кока-колу попивая, попкорном закусывая". Это вам к "двоим из ларца, одинаковы с лица" из мультфильма "Вовка в тридевятом царстве". Они все за вас сделают. :)
   пи/4*корень(10000) < 250. Поэтому 250 достаточно. В сети достаточно квалифицированной информации про квантовые алгоритмы. Дорогу осилит идущий.

Машина тыкает пальцем в небо, пусть она хоть 8 лет это "42" считает

думал, что ухудшение эффективности (увеличение числа попыток до 250) объясняется наличием более красивого или более простого решения для 250 вопросов
нет?

  Нет. По крайней мере я не знаю более красивого или более простого решения.