Электронная рассылка

ОТВЕТ  ЗАДАЧИ  С  12 МОНЕТАМИ

Ну – ну.

Этот вы пуск рассылки – экстренный. Я собирался отослать его только через неделю. Но я не умею отказывать женщинам, и если женщина просит, а тем более требует – как откажешь. Вот какое письмо мне прислала Елена:

«Я не могу понять,а где же ответ на задачу?

У нас с мужем были всякие соображения по поводу решения этой задачи с

монетами,но никто из нас не пришел к нужному решению.

Месяц ожиданий,а в итоге- ответа не поступило,подсказки подсказками,но

где же долгожданное решение,так, вы вводите людей в ещё большую

задумчивость,может вы сами и не знаете решения,а просто хотите,чтобы

такие как мы решили вместо вас эту задачку,но мы же всётаки не

Энштейны и не его дети.Просим выслать ответ на мыло.

Р.S.Очень извеняюсь,если хоть чем-то оскорбила вас.

Я думаю вашего ответа будет достаточно,чтобы больше не сомневаться в

ваших интелектуальных способностях.» (Конец цитаты)

Я был дважды женат и дважды успешно развелся, и поэтому я высоко ценю способности женщин. Особенно интеллектуальные. Они правда несколько отличаются от наших. И я, конечно, не могу их оценить в полной мере, но ценю высоко. Не знаю будет ли достаточно моего ответа, но попытаюсь…

ОТВЕТ  АННЫ.

Вот что пишет М. Гарден в книге «Математические досуги»:

«Эта задача была блестяще разобрана К.Л.Стронгом в майском номере журнала Scientific American за 1945 год. Одно из ее решений (а их довольно много) связано с троичной системой.»

Много ответов прислали мне и Вы. Я хочу привести Вам ответ Анны. Во-первых, она первой написала, что монет может быть 13, а во-вторых, ее ответ достаточно компактен.

Томи! Большое спасибо за красивую задачу. Она классная! Одно
замечание: поскольку в задаче не требуется определить легче или
тяжелее стандартной фальшивая монета, монет может быть и 13.
        РЕШЕНИЕ:
Нумеруем монеты. Взвешивание первое:
на левую чашку весов кладём ╧╧ 1,2,3,4; на правую - 5,6,7,8. Допустим,
что нам повезло и чашки оказались в равновесии. Назовем это случаем А.
Тогда фальшивую монету надо искать среди ╧╧ 9, 10, 11, 12, 13.

Взвешивание второе для случая А:
налево кладём ╧╧ 9 и 10; направо - 11 и любую гарантированно
нормальную. Напр. ╧1. Если весы опять в
равновесии (случай Аа), то нестандартная монета - либо ╧12, либо ╧13.
Тогда в третьем взвешивании нужно сравнить вес одной из них с весом стандартной.
Кладём налево ╧12, направо - ╧1. Если равновесие, фальшивая - ╧13.
Правда, мы не можем сказать, легче или тяжелее она стандартной, но это и не
требуется.
Если равновесия в паре ╧1 - ╧12 нет, фальшивая - ╧12. Причём в этом
случае мы видим, легче или тяжелее она стандартной.

Вернёмся ко второму взвешиванию. Если равновесия нет (случай Аб), значит,
мы имеем три подозрительные монеты - ╧╧ 9 и 10 на одной чашке и ╧11 на другой.
Допустим, правая чашка перевесила (если перевесила левая чашка,
рассуждения аналогичны), значит: либо ╧9 лёгкая, либо ╧10 лёгкая,
либо ╧11 тяжёлая. В третьем взвешивании на одну чашку кладём ╧9, на
другую - ╧10. В случае равновесия - фальшивая монета ╧11. Она тяжелее. Если
равновесия нет, фальшивая та, что легче.

Теперь вернёмся к началу, к первому взвешиванию. Допустим, нам не повезло и
левая, к примеру, чашка весов пошла вверх(назовём это случаем Б). Это могло
произойти только в следующих случаях: либо ╧1, либо ╧2, либо ╧3, либо ╧4
оказалась лёгкой; либо ╧5,либо ╧6, либо ╧7, либо ╧8 оказалась тяжёлой.
Если вверх пошла правая чашка, рассуждаем аналогично.

Взвешивание второе для случая Б. Уберём с весов три подозрительные монеты,
но добавим одну нормальную и кое-что поменяем местами таким, к примеру,
образом: левая ч. - ╧╧ 1, 2, 5; правая - ╧╧ 3, 6, 9. В случае равновесия мы
третьим взвешиванием легко обнаружим фальшивую монету среди трёх
убранных, помня, что ╧4 может быть только стандартной или лёгкой, а
╧╧7 и 8 только стандартными или тяжёлыми.
Если после второго взвешивания левая чашка пошла вверх, значит: либо
╧1 лёгкая, либо ╧2 лёгкая, либо ╧6 тяжёлая. Как найти среди них
фальшивую за одно взвешивание, я уже писала.
Если после второго взвешивания левая чашка пошла вниз, значит:
либо ╧3 лёгкая, либо ╧5 тяжёлая. Сравнив третьим взвешиванием любую из
них с нормальной, найдём фальшивую.
С уважением, Анна.

