|
|
 |
Условие
Тест состоит из 30 вопросов, на каждый есть два варианта ответа (один верный, другой нет). За одну попытку Витя отвечает на все вопросы, после чего ему сообщают, на сколько вопросов он ответил верно. Сможет ли Витя действовать так, чтобы гарантированно узнать все верные ответы не позже, чем
а) после 29-й попытки (и ответить верно на все вопросы при 30-й попытке);
б) после 24-й попытки (и ответить верно на все вопросы при 25-й попытке)?
(Изначально Витя не знает ни одного ответа, тест всегда один и тот же.)
Решение 1
Можно считать, что ответы на каждый вопрос – это ДА и НЕТ.
а) Пусть в k-й попытке (k = 1, 2, ..., 29) Витя отвечает ДА на k-й вопрос и НЕТ на все остальные. Каждые две попытки отличаются ровно в двух местах, поэтому результаты либо совпадают, либо отличаются на 2. Если результат k-й попытки отличается от результата 1-й, то Витя сразу узнаёт ответы на 1-й и k-й вопросы. Зная ответ на 1-й вопрос, он узнает ответы и на все остальные.
Если же результаты всех попыток совпадают, то ответы на первые 29 вопросов одинаковы. Тогда по результату 1-й попытки определяется как этот общий ответ, так и ответ на 30-й вопрос.
б) При 1-й попытке Витя отвечает НЕТ на все вопросы. Разобьём вопросы на 6 групп по 5 вопросов. Покажем как за четыре попытки узнать ответы на все вопросы такой группы.
В этих четырёх попытках Витя отвечает ДА только на часть вопросов из данной группы:
а – на все вопросы (здесь Витя узнаёт сколько ответов ДА в нашей группе);
б – на 3-й, 4-й, 5-й;
в – на 2-й, 4-й, 5-й;
г – на 2-й, 3-й и 5-й.
Нетрудно проверить. что последние три попытки действительно дают полную информацию об ответах на все пять вопросов.
Осталось заметить, что вопрос а) в последней группе задавать не нужно, так как мы и без него знаем число ответов ДА (во всем тесте и в остальных группах, а значит, и в последней).
Решение 2
Попытку, в которой ответ ДА даётся на все вопросы из некоторого множества A, а ответ НЕТ – на все остальные вопросы, будем называть взвешиванием множества A. Весом множества A вопросов будем называть количество правильных ответов ДА в этом множестве.
Заметим, что взвесив весь тест, мы узнаём его вес. Взвесив же после этого произвольное множество A, мы можем узнать и вес A: сложив результаты этих двух попыток и вычтя из этой суммы количество вопросов, не входящих в A, мы получим удвоенный вес A.
Далее мы будем рассматривать только правильные алгоритмы. Такой алгоритм на n попыток задаётся списком A1, ..., An–1 множеств вопросов и состоит из предварительного взвешивания всего теста и последующего взвешивания множеств A1, ..., An–1.
Лемма. Если существует правильный алгоритм, разгадывающий тест из m вопросов за n попыток, то существует правильный алгоритм, разгадывающий тест из 2m + n – 1 вопросов за 2n попыток.
Доказательство. Разобьём все множество из 2m + n – 1 вопросов на 3 части: А – первые m вопросов, B – следующие m вопросов, дополнительные n – 1 вопросов X1, ..., Xn–1. По условию тест, состоящий только из множества А, можно разгадать за n попыток. Пусть A1, ..., An–1 – взвешиваемые при этом множества. Обозначим через Bi множество, получающееся из Ai увеличением на m номеров всех его вопросов.
Новый алгоритм состоит из трёх этапов.
Первый этап состоит из двух попыток: взвешивания всего теста и множества B (пусть его вес равен b).
Второй этап состоит из n – 1 попытки: в i-й из них взвешивается множество Ai∪Bi∪Xi (то есть находится сумма ai + bi + xi весов множеств Ai и Bi и вопроса Xi).
Третий этап также состоит из n – 1 попытки: в i-й из них взвешивается множество Ai∪(B \ Bi) (то есть находится сумма ai + b – bi).
Поскольку мы знаем b, после третьего этапа находим все разности ai – bi.
Складывая ai + bi + xi с ai – bi, по чётности определяем xi. После этого находятся все ai и bi, а также вес a множества A (вычитанием
b + x1 + ... + xn–1 из веса теста).
По условию знание весов a, a1, ..., an–1 позволяет узнать ответы на все вопросы из A, а знание b, b1, ..., bn–1 – ответы на все вопросы из B.
Начиная с тривиального алгоритма, разгадывающего тест из двух вопросов за две попытки, по индукции получаем
Следствие. Тест длины n·2n–1 + 1 можно разгадать за 2n попыток.
В частности, тест длины 33 можно разгадать за 16 попыток. Тем более тест длины 30 можно разгадать за 16 попыток.
Ответ
Сможет.
Замечания
1. Баллы 5 + 5.
2. Обсуждение задачи см. в статье К. Кнопа и Л. Медникова "Тест Клепцына: с компьютером и без него".
