1. Главная
  2. Библиотека
  3. Логика
  4. В ШАД 40 аудиторий, в одной вы забыли ключи от дома. Ох...
Разбор задачи

В ШАД 40 аудиторий, в одной вы забыли ключи от дома. Охранник Молчунов точно знает, где именно, но он сидит в звукоизолированной комнате. Вы можете послать ему несколько записок с вопросами, требующими ответа "да" или "нет". Охранник вытаскивает записки

  • Предмет: Логика
  • Автор: Кэмп
  • #Теория алгоритмов
  • #Логика программирования
В ШАД 40 аудиторий, в одной вы забыли ключи от дома. Охранник Молчунов точно знает, где именно, но он сидит в звукоизолированной комнате. Вы можете послать ему несколько записок с вопросами, требующими ответа "да" или "нет". Охранник вытаскивает записки

Условие:

В ШАД 40 аудиторий, в одной вы забыли ключи от дома. Охранник Молчунов точно знает, где именно, но он сидит в звукоизолированной комнате. Вы можете послать ему несколько записок с вопросами, требующими ответа "да" или "нет". Охранник вытаскивает записки из пачки в произвольном порядке, и, честно кивает вам или крутит головой сквозь стекло, отвечая тем самым на текущий вопрос. Если вы все еще не знаете, где ключи, можете послать еще одну серию записок на тех же условиях (но только один раз). Какое наименьшее число записок нужно послать, чтобы наверняка узнать, где ключи?

Решение:

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

Ниже пошаговое рассуждение:

──────────────

  1. Особенности условий задачи

    • Ключи находятся в одной из 40 аудиторий.
    • Охранник знает место, но отвечает на записки с вопросами, требующими “да” или “нет”.
    • В каждом раунде мы выдаём пачку записок, а охранник отвечает честно, но выдаёт ответы в произвольно...

Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит

Попробуй решить по шагам

Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение

Какое свойство ответов охранника является ключевым для понимания стратегии решения задачи?

Что нужно знать по теме:

Что нужно знать по теме

Алгоритм решения

Топ 3 ошибок

Что спросит препод

Не нашел нужную задачу?

Воспользуйся поиском

Выбери предмет