Таблицы Брадиса

Во второй взвешиваем множество .

Во второй взвешиваем множество .

Математическое просвещение - Винберг Э. Б

Отметим, что для канонических тестов результат каждого взвешива­ния в совокупности с результатом первой попытки позволяет вычислить вес множества X и его дополнения.

Разобьём 2M+N — 1 вопросов теста на три части, две из которых (назо­вём их A и B) содержат M вопросов, а третья часть С — остальные N — 1 вопросов. Заметим, что множества вопросов A, B и C не пересекаются.

По условию леммы правильные ответы на вопросы каждой из частей A или B можно узнать каноническим тестом из N попыток. Подмножества вопросов, которые мы бы взвешивали в этих попытках, мы будем обозна­чать Ai,..., An-i для части A, для части B взвешиваемые в каноническом тесте множества обозначим через Bi,..., Bn-i.

Список попыток тоже разобьём на три части: первая попытка, вторая попытка, части «Sum» и «Diff» (из N — 1 попыток каждая). В первой по­пытке мы отвечаем «да» на все вопросы (это канонический тест). Во вто­рой — взвешиваем множество B. В части «Sum» взвешиваем в I-й попытке A/ U B/ U С/. В части «Diff» в I-й попытке взвешиваем A/ U (B \ B/). Рас­смотрим, какие выводы можно сделать, получив результаты первых двух попыток и I-х попыток из «Sum» и «Diff», то есть узнав веса A/ + B/ + С/, A/ + B — B/ и B. Очевидно, что чётность суммы этих результатов совпа­дает с чётностью значения С/, что даёт нам знание правильного ответа на вопрос С/. Дальше из системы уравнений легко находим веса A/ и B/.

Наконец, зная общее число ответов «да» во всем тесте, а также в частях В и С, мы можем определить вес А. Таким образом, по результатам про­деланных попыток мы знаем результаты взвешиваний всех подмножеств Аі,..., А^-і, А, всех подмножеств Ві,..., В^-1, В и правильные ответы на все вопросы множества С. В силу выбора множеств А/, В/ мы в состо­янии по этим данным узнать правильные ответы все вопросы множеств А и В, на этом доказательство леммы закончено.                                                                                           □