Задача Второй Мировой
Еще известная задача такого уровня: (Возможно это легенда, но очень уж красивая)
Во времена Второй Мировой Войны, английские ученые подбросили немецким ученым, чтобы они не решали военные проблемы, а решали головоломки, следующую логическую задачу.
Кладоискатели нашли клад и записку в которой было написано: В этих 20 мешках с золотыми монетами есть один мешок с фальшивыми монетами. Известно, что фальшивая монета в два раза тяжелее настоящей.
Задача:
Как при помощи одного взвешивания определить в каком мешке находятся фальшивые монеты?
Примечание: взвешиванием называется тот момент, когда весы, типа коромысла, станут горизонтально, показывая, что на правой стороне весов и на левой стороне одинаковый вес.
И еще: англичане приделали приписку к задаче, что они потратили 10 тысяч человеко-часов для решения этой задачи.
Ответ: Итак, берем из первого мешка 2 монеты, из второго - 4, из третьего - 6 и т.д. Эту кучу монет бросаем на одну чашу весов, после чего уравновешиваем весы, насыпая на вторую чашу монеты из какого-нибудь одного, например первого мешка.
Если бы все монеты были настоящими, то чаша 1 весила бы 420 у.е. Но там-то у нас 2*х фальшивых монет, поэтому она весит 420+2*х у.е.
Предположим, что мешок 1, которым мы уравновешивали весы, содержит настоящие монеты, тогда количество монет, истраченных на равновесие, будет где-то между 422 и 460. Нам остаётся только найти х: х = (кол-во понадобившихся монет - 420)/2
Если же мешок, монетами из которого мы уравновешиваем весы, оказался фальшивым, то равновесие будет достигнуто где-то на между 211 и 230 монетами. Естественно мы тогда поймём, что что-то здесь не так ;-)
Рейтинг: -21
Комментарии:
Бизон, 2008-08-17
Берем из каждого мешка по 2 монеты. Кладем их на чашу №1. Выходит 20*2 = 40 монет из которых 2 фальшивых. Т.е. вес их будет составлять 42 у.е. Потом на чашу №2 будет класть с каждого мешка по 21 монете. Если весы взвесились, то монеты фальшивые, если нет, то берем со следущего, пока их не найдем... Вроди правильно и легче... ;-)Предварительно надо пометить, какая монета из какого мешка, иначе придется взвешивать сами мешки вместо монет.Берем из каждого мешка по одной монете. Раскладываем на весах по 10 штук. Одна чаша перевесит, т.к. она тяжелее на одну золотую монету. Назовем эту чашу тяжелой. Затем, снимаем с каждой чаши одновременно по одной монете. Получается, что равновесие достигнется,когда с тяжелой чаши уберут фальшивую монету.Дима, 2009-08-14
смотри "мешки с золотом"юрицт, 2009-11-10
Вариант Бориса - зачёт (мин. ресурсов и времени).
Я решал так:
На первую чашу ложем 2 монеты из первого мешка (предположение – монеты в первом мешке настоящие). Потом на вторую чашу по очереди ложем монету из 2-го, вынимаем, следующую и т.д. Пока весы не уровняются (если фальшивые монеты в мешках со 2 по 20). Если равновесие не достигнуто – фальшивые монеты в первом мешке.
nickusha, 2009-11-16
ну да,только выкладывать не Х2 а 1,2,3,4,5...и т.д.,вес получается 210+к,где к-номер мешка с фальшивыми монетами.
уравновешиваем монетами из первого мешка.если в нем монеты фальшивые,то 210 из первого мешка весят 420,и они перевесят 211 на другой чаше(ну,если надо строго соответствовать условию,можно накидать еще 209 монет из любого другого мешка для равновесия),а если настоящие,то мы добавим к 210-то монетам еще к настоящих.
На счет 10 тысяч человеко часов сильное преувеличение
zx, 2009-11-18
тож решил,но больше понравился вариант Бориса.
А в ответе используется слишком много монет(может в мешках было по 10 монет-тогда как в ответе задачу уже не решить).ПоТёмкин, 2010-01-13
Тупость. Не сказано было, что можно доставать монеты. Имелось ввиду взвешивать мешки. Бред. 100 минусов поставил бы.Пекло Ирина, 2010-01-24
По-моему есть решение проще, если учесть, что в условии сказано- взвешиванием считается, когда весы уравновешены. Берем по 10 мешков на каждую чашу. Понятно, что равновесия не будет, т.к.чаша с мешком с фальшивыми монетами перевесит и это не считается взвешиванием. Убираем мешки с чаши, которая легче, т.к.там настоящие монеты. Оставшиеся 10 мешков делим пополам и взвешиваем, опять более легкие мешки откладываем. Осталось 5 мешков. Берем произвольно по 2 мешка на чашу. Если чаши уравновешены - значит в них монеты настоящие и отложенный мешок фальшивый. Если же нет то с более тяжелой чаши 2 мешка раскладываем по чашам и тогда более тяжелая чаша и есть искомая.Snake, 2010-06-09
Stara9 zada4aПри такой формулировке задача решается так - в лоб.
Берем две монеты - из первого и из второго мешка, кладем их на правую чашу - и весы выходят из равновесия, "по умолчанию".
Если они настоящие, то вес справа равен 2 (случай А), если среди них одна фальшивая - то 3 (случай Б).
На левую чашу кладем по очереди по одной монете из каждого мешка, затем убираем. В случае А у нас на левой чаше происходит следующее: если монета настоящая, то ее вес - 1, и правая все равно перевешивает (1<2), взвешивание еще не состоялось. А если она фальшивая (рано или поздно такая попадется, по условию задачи), то ее вес равен 2, и весы уравниваются (2=2). Монета найдена, взвешивание ровно одно.
В случае же Б у нас все монеты - настоящие, вес слева равен 1 (1<3). То есть, если мы все монеты перебрали, но равновесие не наступило, то фальшивка - одна из первых двух монет. И взвешивание еще не состоялось (!)
Оставляем одну монету справа, а вторую перекладываем на пустую левую чашку. Перевесившая - фальшивая, причем взвешивание - не состоялось вообще (!). Для пущей важности можно положить любую из 18 монет на легкую чашку, чтобы удостовериться, что весы в равновесии.
Итог - задача решена, и в полном согласии с ее условием.
Что касается претензий, что это некорректно: по идеологии классических задач на взвешивание проделано 18 или 19 взвешиваний (где "взвешивание" - установка на каждую чашу весов некого количества монет, наблюдения и записи в "журнал" - Л>П, Л=П или Л<П), то отвечу, что канонический ответ подразумевает не менее 211 взвешиваний. Конечно, все эти монеты "непрерывно" насыпаются на чашу весов. Но в условии нет ни открытого разрешения так делать, ни открытого запрета делать, как описано мной.
Собственно, это означает, что условие надо формулировать (несмотря на возраст задачи) очень внимательно.sw, 2010-09-15
В задаче указано условие - "Задача:
Как при помощи ОДНОГО взвешивания определить в каком мешке находятся фальшивые монеты?"
В связи с этим понятен смысл о 10к чел/часах. Запуталинах
По мне некорректнот_т, 2011-12-28
пометить мешки, разделить по 10 мешков на две группы. из первой группы брать от каждого мешка по нескольку монет: с 1-го одну монету, с 2-го 2 монеты и т.д. аналогично поступить и со вторым мешком. допустим, вес каждой настоящей монеты 2 гр. тогда:
2+4+6+8+10+12+14+16+18+20=110
взвешиваем два мешка из отборных монет. если один мешок тяжелее другого на 2 гр. то фальшивые в той группе в 1-м мешке, если на 4 гр. то во 2-м мешке и т.д.
