Тема: «Задачи на взвешивание».
Цель: Развивать логическое мышление, внимание, вырабатывать собственную систему эвристических приёмов, позволяющих решать незнакомые задачи, научить решать данный тип задач наиболее рациональным способом.
Решение задач по теме.
1. Имеются чашечные часы без гирь и две монеты, одна из которых фальшивая, причём легче другой. Требуется выявить фальшивую монету.
2. Имеются чашечные весы без гирь и три монеты, одна из которых фальшивая, причём легче другой. Требуется выявить фальшивую монету.
3. Имеется четыре одинаковых по виду монеты, одна из которых фальшивая, легче других. Требуется определить фальшивую монету. Какое минимальное число взвешиваний потребуется?
4. Имеется 16кг муки и несколько одинаковых по весу пустых мешков. Имеются весы, но гирь нет. Как, не имея гирь, взвесить 8кг, 4кг, 12кг, 14кг?
5. Из 4 внешне одинаковых монет 2 весят по 10г, а две другие - по 9г. Имеются чашечные весы со стрелкой, показывающей разность масс грузов, положенных на чашки. Как за одно взвешивание найти хотя бы одну десятиграммовую монету?
Дополнительные задачи.
6. В пакете 9кг крупы. Как при помощи чашечных весов и одной 200г гири отвесить 2кг крупы, если разрешается сделать только три взвешивания?
7.Есть 5 монет достоинством 1, 2, 3, 5, 10талеров. Четыре из них - настоящие, их вес в граммах равен достоинству, а одна фальшивая, её вес в граммах не равен её достоинству. Как, используя только чашечные весы без гирь, найти фальшивую монету?
8. Имеется 10 мешков монет. В девяти мешках монеты настоящие (по 10гр.), а водном - фальшивые (по11 гр). Одним взвешиванием определите, в каком мешке фальшивые монеты. Как это сделать?
Решение.
5. Положим на левую чашу весов две монеты, а на правую одну. Возможны 4 случая, показанные в таблице ниже:
| Слева | Справа | Оставшаяся монета | Показания стрелки |
| 10+10 | |||
| 10+9 | 10 | ||
| 10+9 | 10 | ||
| 9+9 | 10 | 10 |
Таким образом, по показаниям стрелки мы можем однозначно определить, с каким из четырёх возможных случаев мы имеем дело. Осталось заметить, что в каждом из этих случаев нужная монета без труда находится (отмечено в таблице жирным шрифтом)
6. На столе лежит десять пронумерованных шляп. В каждой шляпе лежит по десять золотых монет. В одной из шляп находятся фальшивые монеты. Настоящая монета весит 10 граммов, а поддельная только 9. В помощь даны весы со шкалой в граммах. Как определить в какой из шляп находятся фальшивые монеты, используя весы только для одного взвешивания? Весы могут взвешивать не более 750 грамм.
Ответ: Легко! Из первой шляпы берем 1 монету, из второй - 2, из третьей - 3 и т.д. Все это взвешиваем и отнимаем результат от идеального веса (в нашем случае 55*10=550 грамм). Получившееся число будет совпадать с номером шляпы с фальшивыми монетами.
7. Имеется 13 монет, из них ровно одна фальшивая, причем неизвестно, легче она настоящих или тяжелее. Требуется найти эту монету за три взвешивания. Весы - стандартные для задач этого типа: две чашечки без гирь.
Ответ: Отложим в сторону тринадцатую монету, а остальные обозначим следующим образом: FAKE MIND CLOT. Теперь взвешиваем одну четверку против другой (буквы обозначают монеты, входящие в каждую четверку): MA DO - LIKE, ME TO - FIND, FAKE - COIN. Теперь совершенно просто найти фальшивую монету, если она входит в эти двенадцать монет. К примеру, если результаты взвешивания были: слева легче, равно, слева легче, то фальшивой может быть только монета "A", которая легче других. А что если фальшивой окажется все-таки отложенная нами, тринадцатая монета? Все очень просто: в этом случае при всех трёх взвешиваниях весы будут сбалансированы. К сожалению, в этом случае нам не узнать легче или тяжелее тринадцатая монета, но в условии такого требования и не было.
8. У барона Мюнхгаузена есть 8 внешне одинаковых гирек весом 1 г, 2 г, 3 г, ..., 8 г. Он помнит, какая из гирек, сколько весит, но граф Склероз ему не верит. Сможет ли барон провести одно взвешивание на чашечных весах, в результате которого будет однозначно установлен вес хотя бы одной из гирь?
Ответ: Да. 7+8 = 1+2+3+4+5, остается 6.
9.В аптеку поступило сильнодействующее лекарство - 8 упаковок по 150 таблеток. Следом пришло сообщение, что в этой партии есть несколько упаковок с бракованными таблетками - их вес на 1 мг больше нормальной дозы. Как за одно взвешивание выявить все упаковки с бракованными таблетками? Упаковки можно вскрывать.
Ответ: Следует учинить непересекающиеся подмножества таблеток от разных упаковок: взять из первой упаковки одну таблетку, из второй - две, из третьей - четыре, из четвёртой - восемь, из пятой - 16, из шестой - 32, из седьмой - 64, из восьмой - 128. Всё это взвесить. Вычесть из полученного веса идеальный вес (идеальный вес каждой таблетки известен из документации, но можно обойтись и без него - подумайте как). Полученный излишек веса (он уже нормализован за счёт единичного излишка веса каждой таблетки) перевести в двоичный вид (ведь мы сформировали подмножества по двоичному закону). В этом числе номера разрядов, равные единице, и будут показывать номера бракованных упаковок.
10. Среди 101 одинаковых по виду монет одна фальшивая, отличающаяся по весу. Как с помощью чашечных весов без гирь за два взвешивания определить, легче или тяжелее фальшивая монета? Hаходить фальшивую монету не требуется.
Ответ: Взвешиваешь 50 и 50 монет: 1) Равенство: берем оставшуюся монету и ставим ее в левую кучку вместо одной из имеющихся там
1.1 Левая кучка тяжелее => фальшивая монета тяжелее
1.2 Левая кучка легче => фальшивая монета легче
2) Hеpавенство: берем более тяжелую кучку и разбиваем ее на две кучки по 25 монет.
2.1 Вес кучек одинаковый => фальшивая монета легче
2.2 Вес кучек неодинаковый => фальшивая монета тяжелее.
11. Как развесить 20 фунтов чая, в 10 коробок по 2 фунта в каждой за девять развесов имея только гири на 5 и на 9 фунтов? Используются обычные весы с двумя чашами - как у статуи Правосудия.
Ответ: 1) Hа одну чашу весов положить гирю в 5 фунтов, на другую гирю в 9 фунтов. Затем уравновесить весы, насыпав 4 фунта чая в чашу с гирей на 5 фунтов. 2) Убрать гири с чаш весов, оставить 4 фунта в одной чаше и уравновесить весы, насыпав во вторую еще 4 фунта. 3) Еще раз отвесить 4 фунта.
4) И еще раз 4 фунта. Таким образом, после четырех взвешиваний в остатке будет тоже 4 фунта. 5) Разделить 4 фунта пополам, уравновешивая чаши весов.
12. Эта история случилась давным-давно, еще во времена крестовых походов. Один из рыцарей был захвачен мусульманами в плен и предстал перед их предводителем - султаном Саладином, который объявил, что освободит пленника и его коня, если получит выкуп в 100 тысяч золотых монет. "О, великий Саладин, - обратился тогда к султану рыцарь, у которого за душой не было ни гроша, - ты лишаешь последней надежды. У меня на родине мудрому и находчивому пленнику дается шанс выйти на свободу. Если он решит заданную головоломку, его отпускают на все четыре стороны, если нет - сумма выкупа удваивается!"
"Да будет так, - ответил Саладин, и сам обожавший головоломки. - Слушай же. Тебе дадут двенадцать золотых монет и простые весы с двумя чашками, но без гирь. Одна из монет фальшивая, однако, неизвестно, легче она или тяжелее настоящих. Ты должен найти ее всего за три взвешивания. Не справишься с задачей до утра - пеняй на себя!" А вы смогли бы выкрутиться?
Ответ: Эта задача была блестяще разобрана К. Л. Стонгом в майском номере журнала Scientific American за 1955 год. Одно из ее решений (а их довольно много) связано с троичной системой. Сначала запишите все числа от 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, вы кладете на правую чащу весов. Таким образом, вы узнаете последнюю цифру нужного вам числа.
13. Имеется 8 с виду одинаковых монет. Одна из них фальшивая и известно, что она легче настоящей монеты. Как с помощью всего лишь двух взвешиваний найти фальшивую монету? В Вашем распоряжении только лабораторные весы, которые показывают только больше или меньше.
Ответ: Делим монеты на две равные кучки. Из каждой кучки берем по 3 монеты, кладем на весы и взвешиваем. Если вес одинаковый, то взвешиваем оставшиеся 1и 1 монеты и выявляем фальшивую (более легкую). Если же одна группа из трех монет легче другой, значит, там есть фальшивая монета. Оставляем более легкую группу из трех монет и кладем на весы 1и 1 и действуем по предыдущему алгоритму: если вес одинаков, значит фальшива третья, а если нет то та которая легче.
14. Имеется 100 серебряных монет разных размеров и 101 золотая монета также разных размеров. Если у одной монеты размер больше, чем у другой, то она и больше весит, но это верно только для монет, сделанных из одного и того же металла. Все монеты можно легко упорядочить по размерам на глаз. Отличить золота от серебра можно тоже. Как за 8 взвешиваний определить, какая монета из всех 201 штук занимает по весу ровно 101-е место? Все 201 монеты также различны по весу. Весы с двумя чашками, как обычно.
Ответ: Раскладываем в два ряда все монеты в порядке возрастания размера: золотые отдельно, серебряные отдельно. Пусть первая по счету в каждом ряду монета самая большая (и тяжелая). Среднюю по весу монету можно найти, последовательно взвешивая срединные монеты каждой из оставшихся линеек.
1) взвешиваем 51-ю золотую монету и 50-ю серебряную. Если первая тяжелее, то искомая монета находится где-то среди 52-101 золотой и 1-50 серебряной. Если легче, то искомая монета находится где-то среди 1-51 золотой и 51-100 серебряной. То есть, 51+50 монет. Остальные можно отложить.
2) взвешиваем опять срединные монеты. Так как число вариантов растет в геометрической прогрессии, буду рассматривать только итоги ;) Из 51+50 монет выбираем, сравниваем 25 и 26 монеты. Остается 26+25 монет.
3) Взвешиваем 13 и 13 монеты. Остается 13+13 или 13+12. Далее буду рассматривать только случай 13+13, 13+12 аналогично. 4) Взвешиваем 7 и 7. Остается 7+7. 5) Взвешиваем 4 и 3. Остается 4+3. 6) Здесь могу поподробнее, так как монет осталось мало, то пусть остались золотые монеты 1234 и серебряные ABC (все в порядке возрастания). Взвешиваем 2 и B. Если 2>B, то средняя монета какая-то из 34AB, если нет, то из 12C. Рассмотри первый случай. 7). Взвешиваем 3 и A. 8а). если 3 8б). если 3>A, то взвешиваем 4 и A. Какая больше, та и искомая.
15. Еще известная задача такого уровня: (Возможно это легенда, но очень уж красивая). Во времена второй Мировой Войны, английские ученые подбросили немецким ученым, чтобы они не решали военные проблемы, а решали головоломки, следующую логическую задачу. Кладоискатели нашли клад и записку, в которой было написано: В этих 20 мешках с золотыми монетами есть один мешок с фальшивыми монетами. Известно, что фальшивая монета в два раза тяжелее настоящей монеты.
Задача: Как при помощи одного взвешивания, определить в каком мешке находятся фальшивые монеты? Примечание. Взвешиванием называется тот момент, когда весы, типа коромысла, станут горизонтально, показывая, что на правой стороне весов и на левой стороне одинаковый вес. И еще: англичане приделали приписку к задаче, что они потратили 10 тысяч человеко-часов для решения этой задачи.
Ответ: Итак, берем из первого мешка 2 монеты, из второго - 4, из третьего - 6 и т.д. Эту кучу монет бросаем на одну чашу весов, после чего уравновешиваем весы, насыпая на вторую чашу монеты из какого-нибудь одного, например первого мешка.
Если бы все монеты были настоящими, то чаша 1 весила бы 420 у.е. Но там-то у нас 2*х фальшивых монет, поэтому она весит 420+2*х у.е.
Предположим, что мешок 1, которым мы уравновешивали весы, содержит настоящие монеты, тогда количество монет, истраченных на равновесие, будет где-то между 422 и 460. Нам остаётся только найти х: х = (кол-во понадобившихся монет - 420)/2. Если же мешок, монетами из которого мы уравновешиваем весы, оказался фальшивым, то равновесие будет достигнуто где-то на между 211 и 230 монетами. Естественно мы тогда поймём, что что-то здесь не так
16. Имеются 6 гирь весом 1, 2, 3, 4, 5 и 6 г. На них нанесена соответствующая маркировка. Однако есть основания считать, что при маркировке гирь допущена одна ошибка. Как при помощи двух взвешиваний на чашечных весах, на которых можно сравнить веса любых групп гирь, определить, верна ли имеющаяся на гирях маркировка?
Ответ: На одну чашу весов кладем гири, маркированные 1, 2 и 3 г., а на другую - 6 г. Равновесие означает, что ошибка в маркировке возможна лишь внутри групп 1-2-3 и 4-5. При втором взвешивании на одну чашу кладем гири 3 и 5 г., на другую - 6 и 1 г. Если первая чаша перевесила, то ошибки в маркировке нет.
17. Имеется 9 одинаковых монет, одна из которых фальшивая и по этой причине легче остальных. Мы располагаем двумя весами без гирь, позволяющими сравнивать по весу любые группы монет. Однако одни из имеющихся весов являются грубыми, на них нельзя отличить фальшивую монету от настоящей. Их точность не позволяет уловить разницу в весе. Зато другие весы точные. Но какие весы грубые, а какие точные - неизвестно. Как в этой ситуации с помощью трех взвешиваний определить фальшивую монету?
Ответ: Положим на весы №1 по четыре монеты на каждую чашку. Если одна группа монет перевесила, то остальное понятно - эти весы точные, и мы знаем 4 монеты, среди которых одна фальшивая. Пусть весы оказались в равновесии. Обозначим через А девятую монету и добавим к ней монеты В и С - по одной из каждой четверки. Оставшиеся две тройки монет положим на чаши весов №2. Худший вариант - вновь равновесие. Тогда на весах №2 сравниваем монеты В и С. В случае равновесия фальшивой будет монета А.
18. Среди 2000 внешне неразличимых шариков половина - алюминиевые, весом 10 г каждый, а вторая половина - дюралевые, весом 9.9 г каждый. Требуется выделить две кучки шариков так, чтобы количество шариков в кучках было одинаковым, а массы - разными. Каким наименьшим числом взвешиваний на чашечных весах без гирь это можно сделать?
Ответ: Два. Делим на кучи (1) 666, (2) 666, (3) 666 и (4) 2.
Взвешиваем (1)-(2), (2)-(3). Если в обоих случаях равенство, то оставшиеся 2 шарика разные.
19. Пять различных по весу предметов требуется расположить в порядке убывания их веса. Пользоваться можно только простейшими весами без гирь, которые позволяют лишь установить, какой из двух сравниваемых по весу предметов тяжелее. Как следует действовать, чтобы решить задачу оптимальным образом, то есть так, чтобы число взвешиваний было минимальным? Сколько взвешиваний придется при этом произвести?
Ответ: Первым взвешиванием сравним любые 2 из 5 данных предметов. Пусть A - более легкий, а B - более тяжелый предмет. Тогда результат первого взвешивания запишем в виде A<B. Читается: «A легче В». Затем сравним два других предмета и обозначим более легкий D а более тяжелый - E: D<E. Пятый предмет обозначим C. Третьим взвешиванием сравним предметы B и E. Обе возникающие здесь возможности приводят к аналогичным рассуждениям, поэтому мы ограничимся рассмотрением случая B<E. В итоге после трех взвешиваний мы знаем, что A<B<E и D<E. Четвертым взвешиванием сравним пятый предмет C с предметом B. Необходимо различать два случая: а) B<C; б) C<B. В первом случае (B<C) A<B<E, D<E и B<C. Сравним (для этого понадобится пятое взвешивание) предметы C и E. Здесь также необходимо различать два возможных случая: E<C или C<E. Если A<B<E<C, то место предмета D, более легкого, чем E, можно определить, сравнив A с D и B с D. Таким образом, для полного упорядочения пяти предметов по весу в этом случае необходимо произвести 7 взвешиваний.
В случае A<B<C<E для определения места D также достаточно произвести два взвешивания, а именно: сначала сравнить D с B, а затем в зависимости от результата взвешивания сравнить D либо с A либо с C. В итоге мы снова производим 7 взвешиваний. Во втором случае (C<B) A<B<E, C<B и D<E.
Сравним предметы A и C (пятое взвешивание). В обоих возможных случаях (A<C<B или C<A<B<E) для определения места предмета D, о котором уже известно, что он легче предмета E, достаточно двух взвешиваний. Следовательно, и в случае, когда C<B, семи взвешиваний достаточно, чтобы расположить предметы в порядке возрастания их веса. Поскольку мы исчерпали все возможные случаи, то доказательство на этом заканчивается
Приложение 16