Дык нет дихотомии. У нас же ответ на наш запрос не бинарный, и это при разумном подходе укорачивает дело.Судовой_Врач писал(а):Дендр: "А причем здесь биты?"
Дык дихотомия.
Кроме того, от полученных на выходе данных мы можем изменять наш следующий запрос. Записывая ответы в ряд, мы получим некое число в "несколько-ричной" системе счисления, которому ставим в соответствие одно и только одно число в двоичной системе. И не невероятно, что длина первого числа будет короче, чем второго.
Да, для ста вопросов достаточно ста проверок - это очевидно. Необходимо - 19, но не доказано, что необходимо и достаточно. Но имею мнение, что и 99 будет достаточно. Объясню ниже.
Для шести вопросов, 4 проверки и правда недостаточно. Долго колупался, но так и не нашел стратегии. Может, для
Но для пяти - я выше показал, что 4 - необходимо, но не показал, что достаточно.
Показываю теперь.
Первый тест: ддддд.
На выходе:
0 - нет ответов "да". Следовательно, мы выяснили, что правильный ответ - "ннннн".
1 - один ответ "да". Имеем 5 вариантов: "днннн", "ндннн", "ннднн", "ннндн" и "ннннд".
2 - два ответа "да". Тут 10 вариантов. Не стану их перечислять, чтобы не загромождать форум.
3 - три ответа "да", или два ответа "нет" - зеркальное отражение случая (2).
4 - отражение случая (1)
5 - отражение случая (0)
Рассмотрим отдельно (1) и (2). Остальные либо уже вышли на ответ, либо аналогичны этим.
(1) Второй тест: ддднн.
Мы знаем, что у нас ровно один ответ "да". Он либо среди первых трех, либо среди последних двух.
В первом случае нам выдадут на выходе - 3.
Во втором случае - 1.
(надо доказывать?)
а) мы узнали, что у нас 1 ответ "да", 4 ответа "нет", и ответ "да" - среди первых трех. Делаем третий запрос: ддннн. Если "да" на самом деле в первых двух местах, нам выдадут на выходе 4. Если на третьем - 2.
То есть, мы теперь знаем, что выходное данное 132 дает нам "ннднн", а 134 - один из двух вариантов. "днннн" или "ндннн". Четвертым запросом мы получим то, что хотим.
б) тут мы знаем, что у нас либо "ннндн", либо "ннннд", и у нас выходное данное 11. Следующий запрос даст нам окончательный ответ.
(2) Второй тест: ддднн.
Тут три возможности: оба ответа "да" в первой части (выход - 4), оба во второй (выход - 0), в разных (выход - 2).
а) три варианта: "ддннн", "днднн" и "ндднн". Это аналогично варианту (1а). То есть и тут достаточно двух запросов. Итого - 4.
б) один вариант: "ннндд". Тут все понятно.
в) 6 вариантов: "днндн", "днннд", "ндндн", "ндннд", "ннддн", "ннднд".
Вот это самый сложный случай. Займемся им особно. Пока у нас на выходе получилось 22.
Все варианты, какие могут быть:
днндн
днннд
ндндн
ндннд
ннддн
ннднд
Третий запрос: ддндн
соответсвенно, выходы:
4 2 4 2 2 0
Итого - если выходное число:
220 - у нас один вариант: "ннднд"
224 - два варианта: "днндн", "ндндн" - одним дополнительным запросом решаем (четвертым)
222 - 3 варианта. "днннд", "ндннд", "ннддн". Этот случай самый сложный, на нем и задержимся опять.
Варианты, повторю отдельно: днннд ндннд ннддн
Четвертый запрос: ндддн
выходы: 0 2 4 - каждый однозначно определяет один из вариантов полного ответа.
*****************************
Общий итог.
Определить ответы на 5 вопросов возможно за 4 запроса.
Стратегия:
Первый запрос ддддд
Варианты:
0 - ответ "ддддд" *
1 - см. ниже (5 вар-в)
2 - см. ниже (10 вар-в)
3 4 5 - строго аналогичны первым трем - делаем зеркальное отображение.
Второй запрос ддднн
Варианты (с учетом первого выхода)
13 - 3 варианта: "днннн" "ндннн" "ннднн"
11 - два варианта: "ннндн" "ннннд"
20 - ответ "ннндд" *
22 - 6 вариантов "днндн" "днннд" "ндндн" "ндннд" "ннддн" "ннднд"
24 - три варианта: "ддннн" "днднн" "ндднн"
Видно, что случаи (13) и (24) очень похожи, и определяются максимум за два запроса каждый.
Случай (11) решится за один запрос - тут понятно и без слов.
Случай (20) уже дал полный ответ.
И случай (22) решается тоже за два запроса. Тут вообще универсально можно сделать. Третий запрос будет ддндн, четвертый - ндддн.
2242 "днндн"
2220 "днннд"
2244 "ндндн"
2222 "ндннд"
2224 "ннддн"
2202 "ннднд"
Таким образом, показано, что для пяти вопросов достаточно 4 проверок.
Ранее было доказано, что для этого же случая необходимо 4 проверки. То есть, для пяти вопросов необходимо и достаточно четырех проверок.
Следовательно, по индукции, для N>=5 достаточно K(N)=N-1.
