Question

Султан задумал натуральное число не болшее 15.Можно задавать Султану любой вопрос, на который можно ответить "да" или "нет".Доказать, что любое число можно угадать, не более чем за 4 вопроса.Показать, что 3 вопросов может не хватить.

Answer 1

Если каждый раз спрашивать больше ли задуманное число чем среднее из области возможных вариантов, то минимум нужно 4 вопроса. Например, если он всегда говорит да : 1 - больше 7?
2 - больше 11? 3 - больше 13? 4 - больше 14?

Answer 2

1. Нечет?

Да - 8 чисел.

Нет - 7 чисел.

Выбираем более маловероятный вариант - 8 чисел.

2. Больше 7?

Да - 4 числа.

Нет - 4 числа.

Выбор последующего вопроса равновероятен.

3. Больше 3?

Да - 2 варианта.

Нет - 2 варианта.

4. Одно из двух.

Решение, наиболее маловероятым вариантом, является доказательством, что можно угадать не более, чем за 4 вопроса.

Это же решение показывает, что 3 вопросов может не хватить.