Тест теста

[Инна]

Задача довольно практичная.
Есть тест из N вопросов, подразумевающих бинарный ответ: да или нет.
Петя изначально не знает правильный ответ ни на один из вопросов.
После К попыток (при каждой попытке ему сообщается результат - число правильных ответов из N) Петя должен ответить верно на все вопросы.
Надо найти минимальную оценку К(N).
Например, заведомо достаточно К=N+1:
При первой попытке ответить на все вопросы нет, а потом отвечать на единственный вопрос - да по очереди для всех вопросов.
Насколько можно улучшить эту оценку?

[Юляша]

Ну, сразу ясно, что хватит K=N.

В приведенном в задании алгоритме последнее испытание лишнее - мы и до этого уже знаем правильный ответ на последний вопрос.

Ну и уточнение по заданию:
Петя может управлять своими ответами в зависимости от результатов теста? Или он должен представить универсальный алгоритм на К попыток?

[Инна]

Да, то что на 1 можно уменьшить - правильно.
Тактика может зависеть от результатов предыдущих тестов.

[Dendr]

Ну, начнем с того, что после первого теста теста мы можем узнать, сколько правильных ответов "да", а сколько, соответственно, "нет". Ответим в первый раз на все вопросы "да", получим на выходе число n. Очевидно, что n - число ответов "да", тогда N-n - ответов "нет".

Второй тест теста - на m вопросов произвольно мы даем "да", на остальные - "нет".
Пусть далее из них х (этого числа мы пока не знаем!) - правильных "да". Тогда среди "нет" затесалось n-x ответов, которые на самом деле "да", они неправильные, а остальные "нет" тогда, очевидно, правильные. То есть (N-m)-(n-x)=N-n-m+x - правильных "нет" в нашей расстановке.
Итого - у нас получится N-n-m+2x правильных ответов. Запускаем тест, получаем на выходе l - число правильных ответов. Видно, что x=(l+n+m-N)/2.
Таким образом, на втором шаге мы разбили тест на секции, о каждой из которых мы имеем сведения, как после первого шага обо всем тесте. Так же и поступаем дальше.
Можно предположить, что делением на два мы постепенно придем к полному тесту.

Проверка для N=4.
Разбиение 4->2+2->1+1+1+1. То есть 3 проверки.
Пусть Да да нет да.
Тест 1. Да да да да. Выход - 3. N=4, n=3 (три ответа "да", один "нет")
Тест 2. Да да нет нет. Выход - 3. m=2, l=3. Тогда l+m+n-N=3+2+3-4=4, x=2. То есть среди первых "да" оба правильные. Следовательно, среди "нет" только одно правильное. (варианты: "да да да нет" или "да да нет да")
Тест 3. Да да да нет. Выход - 2. По предыдущему тесту делаем вывод, что ответ - "да да нет да".

Проверка для N=5.
Разбиение будет 5->3+2->2+1+1+1->1+1+1+1+1 - итого 4 теста. То есть, формула есть K=ceil(log(N,2))+1 (log - логарифм по основанию 2, ceil - округление до ближайшего целого в большую сторону)
Пусть правильные ответы: Нет, нет, да, да, нет. Далее логика тестера:

Тест 1. (5) Да да да да да - выход 2. Следовательно, у нас 2 ответа "да", 3 ответа "нет". (N=5, n=2)

Тест 2. (3+2) Да да да нет нет - выход 2. (m=3, l=2) l+m+n-N=2+3+2-5=2, x=1. То есть у нас среди первых трех один "да" и два "нет", среди последних двух - один "нет и один "да".

Тест 3. (2+1 + 1+1) Да да нет да нет - выход 2. Пользуясь логикой второго шага, получим вот что...
Общая сумма дробится на три случая: 2=2+0=1+1=0+2.

