Игра "Угадай число" как процесс получения информации.

 Попробуем сыграть в игру "Угадай число"

Правила игры -

• Соперник загадывает некоторое число X  от 1 до N (8, 10, 100, 1000, 1 000 000). Число N известно Игроку
• Игрок задает вопрос, на который Соперник отвечает Да или Нет
• Игра заканчивается, когда игрок называет загаданное число не задавая вопроса

Пример протокола игры (при N = 4)

• Игрок - "Это число равно 1"   Соперник "Нет"
• Игрок - "Это число равно 2"   Соперник "Нет"
• Игрок - "Это число равно 3"   Соперник "Нет"
•  Игрок - "Загадано число 4"
  игра завершилась и Игрок задал три вопроса

"Угадать число", значит получить информацию о неизвестном. Эта информация содержится в вопросе и ответе на него.
Сформулируем проблемы:

1.  В чём можно измерять количество информации?
2.  Какая оптимальная стратегия должна быть, чтобы узнать число за наименьшее число вопросов?
3. Возможно ли сделать стратегию стандартной? Можно ли её "масштабировать"
4. Какие свойства информации можно понять на примере этой игры?

 
 

1. Угадать число, значит понять каким набором гирь его можно взвесить.
Пусть N = 1000. Чтобы взвесить число до 1000 можно взять "эффективный набор" из 10 гирь {512, 256,128, 64, 32, 16, 8, 4, 2, 1}
При взевшенивании, первой на весы ставим гирю 512. Переведем "результат" взвешивания в вопрос

• Ваше число БОЛЬШЕ 511?
  • Ответ ДА означает, что гиря 512  должна остаться на весах
  • Ответ НЕТ означает, что гиря 512  должна быть убрана с весах
• Второй вопрос может  быть сформули одним из двух способов
  • Ваше число БОЛЬШЕ 767? - это если ответ на 1 вопрос был ДА
  • Ваше число БОЛЬШЕ 255? - это если ответ на 1 вопрос был НЕТ

​​​​​​​​​​​​​​и так далее. В результате, за десять вопросов, число будет угадано.
Может показаться, что будет лучше использовать в первом вопросе число 500 или задавать вопросы со словом РАВНО. Это обманчивое желание, поскольку, если наш Соперник "жульничает" (то есть может менять число, но так, чтобы ответы были правдивые) то быстрее чем за десят вопросов угадать не получится (10 вопросов потребуется и для N = 513).
Указанным набором можно за десять вопросов угадать число от 1 до 1024, поэтому набор гирь из степеней 2 будет оптимальным.

Можно считать, что минимальное количество вопрсов, которое необходимо задать для угадывания числа от 1 до N есть количество информации, которую надо получить. Получение информации с помощью вопросов ДА/НЕТ сопровождается уменьшением количества вариантов не менее, чем в два раза и считается, что при вопросах такого типа получается 1 бит информации

При угадывании числа от 1 до 1000 потребовалось 10 вопросов потому, что 2⁹ = 512  < 1000 <=  1024 = 2¹⁰ 
А сколько вопросов потребуется для угадывания числа от 1 до 1 000 000?
Почему? 
Как организовать стратегию угадывания? (Подумайте, как бы организовали взвешивание груза весом не более тонны с точностью до 1 грамма)

Попробуем сформулировать вопросы про свойства количества информации на основе результатов исследования игры "Угдай число"
Обозначим минимальное количество вопросов для угадывания числа от 1 до N как I(N)

1. Чему равно I(1)?
2. Известно, что N₁ < N₂.  Что можно сказать про I(N₁) и I(N₂)?
3. Что можно сказать про  I(N₁*N₂)  и I(N₁), I(N₂)?
4. Знаете ли функцию, удовлетворяющую результатам ответов на 1-3 (это 10-11 классов)