Мой ответ из той же логики, но оформлен несколько по другому. Вот он:

Условимся, монеты, которые лежат на «тяжелой» чашке, обозначать знаком +, монеты на легкой чашке знаком -, и качественные монеты знаком *. Так как фальшивая монета, может быть только или тяжелой и лежать на «тяжелой» чашке, или легкой и лежать на «легкой» чашке, то получается следующая «алгебра» при 2-х взвешиваниях: ++ = +;   -- = -;  +-=*; -+=*. Другими словами, если монета лежит на чашке, которая внизу, а затем, на чашке, которая вверху, то она не фальшивая. Это мой фокус.

Лемма 1. Задача из трех монет (две монеты + и одна -, или две монеты – и одна +) решается в одно взвешивание. Пример:  +А, +В, -С  при эом взвешивании А и В кладутся на весы, получаем: 1). +А = +В (равновесие) фальшивая – С,  2). ++А  и - +В Сокращаем знаки. ( А внизу фальшивая) В получает*. Я думаю, что принцип понятен из этого примера.

Лемма 2. Задача из 4 монет ( без знаков, но с «хорошей») решается в 2 взвешивания.

Заменим одну монету на качественную и положим по две монеты на каждую чашку. При взвешивании припишем монетам знаки. Получим 2 монеты с одним знаком и одну с другим. Это случай леммы 1.А если весы в равновесии, то снята фальшивая монета.

Теперь мы готовы к общему решению.

Положим на чашки весов по 4 монете. Если весы в равновесии, действует лемма 2. Если нет, то припишем монетам номера и знаки: на первой чашке +1, +2, +3, +4. На второй -5, -6, -7, -8. Подготовим монеты ко второму взвешиванию. Снимем три монеты, например +3, +4 и -5. Если при втором взвешивании весы будут в равновесии, то с этими тремя монетами разберемся по лемме 1. Остается на одной чашке весов +1, +2, добавим к ним хорошую монету *. На второй чашке остались -6, -7 и -8. Поменяем +1 и -6 местами. Получим на первой чашке -6, +2, *, на второй получим +1, -7, -8. Взвешиваем, т.е. приписываем знаки. Пусть первая чашка тяжелей, тогда на ней +-6, ++2, +*, на второй: -+1, --7, --8. Сокращаем знаки. На первой *, +2, *. На второй: *, -7, -8. Этот случай леммы 1. Пусть теперь первая чашка будет легче. Припишем знаки для этого случая. На первой чашке --6,-+2, -*. На второй: ++1, +-7,+-8. Сокращаем знаки для первой чашки -6, *, *, для второй +1, *, *. Задача решена.

РЕШЕНИЯ  АРТЕМА  КОРНЕЕВА

Ваши решения, вероятно, не хуже, чем решения Артема, но у него ответ более полный. Вот его письмо:

 Высылаю Вам два решения про 12 монет . (первое - красивое, второе - странное...)

1 решение

В качестве примера рассмотрим задачу, предлагавшуюся на теоретическом туре одной

из региональных олимпиад по информатике. Пусть у нас имеется 12 монет, одна из

которых фальшивая, по весу отличающаяся от остальных монет, причем неизвестно,

легче она или тяжелее. Требуется за три взвешивания определить номер фальшивой монеты

(попробуйте решить эту задачу самостоятельно и вы убедитесь, что это совсем не просто,

 а порой вообще кажется невозможным). Введем следующие обозначения. Знаком "+" будем обозначать монеты, которые во время текущего взвешивания следует положить на весы, причем, если монета на весах уже была, то на ту же самую чашу, на которой эта монета находилась во время своего предыдущего взвешивания. Знаком "-" будем обозначать монеты, которые следует переложить на противоположную чашу весов, по отношению к той, на которой они находились (каждая в отдельности), заметим, что если монета на весах еще не была, то знак "-" к ней применен быть не может. Наконец, знаком "0" - монеты, которые в очередном взвешивании не участвуют.

 Тогда, существует 14 различных способов пометки монет для трех взвешиваний:

1 2 3 4 5 6 7 8 9 10 11 12 13 14

+ + + + + + + + + 0 0 0 0 0 - первое взвешивание

+ + + - - - 0 0 0 + + + 0 0 - второе взвешивание

+ - 0 + - 0 + - 0 + - 0 + 0 - третье взвешивание

