Тест состоит из 30 вопросов, на каждый есть два варианта ответа (один верный, другой нет)
За одну попытку Витя отвечает на все вопросы, после чего ему сообщают, на сколько вопросов он ответил верно. Сможет ли Витя деймтвовать так, чтобы гарантированно узнать все верные ответы не позже, чем
а) после 29-й попытки (и ответить верно на все вопросы при 30-й попытке)
б) после 24-й попытки (и ответить верно на все вопросы при 25-й попытке)

(Изначально Витя не знает ни одного ответа, тест всегда один и тот же)

Решение от Златы

вот такое решение:
1. 1-я попытка ДА на все вопросы. Получаем К очков
2. На 1,2 отвечаем НЕТ, на остальные ДА. ПОлучаем К-2, К, или К+2 очков
3. В случае К-2, или К+2 мы однозначно определяем ответы 1 и 2. Далее, меняя на НЕТ по одному из вопросов, мы определяем его. И к 29-й попытке у нас уже определены все вопросы. С 30-й сдаём экзамен
4. В случае К (один был верный, другой нет), мы возвращаем предыдущий (первый) в ДА, а в НЕТ ставим два следующих (2 и 3). По тому же алгоритму, если получим К-2, или К+2, определим эти вопросы, а далее по цепочке предыдущие, если получаем К, повторяем алгоритм.
5. Действие должно закончиться, как только рядом окажутся два последовательных вопроса с ответами ДА или НЕТ. Что обязательно должно случиться при К не равно 15.
6. Пусть К=15 (первая попытка)
7. Отвечаем НЕТ на первый вопрос и определяем его. - 2-я попытка
8. Отвечаем НЕТ на 2,3 вопросы - 3-я попытка
,,,,,,,,,,,,,,,,
9. отвечаем НЕТ на 28, 29 вопросы - 29 попытка. Получаем К очков
10. Однозначно определяем чередующуюся последовательность ответов по первому вопросу

Ну самый тупой метод дает 30 попыток и гарантированно верный ответ на 31-й

_________________
А кто сказал, что я прав?

Алг, при К=15 не проходит ИМХО Для примера две исходных последовательности из а=4 вопросов
1010 и 0101
1111 = 2 и 2
0011 = 2 и 2
1001 = 2 и 2
итого выяснили, что ответы чередуются, но не понятно, что на первом месте нужен еще один 4-й вопрос.

_________________
А кто сказал, что я прав?

так при к=2 другой алгоритм предлагала

1010 и 0101

1111
0111
1001
обнаружили чередующуюся послед. и знаем первый элемент
однозначный ответ с 4-й попытки

Пардон, ошибся не заметил перехода ко второму алгоритму
110100 101010
111111 = 3 и 3
011111 = 2 и 2
100111 = 3 и 3
110011 = 3 и 3
111001 = 3 и 3
Похоже, что в случае удвоения первых и последних еще по вопросу надо

_________________
А кто сказал, что я прав?

А вообще-то теория говорит, что что бы получить 1 бит информации надо задать 1 бинарный вопрос. В условии я пока не вижу скрытой информации в процедуре теста, а если ее там нет, то увы

_________________
А кто сказал, что я прав?

101010 ок
110100 ты прав.

Мы получаем каждый раз НЕ бинарную информацию, а число от 0 до 30.
Потенциально - 5 бит.