тестирование, за сколько попыток можно узнать все ответы

[Nikita]

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

у меня получается узнать ответы на все вопросы только за 30 попыток. И последняя - 31-я. Подкиньте идею.

[Mikhail Sokolov]

Похоже, что не сможет.
1.Очевидно, если тест состоит из 1-ого вопроса, то Витя узнает правильный ответ на него после 1-ой попытки.
2. Пусть тест состоит из 2-х вопросов и после первой попытки Витя ответил правильно только на один. Тогда, чтобы узнать ответы на оба вопроса, Вите достаточно знать ответ хотя бы на один из них (ответ на второй в этом случае будет очевиден). Но для этого нужно затратить 1 попытку (см. п.1). Итого в худшем случае надо затратить 2 попытки.
...
И так далее, по индукции, чтобы узнать ответы на $n$ вопросов нужно затратить, в худшем случае, $n$ попыток.

[Архипов]

В отношении максимального количества попыток это так. Конкретное количество попыток зависит от везения. Например, 7 пар вопросов из 15 пар, по теории вероятности, имеют одинаковый номер ответа. Потому имеется возможность за 23 попытки уточнить всю цепочку.
Менять варианты в паре вопросов, а не по одному. Из 8 смешанных пар можно еще две пары угадать, перемешав их. Итого - можно за 21 попытку угадать все ответы. Приблизительно.

[Nikita]

Mikhail Sokolov
вот и я так подумал.

Архипов
в задаче ведь не сказано, что ответы на вопросы распределены случайно между вариантами ответов. Значит, вполне может быть, что одинаковый номер ответа у всех 30 вопросов.

[gris]

Если Витя ошибся больше, чем в трех вопросах, то ему лучше убиться об стенку или пойти поучить материал, а не изобретать хитроумные методы подбора. Всё равно у такого тупого ничего не получится. А если только три неправильных ответа, то разбиваем на тройки, инвертируем ответы последовательно в каждой тройке, в самом плохом случае получаем за 11 попыток девять подозрительных билетов, с которыми разбираемся еще за 5 попыток.

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

У меня пока два малюсеньких соображения. Пусть инвертировать группу означает поменять 0 на 1 и 1 на 0. Если при первом испытании нам удалось угадать меньше 15 бит, то просто инвертируем всю строку и получаем гарантированно 15 правильных ответов.
если инвертировать группу из нечетного количества бит, то можно узнать есть ли в ней совпадения и даже сколько их в ряде случаев.

Надо, наверное, делать попытки подобные
00000000....
10101010...
110011001100... и так далее.
Мне кажется, что есть подобная задача про нахождение фальшивой монеты(?).

[Mikhail Sokolov]

Да, я был не прав.
Например, если неправильный ответ был всего 1, то можно инвертировать половину множества вопросов, тем самым определив в какой из половин дан неправильный ответ, и т.д.

[Хорхе]

Простите за оффтоп: 1) это задача с Турнира городов, почему она не в разделе "ОЗ"? 2) Неужели в Саратове не делают разбора Турнира городов? Или это Вы его и проводите?

PS По теме: ответ на оба вопроса "да".

[Архипов]

Nikita в сообщении #157057 писал(а):

Архипов
в задаче ведь не сказано, что ответы на вопросы распределены случайно между вариантами ответов. Значит, вполне может быть, что одинаковый номер ответа у всех 30 вопросов.

Ну, так Витя и задаст все одинаковые. Понадобилась одна попытка, чтобы узнать все 30 верных ответов.. Повезло.

[Nikita]

а если рассмотреть случай 4х битного ключа. Можно ли уложиться в 4 попытки?
По-моему нет.

0110 - пусть это будет правильный ответ на тест.
_____
0000 - 2 правильных
1010 - 2 ...
1100 - 2 ...
1001 - 0 - инвертируем - 0110
0110 - итого 5 попыток.

Хорхе
меня поставила в тупик эта задача.

Архипов
хорошо, когда везет. Но ведь, может и не повезти.

[gris]

Инвертировать надо именно нечетное количество бит. Иначе мы сможем и не получить информации о наличии в группе несовпадений.
0000 2
1000 1 - уменьшилось, значит первый бит был правильный. Займся тремя другими.
0100 -3 - увеличиилось, значит второй бит правильный и еще один из двух последних.
0110 ОК!
Увы, с ключом 0101 не работает
Двухбитный ключ, впрочем, раскалывается только на третьей попытке, трехбитный на четвертой.