а) 2+0
Да да нет: N=3, n=1, m=2, l=2 => x=1, т.е. среди первых "да" один правильный, т.е. правильно либо "Да нет нет", либо "Нет да нет".
да нет: N=2, n=1, m=1, l=0 => x=0, т.е. среди "да" нет правильных ответов, тогда ответ правильный: "нет да" - однозначно.
б) 1+1
Да да нет: N=3, n=1, m=2, l=1 => x=0.5, чего не может быть. Т.е. предположение неверно
в) Да да нет: N=3, n=1, m=2, l=0 => x=0, т.е. правильных вообще нет, тогда ответ "Нет нет да"
да нет: N=2, n=1, m=1, l=2 => x=1, т.е. ответ "да" - уже правильный. Т.е. правильно "да нет".
Итого: три варианта: "Да нет нет нет да", "Нет да нет нет да" и "Нет нет да да нет".

Тест 4. Тут можно уже сделать вот такую вещь: подобрать ответ исходя из имеющихся. Так или иначе выход должен быть числом 0, 2 или 4 (1, 3, 5 - если пожелаете). Берем "Нет да да да нет". Видно, что это даст для каждого из вариантов числа, соответственно: 0, 2, 4 - и можем выбрать тот, что нужен. На выходе у нас в нашем случае выйдет ответ 4, и мы так узнаем, что "нет нет да да нет" - нужный нам ответ.

Итого Видно, что такая стратегия хромает (уже для 5 пришлось заниматься списками). Но предполагаю, что и для большого N можно это сделать, хотя и придется долго мучиться. Быстрее, по крайней мере, не получится. Даже очень может быть наоборот (но это очень навскидку). Для больших N получается, по моей раскладке, K=log(N,2).
Но может быть и что K=N/log(N,2)... Пока не уверен.

[Юляша]

Похоже, что степени двойки тут лезут во все дыры... и бином Ньютона, как обычно)

Пусть, для примера, в тесте 8 вопросов (2**3)
Из соображений симметрии первый прогон теста может быть любым - пусть будет "все нет"

Тогда из 256 первоначальных вариантов остается только столько, сколько соответствует нужному коэффициенту бинома - максимальный выбор остается при раскладе 4х4.

Пока что не проанализировано до конца, но навскидку очень эффективной кажется "двоичная гребенка". Для 8 вопросов первые 4 теста будут иметь вид

нннннннн
дддднннн
дднндднн
дндндндн

Есть гипотеза, что после этого можно финишировать буквально 1-2 прогонами.

Для теста из 4 вопросов есть практическая уверенность, что меньше 4 прогонов (при раскладе 2х2) не получится.

[Dendr]

Для теста из 4 вопросов есть практическая уверенность, что меньше 4 прогонов (при раскладе 2х2) не получится.

Да... хотел было расписать, но так и не подобрал нужный вариант. За три не вышло.

(дальше объяснения будут путанные, но попробую пояснее писать)
Табличка получается следующая:
N - K
1 - 1
2 - 2
3 - 3
4 - 4
5 - 4 (?)

По поводу 5 - понятно, что быстрее, чем у 4 - нельзя. Я даже показал, что за 4 в отдельных случаях можно. Но не факт, что это универсальное число-минимум.

По поводу 3. Всего 8 вариантов, точнее, 4 пары - так что максимум запросов 4, остальные подавать бессмысленно.
Первый тест, разумеется, "ддд". Он даст число 0-1-2-3. (запрос "ннн" уже не нужен, как легко догадаться)
0 или 3 - сразу знаем ответ. Если же 1 или 2 - то это симметричные случаи. Берем, значит, 1.
Варианты ддн, днд, ндд. Из-за симметрии перестановок и симметрии "д/н" нам нет разницы, какой запрос делать сейчас. Делаем "ддн". На выходе - 3, 1, 1. То есть. Нужен будет еще и третий запрос.

Вообще, видно, что тут большую роль играет четность.

Вот берем первый заход "дд..д" - и знаем, сколько ответов "да" - обозначаем через n.
Если на второй ставим n раз "да", остальное нет. Получим обязательно четное число. То есть, вообще говоря, один из f(N) вариантов, где f(N)=(N+1)/2 для нечетного N и =N/2+1 для четного.
Для 3 это 2. На первом этапе мы можем ограничить число вариантов до 3. После второго делим их на две подгруппы. 3=2+1. После третьего только большая подгруппа разобьется на единичные. Раньше никак.