Из полученной таблицы вычеркнем 2 столбца так, чтобы в каждой из трех строк количество ненулевых элементов оказалось четным (ведь мы не можем во время одного взвешивания положить на две чаши весов нечетное число монет). Это могут быть, например, столбцы 4 и 14. Теперь будем взвешивать 12 монет так, как это записано в оставшихся 12 столбцах. То есть, в первом взвешивании будут участвовать 8 произвольных монет, во втором - три монеты следует с весов  убрать, две - переложить на противоположные по отношению к первому взвешиванию чаши весов и три монеты положить на весы впервые (на свободные места так, чтобы на каждой из чаш

 вновь оказалось по 4 монеты). Согласно схеме проведем и третье взвешивание, опять

 располагая на каждой чаше весов по 4 монеты. Результат каждого взвешивания в отдельности никак не анализируется, а просто записывается. При этом равновесие на весах всегда кодируется нулем, впервые возникшее неравновесное состояние - знаком плюс, если при следующем взвешивании весы отклонятся от равновесия в ту же самую сторону, то результат такого взвешивания также кодируется плюсом, а если в другую сторону - то минусом. Например, записи "=<<" и "=>>" кодируются как "0++", а записи "<=>" и ">=<" - как "+0-". Так как мы не знаем, легче или тяжелее остальных монет окажется фальшивая, то нам важно как изменялось состояние весов

 от взвешивания к взвешиванию, а не то какая именно чаша оказывалась тяжелее, а какая легче.

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

       Ею оказывается та, которой соответствует такой же столбец в таблице, как и закодированный нами результат трех взвешиваний. Для первого из примеров это монета, которая участвовала во взвешиваниях по схеме, указанной в 10-м столбце таблицы, а для второго - в 8-м.

        В самом деле, состояние весов в нашей задаче меняется в зависимости от того, где оказывается фальшивая монета во время каждого из взвешиваний. Поэтому монета, "поведение" которой согласуется с записанным результатом взвешиваний, такой результат и определяет.

Анализ таблицы показывает, что эту задачу можно решить не только для 12, но и для 13 монет.

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

 Для произвольного числа монет N>2 количество взвешиваний при определяется

 по формуле log3(2*N + 1) (за одно взвешивание задача не разрешима ни для какого количества монет!!!), но подход к решению задачи при этом не изменится.

  2 решение

Данное решение представлено в книге Мартина Гарднера "Математические

досуги". Сначала запишите все числа от 1 до 12 в троичной системе.

Замените в каждом числе цифру 2 на 0, а 0 на 2 и запищите рядом результат.

У вас получится три столбца чисел:

1  001 221

2  002 220

3  010 212

4  011 211

5  012 210

6  020 202

7  021 201

8  022 200

9  100 122

10 101 121

11 102 120

12 110 112

  Внимательно изучив эти числа, вы обнаружите все числа, в которых

встречаются сочетания 01, 12, 20. Каждой из двенадцати монет поставим в

соответствие одно из этих чисел.

  При первом взвешивании на левую чашу весов кладем четыре монеты,

обозначенные числами, которые начинаются с 0, а на правую чашу весов кладем

те четыре монеты, которым соответствуют числа, начинающиеся с 2. Если монеты

уравновесят друг друга, вы можете утверждать, что число, которое отвечает

фальшивой монете, начинается с 1. Если перевесит левая чашка, то искомое

число начинается с 0, а если правая - то с 2.

  Взвешивая монеты второй раз, их надо распределять в зависимости от средней

цифры. Если в центре стоит 0, монета кладется на левую чашу, если 2 - на

правую. Вторая цифра числа, обозначающего фальшивую монету, определяется

точно так же, как определялась его первая цифра при первом взвешивании.

  Производя последнее взвешивание, вы кладете налево те монеты, которые

обозначены числами, оканчивающимися на 0, а монеты, соответствующие числам,

имеющим на конце 2, вы кладете на правую чащу весов. Таким образом вы

узнаете последнюю цифру нужного вам числа.

По поводу 27 монет, то тут все просто:

  3

3   = 27

То есть 1-е взвешивание:

Три кучки по 9 - взвешиваем 1-ую и 2-ую и, есил =, то монета в 3-ей, если 1> то в 1-ой , а если  1< то во 2-ой

Три кучки по 3 - взвешиваем 1-ую и 2-ую и, есил =, то монета в 3-ей, если 1> то в 1-ой , а если  1< то во 2-ой

Три монеты - взвешиваем 1-ую и 2-ую и, есил =, то монета № 3-ей, если 1> то № 1 , а если  1< то № 2

С уважением. Корнеев Артем

Читайте, думайте, пишите, ТОМИ

mailto:tomi_magic@mail.ru