ilyaraz's blog

By ilyaraz, 12 years ago, In Russian

Рассмотрим игру для двух игроков. Первый загадывает два числа от 1 до n. Второй пытается получить об этой паре максимальную информацию. Для этого он называется подмножества {1, 2, ..., n}, а первый сообщает про какое-то из своих чисел, лежит ли оно в этом множестве. Что скрывается под словосочетанием "максимальная информация", и за какое асимптотически минимальное количество вопросов ее можно узнать?

  • Vote: I like it
  • +32
  • Vote: I do not like it