Аналогично и дальше: для 4 это 3 (0-2-4). После первого захода можем получить, что число вариантов равно 6. Причем, 0 и 4 отсекут только один из вариантов. У нас останется 4. Другой вариант - делать (1-3). Тогда останутся 3 варианта, причем двух "антиподных" среди нет, поэтому на третьем шаге разбиение будет только на 2, т.е. в любом случае худшая группа будет из двух состоять. Так что, доказано, что быстрее, чем за 4 не сойдется.

Для 5 - это 3. (0-2-4 или 1-3-5). И тут лучше: нет "антиподов". Самый тяжелый случай - 3 "да" + 2 "нет" (или наоборот, неважно) Это получается 10 вариантов. Второй заход оставит обязательно группу из 4 вариантов (10=3+3+4). Третий - из двух (4=2+1+1). И только 4-й - оставит 1 вариант. Итого - похоже и правда, 4.

Дальше пробую применить это для большего N.

[Dendr]

Получается, что так... если вот такие разбиения проводить (уж КАК - это надо на месте для каждого N соображать), получается вот что
6-4
7-4
8-5
9-5
10-5
11-5
12-5
13-5
14-6
15-6
...
Получается, формула такая выходит:
для чисел типа 2p-1: f(p)=**log( C(2p-1,p) ,p)**+2
а для 2p: f(p)=**log( C(2p,p) ,p)**+2
Здесь С(n,k) - биномиальный коэффициент, **х** - целая часть от числа.
Суть следующая (как считал, и какой план у тестера). Берем самый трудный вариант - когда "да" и "нет" поровну, или разница на 1. Определяем число вариантов (бином. коэф.) M.
Дробим их на группы, примерно одинаковые, в количестве штук таком, чтобы можно было зацепить их результатом после запроса. Если у нас некий запрос, то четность результатов одинакова, независимо от правильных ответов. Поэтому это для чисел (2р-1) и (2р) имеем р разных возможных результатов. Соответственно, наибольшая группа будет M/p - округляем до ближайшего большего целого. И так несколько раз, пока после деления не получим единицу.

Думаю - это и есть тот самый минимум. Быстрее - ну никак. А еще надо и придумать стратегию.

[Судовой_Врач]

Инна, если интересует практическая сторона задачи, то лучший, быстрейший и безопаснейший способ - проверять каждым тестом по одному вопросу.
Решение: К=N.
Попытки сократить К приводят к проблемам, что и выяснил Дендр.
Конечно, можно случайно получить и меньшее К. Но предположим, что удача всегда против нас..

П.С.
По сути, эта задача - игра в быки и коровы с бинарным словом неопределенной длины.
Все проверочные слова той же длины. Сообщается только количество коров.
0010101000111110..

[Dendr]

Инна, если интересует практическая сторона задачи

А что значит - "практичная сторона"?
Если я - простой человек с улицы, меня затащили на телешоу типа "кто хочет стать миллионером", но вдруг мне случайно, за кулисами, попадается компьютер, куда загнан этот список вопросов, которые мне зададут, но на все попытки вытрясти ответы он поступает как в условии. Тогда мне действительно нужно как можно скорее получить список ответов.

Но у нас задача не такая. Надо минимизировать число запросов именно, а время на обдумывание неограниченно.
Пусть то же шоу. Но я это делаю в прямом эфире. И от числа попыток зависит мой выигрыш. С одного раза угадаю - миллион долларов. Со ста раз - извини, друг, но только копейка.

Чтобы не было слишком однообразно (с этими шоу) - пусть у нас такой суперкомпьютер.
Есть пульт, на нем ряд тумблеров с двумя положениями (стрелка влево/стрелка вправо). Эти тумблеры определяют положение диода, но какое положение тумблера, левое или правое, задает правильное положение диода, заранее неизвестно (а крышку снимать нельзя). На каждый диод подается 1 Ампер - но "пройдет" ли ток дальше - вот вопрос.
Есть также кнопка подачи энергии. Ставим тумблеры в выбранное положение (левое, например, "да", правое - "нет") и жмем кнопку. Компьютер гудит, тратя петаватты энергии, а в итоге выдает на экранчик лишь значение тока на конечном пункте.
И мы опять щелкаем тумблерами.

