Рассмотрим игру для двух игроков. Первый загадывает два числа от 1 до n. Второй пытается получить об этой паре максимальную информацию. Для этого он называется подмножества {1, 2, ..., n}, а первый сообщает про какое-то из своих чисел, лежит ли оно в этом множестве. Что скрывается под словосочетанием "максимальная информация", и за какое асимптотически минимальное количество вопросов ее можно узнать?
Я подозреваю, что максимальная информация — узнать одно число. Поскольку если первый игрок захочет, то он всегда будет отвечать по первому числу, и про второе ничего не будет известно никогда.
Не всегда даже можно узнать одно число. См. ответ Егора ниже.
Понял косяк
Да, на второй итерации уже не сработает.
Предлагаю такую стратегию за первого: пусть второй спрашивает множество A. Если мощность пересечения A и {1, 2, 3} по крайней мере два, то говорим "да", иначе говорим "нет".
Ответ на первый вопрос — узнать 1 число или тройку чисел, в которые наши 2 входят
Вроде бы умею за квадрат, но вряд ли это оптимально
А как за квадрат?
Пусть загаданы числа А и В. Перебираем все пары чисел. Второй игрок на паре (А,В) скажет что число лежит. Так же второй игрок выберет некоторое число С отличное от А и В. И на парах (А,С) и (В,С) тоже кажат что принадлежит. на всех остальных ответит нет. Мы находит троику (А,В,С). Если вротой игрок будет отвечать как то подругому то выдаст числа
Проверить все пары. Посмотрим все, на что он ответил да. Если там есть две непересекающиеся пары (a, b), (c, d). В каждой из этих пар по загаданному числу. Если на обе (a, c) и (b, d) он ответил да, то ответ либо (a, d), либо (b, c), а точнее — тот из них, на который он ответил да. На обе нет он не мог ответить. Пусть он ответил да на (a, c). По аналогичным соображением он ответит да на (a, d) или (b, c). Все еще без ограничения общности пусть (a, d). Тогда a — точно выбрано, победа.
Пусть любые 2 пары имеют общую вершину. Заметим, что если число входит не менее, чем в 3 пары, на которые ответ да, то оно выбрано. Если ответов да больше 3, то такое число есть. Если 3 — то либо есть такое число, либо у нас пары (a, b), (a, c) и (b, c) и тогда оба выбранных в этих парах. Если ответ да один, то это пара выбранных чисел. Если 2, то опять же пересечение точно выбрано
Я придумал что-то похожее(а может и тоже самое). Найдем пару (a,b), на которой он скажет "Да". Достоверно известно, что в этой паре либо a либо b будет одним из загаданных чисел. Далее проверим все пары чисел вида (a,x), где x любое число, кроме b. 1)Если он скажет больше одного раза "Да", то a это ответ, так как если это не ответ,то ответ b и среди всех чисел кроме b может быть только одно, которое он загадал. 2)Если он ни разу не скажет да, то это значит, что a не загаданное число, так как если бы это было загаданное, то нашлась бы пара, на которой он обязательно сказал бы "Да". 3)Если же он скажет один раз "Да"- то мы нашли тройку чисел, в которых есть оба загаданных числа. В 1) отбрасываем b и начинаем искать заново в 2) отбрасываем a и начинаем искать заново
один из тегов намекает, что можно делать бинпоиск по длине сабсета. при фиксированой длине d спрашивать о {1,...,d}, {2,...,d+1}, ..., {n-d+1,..., n}. но наверно лажа, из-за неопределённости числа при ответе
И что нам это даст?
Такая задача была на киевской городской олимпиаде. http://kievoi.narod.ru/3/2012.html (6 задача). Разбор лежит где-то там же сайте.
А можете разбор найти? А то я украинский, увы, не знаю.
http://kievoi.narod.ru/index1.html Рекомендації щодо розв'язання завдань відбірково-тренувальних зборів... файл под номером 29. Но разбор там тоже по украински.
Можно и за линию. Называю все числа от 1 до n, а первый игрок говорит лежит число или нет.
Он может отвечать всегда "**нет**" (про другое число).
Искренне ваш кэп.
Неправда, он может всегда "нет" говорить, если загаданные числа различны.
Я правильно понимаю, что задачу можно переформулировать в виде: "Дана булева функция n переменных, монотонная по двум переменным, за сколько измерений можно найти эти переменные?"
UPD: нет, не совсем, нужно требование, что на наборе (...0...0..) функция принимает именно 0, а это не следует из монотонности.
Опишу разбор задачи с Киевской городской олимпиады школьников.
Пусть у нас есть 4 разных числа: a, b, c, d. Будем говорить, что множество Q натуральніх чисел разделяет пары {_a_, b} и {_c_, d}, если оба элемента одной пары принадлежат Q, а оба элемента второй пары -- не принадлежат. Будем говорить, что набор множеств Q1, Q2, ..., Qn разделяет пары {_a_, b} и {_c_, d}, если эти пары разделяет хотя бы одно из множеств Q1, Q2, ..., Qn.
Выберем случайное множество чисел Q, элементами которого есть натуральные числа от 1 до N. Несложно показать, что вероятность того что это множество не разделяет данные 2 пары равна
. Выберем независимо случайным образом t подмножеств множества {_1_, 2, ..., N}. Ограничим сверху вероятность того, что эта система не разделяет какие-то 2 неупорядоченных пары. Имеем:
P{система не разделяет какие-то 2 пары} =
P{система не разделяет 2 конкретные пары} < 
.
Павую часть этого неравенства можно сделать меньшей, чем любое наперед заданное положительное число ε, выбрав t следующим образом:
Покажем, что получив ответы на вопросы про множества {Qi}, которые разделяют любую пару двухэлементных множеств чисел, мы можем либо указать одно число, которое было загадано, либо три числа среди которых есть 2 загаданных.
Пусть S -- множество неупорядоченных пар потенциальных загаданных чисел, которые могли бы привести к тем же ответам, что и Q1, Q2, ..., Qt. Любые 2 множества из S имеют непустое пересечение, поскольку иначе какое-то из множеств Qi разделило бы 2 пары и последовательности ответов отличались бы. Имеем:
Математическое ожидание количества вопросов равно
для любого наперед заданного ε.
Для специалистов дополнительный вопрос: как найти Qi за полиномиальное время детерминированным алгоритмом?
А стандартный метод "возьмем ГПСЧ вида a^i mod p с периодом ~ 3/2 требуемого числа запросов для достаточно маленького eps" и докажем какую-нибудь экспоненциальную сумму не покатит? :)
Не знаю, надо думать.