Я подозреваю, что максимальная информация — узнать одно число. Поскольку если первый игрок захочет, то он всегда будет отвечать по первому числу, и про второе ничего не будет известно никогда.

Ответ на первый вопрос — узнать 1 число или тройку чисел, в которые наши 2 входят

Вроде бы умею за квадрат, но вряд ли это оптимально

один из тегов намекает, что можно делать бинпоиск по длине сабсета. при фиксированой длине d спрашивать о {1,...,d}, {2,...,d+1}, ..., {n-d+1,..., n}. но наверно лажа, из-за неопределённости числа при ответе

Такая задача была на киевской городской олимпиаде. http://kievoi.narod.ru/3/2012.html (6 задача). Разбор лежит где-то там же сайте.

Можно и за линию. Называю все числа от 1 до n, а первый игрок говорит лежит число или нет.

Я правильно понимаю, что задачу можно переформулировать в виде: "Дана булева функция n переменных, монотонная по двум переменным, за сколько измерений можно найти эти переменные?"

UPD: нет, не совсем, нужно требование, что на наборе (...0...0..) функция принимает именно 0, а это не следует из монотонности.

Опишу разбор задачи с Киевской городской олимпиады школьников.

Пусть у нас есть 4 разных числа: a, b, c, d. Будем говорить, что множество Q натуральніх чисел разделяет пары {_a_, b} и {_c_, d}, если оба элемента одной пары принадлежат Q, а оба элемента второй пары -- не принадлежат. Будем говорить, что набор множеств Q₁, Q₂, ..., Q_n разделяет пары {_a_, b} и {_c_, d}, если эти пары разделяет хотя бы одно из множеств Q₁, Q₂, ..., Q_n.

Выберем случайное множество чисел Q, элементами которого есть натуральные числа от 1 до N. Несложно показать, что вероятность того что это множество не разделяет данные 2 пары равна . Выберем независимо случайным образом t подмножеств множества {_1_, 2, ..., N}. Ограничим сверху вероятность того, что эта система не разделяет какие-то 2 неупорядоченных пары. Имеем:

P{система не разделяет какие-то 2 пары} = P{система не разделяет 2 конкретные пары} < .

Павую часть этого неравенства можно сделать меньшей, чем любое наперед заданное положительное число ε, выбрав t следующим образом:

.

Покажем, что получив ответы на вопросы про множества {Q_i}, которые разделяют любую пару двухэлементных множеств чисел, мы можем либо указать одно число, которое было загадано, либо три числа среди которых есть 2 загаданных.

Пусть S -- множество неупорядоченных пар потенциальных загаданных чисел, которые могли бы привести к тем же ответам, что и Q₁, Q₂, ..., Q_t. Любые 2 множества из S имеют непустое пересечение, поскольку иначе какое-то из множеств Q_i разделило бы 2 пары и последовательности ответов отличались бы. Имеем:

1. Если существует элемент a, который принадлежит всем множествам из S, то ответ -- {_a_}.
2. Рассмотрим любые 2 пары из S: {_a_, b} и {_a_, c}. В соответствии с предположением, не все пары в S содержат элемент a. Значит, найдется еще пара, которая не содержит a. Как и все остальные пары из S, она имеет общие элементы с выбранными двумя парами. Но такой парой может быть только {_b_, c}. Если бы в S существовала еще одна пара, отличная от выбранных трех, то она бы не имела общих элементов хотя бы с одной из них, а такое невозможно. Следовательно, ответом будет множество {_a_, b, c}.

Математическое ожидание количества вопросов равно для любого наперед заданного ε.