Про весы-обманщики. История одной задачи

Я люблю рассказывать истории про задачи. Особенно когда задачи того стоят. Один из таких замечательных сюжетов – «весы-обманщики». Задачку на эти весы я придумал очень давно, но как-то всё не представлялось возможности ее пристроить. Однако в прошлом году я решил, наконец, кинуть ее в «Математику в школе». Вот условие, с которым она была опубликована:

5418. Среди 9 монет 8 одинаковых настоящих и одна фальшивая, чуть более лёгкая. Костя хочет определить эту монету с помощью чашечных весов без гирь. Сможет ли он справиться с этим за 4 взвешивания, если в одном из них весы могут «соврать» (то есть результат какого-то одного взвешивания может оказаться неправильным)?

Приводить решение я пока не буду, потому что в журнале указан срок присылки решений до 30-го сентября. Желающие могут порешать. (Хотя, если вы прочитаете всё, что я написал ниже, то решение этой задачки покажется совсем детским) Вместо этого расскажу то, что осталось «за кадром», благо, этого добра тут много.

Во-первых, почему целых 4 взвешивания? Неужели не хватит меньшего количества? Ведь если весы всё показывают правильно, то хватает и двух взвешиваний... Оказывается, здесь всё тютелька в тютельку, - не просто без запаса в одно взвешивание, но и даже без запаса в одну монету! Покажем, что для 10 монет эта задача за 4 взвешивания неразрешима.

Пусть мы думаем, что научились решать задачу для 10 монет, то есть при каждой фальшивой монете и каждом способе вранья весов правильно определим ФМ. Если в каких-то случаях нам удастся это сделать быстрее четырех взвешиваний – ну что ж, прекрасно, значит, оставшиеся взвешивания делаем как угодно и не обращаем внимания на их результаты. 

Представим, что против нас действуют не бездушные весы, а некий соперник, который сознательно выбирает, какая монета будет фальшивой, на каком взвешивании он нас обманет (и будет ли обманывать вообще) и как именно (т.е. какой из двух неверных исходов он нам сообщит). Если мы всё равно умеем найти ФМ, то мы умеем отгадывать и поведение соперника. Но сочетание «выбор ФМ + поведение соперника» даёт ему 10*(1+2*4)=90 вариантов, а 4 взвешивания – это всего 3^4 = 81 вариант. Таким образом, какие-то варианты будут для нас неразличимыми, а это означает, что гарантированно находить ФМ мы не сможем.

Это рассуждение показывает, что число монет не может быть больше, чем 81/(1+2*4), то есть 9.

Ok, а теперь подумаем, как бы обобщить задачку? Прежде всего, в обобщении нужно постараться тоже предложить точный результат, то есть такой, при котором число вариантов за соперника будет в точности равно числу вариантов, обеспечиваемых взвешиваниями. А поскольку для N взвешиваний у соперника (не считая выбора монеты) имеются 1+2N вариантов выбора поведения, значит, это количество должно быть степенью тройки. Следующее такое N равно 13. Иначе говоря, мы хотим разрешить делать 13 взвешиваний. Оценка вариантов говорит нам, что максимально возможное число монет при этом равно 3^13 / (1+2*13) = 3^10.

Найдя это значение, я подумал, что никогда в жизни не рискну выдать в олимпиаду задачу про 13 взвешиваний и 59049 монет! Однако, к счастью, в жизни бывают не только школьные олимпиады. Просматривая недавно свою старую переписку, я наткнулся в ней на задачу от моего знакомого, присланную мне еще в 2006 году:

59049 монет и одно неверное взвешивание

Есть 59049 монет (3¹⁰). Среди монет имеется одна фальшивая. Известно, что фальшивая монета немного тяжелее настоящей. Сколько нужно взвешиваний на чашечных весах без гирь, чтобы определить фальшивую монету, если известно, что во время одного из взвешиваний весы могут показать неверный результат?

И – каюсь – даже не задумавшись толком над нею – написал автору:

То, что должно хватать 13 взвешиваний, я понимаю. То, что скорее всего существует троичный код Хэмминга из 3^10 кодовых слов (длины 10 каждое) с расстоянием 3 между кодовыми словами, я тоже понимаю. Хотя ни разу его и не видал. Но ведь для существования плана взвешиваний мало существования такого кода, нужно еще и сбалансированность по каждому разряду обеспечивать... Короче, как Вы предполагали это решать?