И тут вопрос не времени, а расхода энергии. Так что тут обязательно нужен подход с минимизацией числа запросов.

[Dendr]

По сути, эта задача - игра в быки и коровы с бинарным словом неопределенной длины.

Как это, "неопределенной"? Нам же известно заранее N...

Будет время, попробую приложить какую-нибудь тактику к случаю шести вопросов. По моим подсчетам, 4 запроса - это необходимо. Но достаточно ли?

P.S. Построил график этой функции. Забавно, но K(100)=19. Всего лишь. Неужто и правда...

[Судовой_Врач]

..Построил график этой функции. Забавно, но K(100)=19. Всего лишь. Неужто и правда...

Это напоминает попытку сжать любой кусок информации из 100 бит в кусочек из 19 бит.

[Юляша]

Посмотрела предложенную мною гребенку повнимательнее. Худший вариант при 8 вопросах - опять таки 4х4. После 4-х вопросов по гребенке остается 8 неразделенных вариантов с ответом 4 на все вопросы

дднннндд
дндннднд
дннддннд
дннднддн
нддндннд
нддннддн
нднддндн
нндддднн

Еще одного прогона точно недостаточно (из-за четности возможно не больше четырех вариантов ответа)

5 прогон - нддннннд - гарантирует, что останется не больше трех возможностей, (при ответах 5 и 3), в обоих случаях - дднннндн - разделяет эти варианты.

То есть, это гарантированное решение в 6 тестов при восьми вопросах. Я практически уверена, что его улучшить нельзя (при данном числе вопросов). Легко доказать)), что меньше 5 прогонов при 8 вопросах быть не может.

Как вставить сюда формулу с логарифмами и степенями я не знаю, поэтому общую оценку снизу не привожу... (она применима при четном числе вопросов в тесте)

[Dendr]

Это напоминает попытку сжать любой кусок информации из 100 бит в кусочек из 19 бит.

А причем здесь биты?

Смотрим внимательно: у нас 2^100 возможных наборов. Тут я не спорю. Тут - двоичное число.
Но!

Применяем последовательно 19 наборов, на выходе имеем некое число от 0 до 100. А это, коллеги, "стаодноричная" система счисления. Число всевозможных комбинаций выходных ответов - 101^19

2^100=1.26*10^30
101^19=1.2*10^38

Восемь порядков превышения!
Ну, хорошо, погорячился я с 0..100. На самом деле, там четность строго определена видом запроса. То есть на самом деле 50. Эх! Да я не жадный. Пусть возможно только 40 ответов на запрос.
40^19=2.75*10^30 - вполне себе перекрывает то, что надо перекрывать.

Это очень-преочень грубое объяснение, конечно. Но из него можно и нужно понять, что у нас после 19 тестов будет вовсе не 19-битное число.

[Судовой_Врач]

Дендр: "А причем здесь биты?"
Дык дихотомия. Либо ты получаешь одно из двух, либо и того меньше. K=N.
Если N>=20, то 19 тестов не хватит.

Короче, так:
Правильный путь - поочередно на каждом тесте проверять только один вопрос (бит).
При попытке проверить сразу 2 или более вопросов либо получаем экономию, либо теряем тестовую попытку.

[Судовой_Врач]

...
То есть, это гарантированное решение в 6 тестов при восьми вопросах. ...

Юляша, я сомневаюсь, что при восьми вопросах есть решение меньше 8.

Давайте переформулируем эту задачу и спросим у Фёдора, он ведь программист:
Задуман некоторый байт, (например, 0101 1101).
При каждом тесте вы задаёте 1 проверочный байт. Производится операция AND проверочного с задуманным, вам сообщается каждый раз количество единичных битов результата операции.
Сколько "проверочных" байтов достаточно задать, чтобы гарантированно определить любой задуманный?