Question

Мистер Фокс и мистер Форд играют в такую игру. Мистер Фокс загадывает число от 1 до 127 (включительно). Мистер Форд может задать несколько вопросов, на каждый из которых можно ответить да или нет. Все вопросы задаются одновременно (например, записываются на бумаге), все ответы даются одновременно. Каким наименьшим количеством вопросов мистер Форд может гарантированно обойтись, чтобы наверняка узнать загаданное число?

Answer 1

1 - 127 == 128 чисел

128 / 2 == 64  - 1

64 / 2 == 32   -2

32 / 2 == 16  -3

16 / 2 == 8   -4

8 / 2 == 4   - 5

4 / 2 == 2    - 6

2 / 2 == 1     - 7

7 вопросов

Answer 2

Мистер Форд может гарантировать угадать загаданное число с помощью 7 вопросов.

Для решения этой задачи можно использовать двоичное представление числа от 1 до 127. В двоичном представлении каждое число от 1 до 127 может быть записано с помощью 7 бит:

1 = 0000001 2 = 0000010 3 = 0000011 4 = 0000100 5 = 0000101 6 = 0000110 ... 127 = 1111111

Мистер Форд может задавать вопросы о каждом бите загаданного числа. Например, он может задать первый вопрос: "В первом бите вашего числа стоит 1?". Если мистер Фокс ответит "да", то загаданное число должно быть больше или равно 64 (так как первый бит равен 1). Затем мистер Форд может задать второй вопрос: "Во втором бите вашего числа стоит 1?" и так далее для всех 7 бит.

Всего у мистера Форда есть 7 бит, каждый из которых может принимать значение 0 или 1, поэтому всего возможно 2^7 = 128 различных комбинаций вопросов. Однако, чтобы гарантировать угадывание числа, нужно исключить одну комбинацию вопросов, которая может привести к неправильному ответу. Это комбинация вопросов, которая не уточняет один бит загаданного числа. Например, если мистер Форд задаст вопросы только о первых 6 битах загаданного числа, то мистер Фокс может загадать число, которое отличается от любого из предложенных вариантов только последним битом. Поэтому, чтобы гарантировать правильный ответ, мистер Форд должен задать вопросы обо всех 7 битах.

Таким образом, мистер Форд может гарантировать угадывание числа с помощью 7 вопросов.