В ответ получил ссылку на форум c головоломками на SciTecLibrary.ru, http://www.sciteclibrary.ru/cgi-bin/yabb2/YaBB.pl?num=1145890398, где с чувством восхищения простотой прочёл следующее изящное решение (от Pupugai, увы, не знаю, кто это такой).

Первые 10 взвешиваний как обычно: 

Нумеруем монеты и за k-ое взвешивание сравниваем монеты с k-ой цифрой в троичной системе 1 и монеты с k-ой цифрой в троичной системе 2.

В итоге получаем одного Главного Кандидата - монету, которая будет фальшивой при условии, что все взвешивания были правильны.

И еще 20 дополнительных кандидатов, которые могут быть фальшивыми при одном неправильном взвешивании (по 2 кандидата на одно неправильное взвешивание). 

11-е взвешивание: 8 и 8 из числа дополнительных кандидатов.

Если одна из чаш перевесит, то мы знаем, что хотя бы одно неправильное взвешивание уже было, и фальшивая монета либо Главный Кандидат, либо одна из 8 перевесивших. Из этих 9 монет находим фальшивую стандартным способом за 2 взвешивания.

Иначе фальшивой может быть только Главный кандидат или одна из четырех оставшихся монет. 

Делаем 12-е взвешивание: 2 и 2 из этих четырех.

Если равновесие, то фальшивая - Главный кандидат. Иначе опять уже было неправильное взвешивание и фальшивая одна из трех, которую находим за одно 13-е взвешивание.

Но не успел я мысленно обругать себя за то, что не сумел решить задачку, как получил по башке еще более красивым рассуждением от WhiteKnight.

1. Нумеруем монеты i10...ik...i1, ik=0,1,2; k=1..10
2. В k-ом взвешивании на одну чашку кладем монеты с 0 в k-ом разряде, на другую с 1. Результат k-ого взвешивания Wk записываем как: 
      0 - перевесила чашка с "0"   1 - перевесила чашка с "1"   2 - равновесие (фальшивка в группе с 2 в k-ом разряде)
3. Результат взвешивания W10...Wk...W1 указывает на номер "главного" кандидата (не было ошибок в первых 10 взвешиваниях). Если ошибка произошла в k-ом взвешивании, то добавляются два дополнительных кандидата W10W9...Dk...W2W1, где Dk >< Wk не совпадающие с Wk две другие цифры. Итого имеем 20 дополнительных кандидатов. 
4. 21 монету-кандидат дополняем 6 настоящими (любыми из оставшихся) до 27 и организуем 3 дополнительных взвешивания по прежнему принципу. Занумеруем их j3j2j1. 
5. Если в основных взвешиваниях ошибки не было - главный кандидат фальшивый - то ошибка может произойти в одном из доп. взвешиваний. Главного кандидата занумеруем 000 - результат дополнительных взвешиваний V3V2V1 без ошибки должен быть 000. Ошибка в любом из взвешиваний/разряде даст один из результатов 100, 200, 010, 020, 001, 002. Именно на эти 6 мест мы помещаем настоящие монеты. На остальные 20 мест - дополнительных кандидатов.
6. Если ошибка случилась в основных взвешиваниях, то результат дополнительных взвешиваний V3V2V1 безошибочно укажет номер одного из 20 доп.кандидатов.

