Рассылка закрыта
При закрытии подписчики были переданы в рассылку "Национальная и государственная безопасность" на которую и рекомендуем вам подписаться.
Вы можете найти рассылки сходной тематики в Каталоге рассылок.
Логические задачи на сообразительность
Информационный канал Subscribe.Ru
-*--------------------------------------------------------------------------
Логические задачи на сообразительность
[http://subscribe.ru/catalog/rest.interesting.logicpuzzles] http://
subscribe.ru/catalog/rest.interesting.logicpuzzles
+-------------------------------------------------------------------------+
| Логические задачи на сообразительность |
|-------------------------------------------------------------------------|
| Электронная рассылка |
|-------------------------------------------------------------------------|
| Здравствуйте, с вами Томи. Выпуск 13 |
| |
| |
| |
| ОТВЕТ ЗАДАЧИ С 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-ую и, есил =, то монета No 3-ей, если |
| 1> то No 1 , а если 1< то No 2 |
| |
| |
| |
| С уважением. Корнеев Артем |
| |
| |
| |
| |
| |
| Читайте, думайте, пишите, ТОМИ |
| |
| [mailto:tomi_magic@mail.ru] mailto:tomi_magic@mail.ru |
|-------------------------------------------------------------------------|
+-------------------------------------------------------------------------+
-*--------------------------------------------------------------------------
Отписаться: http://subscribe.ru/member/unsub?grp=rest.interesting.logicpuzzles&email=
http://subscribe.ru/ mailto:ask@subscribe.ru
|
| В избранное | ||