И уже после этого автор задачи – мой знакомый, Lactarius – убил меня наповал, опубликовав (там же, по ссылке Ответ #14) «бонусную» задачу.

Пусть имеется 3⁶ монет. При этом известно, что не более двух взвешиваний могут оказаться ошибочными. Сколько взвешиваний потребуется для определения фальшивой монеты?

Давайте сначала сосчитаем. Вместе. Пусть мы проделали N взвешиваний (и имеем 3^N исходов). За эти взвешивания наш Соперник мог ни разу не обмануть, или обмануть 1 раз (2N вариантов) или обмануть дважды (4*N(N-1)/2 вариантов, так как для каждого выбора пары неверных взвешиваний есть 4 варианта ответа). Не очень трудно сосчитать, что наименьшим N, при котором выполнено неравенство 3^N  3^6 (1+2N+2N(N-1)), является N=11. При этом выражение в скобках (1+2N^2) оказывается равным 1+22+220=243 = 3^5, то есть равенство здесь снова точное!

Кивок в сторону. Может быть, Вы когда-нибудь пробовали решать уравнение 1+2n^2=3^m. Пара (11,5) – это наибольшее из его целочисленных решений... Но я уже примерно понимал, как действовать. Давайте еще раз вместе. 

Первый этап - 6 взвешиваний по "покоординатному" плану. После них у нас имеется следующая картинка

1 "главная" ФМ при условии, что весы ни разу еще не врали

12 "дополнительных" ФМ при условии, что весы врали 1 раз (2 варианта ошибочного ответа на каждом из 6 взвешиваний)

60 "вторичных" ФМ при условии, что весы врали уже два раза (4 варианта на каждой из 15 пар взвешиваний)

И что дальше? У нас осталось 5 взвешиваний - 243 варианта. При этом для главной монеты всё еще есть 51 вариант (1 без обмана, 10 с одним обманом, 40 с двумя), для 12 дополнительных есть 12+120 вариантов не более чем с одним обманом, а для оставшихся 60 – всего по одному варианту. Формально 51+132+60=243, то есть всё сходится, - но как дальше взвешивать?? Нам нужно сделать так, чтобы любой из результатов первого взвешивания оставлял 81 вариант. Значит, придется как-то взвешивать не только вторичные ФМ – их нам просто не хватит.

Допустим, мы положили на весы по X дополнительных ФМ и по Y вторичных. Тогда при равенстве у нас останется 1+8+24=33 варианта с главной монетой, (60-2Y) вариантов со вторичными и... сколько ещё? Во-первых, действительно может оказаться, что это взвешивание не содержит ошибки, и тогда остаются 12-2X дополнительных. Во-вторых, это взвешивание может быть ошибочным, а тогда 2X дополнительных превращаются во вторичные! Иначе говоря, у нас остается 33 + (12-2X)*9+(60-2Y+2X) вариантов. Это даёт уравнение 8X+Y=60. Ура! Что-то прояснилось. Теперь просчитаем еще уравнение для результата «одна из чаш перевесила», и получим систему, из которой найдём X и Y. 
Но не тут-то было: второе полученное уравнение в точности совпадает с первым. (Вообще говоря, это и не удивительно, просто в горячке не пришло в голову.)

Ну, значит, однозначного решения системы не получается, а следовательно, можно брать, например, X=6 и Y=12. А вот дальше что? У-у-у... Я покопался в вариантах еще какое-то время и понял, что лучшим выходом будет решение с планом а-ля WhiteKnight. Поиск этого решения занял у меня часа два, но я справился. Вот оно:

Теперь составим план на оставшиеся 5 взвешиваний. Отметим, что каждая монета в таком плане однозначно характеризуется набором координат - пятимерным вектором, состоящим из чисел 0,1,2. i-я координата такого вектора говорит нам, на какую из чаш весов эта монета кладется в i-м взвешивании (i от 1 до 5). Для успешности плана (не в конкретной задаче, а вообще) достаточно, чтобы у разных монет не было одинаковых векторов координат. Еще нужно, чтобы в каждом взвешивании на чашах было поровну монет, но это кажется намного более простым требованием. "Главной" ФМ мы сопоставим вектор 00000.

Для "дополнительных" назначим следующие 12 координат:

01122

02211

20112

10221

22011

11022

12201

21102

11220

22110

11111

22222

Заметим, что хеммингово расстояние между всеми этими точками не меньше 3. Это очевидно для любой пары вида "одна из 10 первых точек + одна из двух последних" и для всех пар точек, в которых 0 стоит на одной и той же позиции. Если же у двух точек индекс (позиция) нуля отличается, то отличаются также позиции у хотя бы одной единицы и хотя бы одной двойки, потому что все эти точки получены циклическими сдвигами – две одинаковые цифры СТОЯТ РЯДОМ ЗА нулём или ПЕРЕД ним.

Так как расстояния не менее 3, то все точки, находящиеся на единичных расстояниях от этих 12 точек (а таковых ровно по 10 штук), различны. На расстояниях 1 и 2 от точки 00000 находятся 10 точек с четырьмя нулями в координатах и 40 точек с тремя нулями - все они отличны от всех вышеперечисленных.

Итого сколько у нас осталось неперечисленных точек, то есть таких, которые находятся на расстоянии более 1 от "дополнительных" и более 2 от "главной"?

243 - 12 - 120 - 1 - 10 - 40 = 60.

Именно в них мы и поместим все "вторичные" ФМ. План готов. Проделав взвешивания по плану, мы попадём либо в одну из точек-монет (и тогда она и есть фальшивая), либо в точку, соседнюю с "дополнительной" монетой (и тогда фальшивой будет эта дополнительная), либо в точку на расстоянии не более 2 от "главной" (и тогда фальшивой будет "главная" монета.