нее.. нам ее на первом курсе задал бородавка (лабы вел по вычтеху), кто говорит программу напишет, чтобы она монетку определяла, тому зачет по лабам сразу и освобождение на весь семестр.. пара человек в надежде на халяву взялись за это дело.. в итоге они весь семестр тока пытались решить эту задачу.. а потом уже после окончания инста на одной пьянке парнишка один торжественно объявил, что на днях нашел решение.. ну мну это заело, и я попарившись тоже ее решил..)
Вот уже две недели продолжалась эта эпопея, даже невнимательно читающие успели за это время, пожалуй, выучить задачу наизусть (но это не помешает мне и в этих комментариях выложить ее условие на память, ибо остальные топики с нею удалены). В итоге все же определились три победителя, три человека, которых можно назвать умнейшими людьми на моем дайре. Как я уже сказала, состав тройки шокирует - нет ни одного из моих старых ПЧ, а только самые новые. Итак, та-дам!!!!
I место
он не первый дал ответ на задачу, однако так как он появился среди моих ПЧ только после решения этой задачи, я не могу сослаться, что он ее долго решал, вообще судить, кто решал дольше, а кто нет, невозможно, поэтому сужу ислючительно по тому, каким образом была решена задача. Ну а тут уж бесспорно - у Arren наиболее изящное решение (ну вы уже догадались, что решение это идентично моему... какая ж я сволочь ))) )
II место
Решение этого моего ПЧ не столь просто и изящно, выглядит достаточно случайно, но ведь главное решить, а уж прочее - пустяки. Так что первые два места стоят очень близко.
III место
Ну тут обошлось не без моей помощи, мне три раза приходилось разочаровывать нашего друга, но никаких подсказок я ему не делала (разве что сказала, что первая половина решения правильное), поэтому совершенно уверена, что и без меня он бы решил задачу.
В комментариях приведено не только решение, но и последняя редакция побробного описания хода мысли, строгой логики, которая должна однозначно привести к моему варианту решения. Обратите внимание, что строгое логическое рассуждение, приводящее к решению задачи - это композиция, это искусство, критерием удачности которого также является эстетика. Учитесь, товарищи, и в следующий раз будете раскусывать такие задачи, как орехи )))
Ответ человека, задавшего мне эту задачку,
на вопрос, сам ли он ее придумал
на вопрос, сам ли он ее придумал
Итак, дорогие товарищи,
истерика по поводу задачи объявляется закрытой!
истерика по поводу задачи объявляется закрытой!
Вот уже две недели продолжалась эта эпопея, даже невнимательно читающие успели за это время, пожалуй, выучить задачу наизусть (но это не помешает мне и в этих комментариях выложить ее условие на память, ибо остальные топики с нею удалены). В итоге все же определились три победителя, три человека, которых можно назвать умнейшими людьми на моем дайре. Как я уже сказала, состав тройки шокирует - нет ни одного из моих старых ПЧ, а только самые новые. Итак, та-дам!!!!
I место
Arren
он не первый дал ответ на задачу, однако так как он появился среди моих ПЧ только после решения этой задачи, я не могу сослаться, что он ее долго решал, вообще судить, кто решал дольше, а кто нет, невозможно, поэтому сужу ислючительно по тому, каким образом была решена задача. Ну а тут уж бесспорно - у Arren наиболее изящное решение (ну вы уже догадались, что решение это идентично моему... какая ж я сволочь ))) )
II место
Aлекс К
Решение этого моего ПЧ не столь просто и изящно, выглядит достаточно случайно, но ведь главное решить, а уж прочее - пустяки. Так что первые два места стоят очень близко.
III место
Merfanef
Ну тут обошлось не без моей помощи, мне три раза приходилось разочаровывать нашего друга, но никаких подсказок я ему не делала (разве что сказала, что первая половина решения правильное), поэтому совершенно уверена, что и без меня он бы решил задачу.
В комментариях приведено не только решение, но и последняя редакция побробного описания хода мысли, строгой логики, которая должна однозначно привести к моему варианту решения. Обратите внимание, что строгое логическое рассуждение, приводящее к решению задачи - это композиция, это искусство, критерием удачности которого также является эстетика. Учитесь, товарищи, и в следующий раз будете раскусывать такие задачи, как орехи )))
-
-
12.06.2006 в 01:21-
-
12.06.2006 в 02:01-
-
12.06.2006 в 03:31Итак задача (еще раз):
Имеется 12 монет, из них одна фальшивая, отличается
по весу от остальных (тяжелее или легче, нам это неизвестно)..
ну и естественно весы с двумя чашками без гирек. Нужно найти алгоритм,
позволяющий за 3 взвешивания точно определить фальшивую монету.
Даю полное решение, оно длинное, но только потому, что по ходу я подробно расписываю логику действий:
Обычно все попадаются на одну и ту же удочку задачи - кажется, что наиболее логично положить поровну 12 монеток на весы - по шесть в каждой, и отсюда отталкиваться, но ведь при этом система оценки весов будет бинарна - то есть либо одна чаша перевешивает, либо другая - да/нет, 0/1 называется. И действительно, если бы система была бинарна максимальное число, которое можно этими да/нет записать (описать), равно 8 (2^3), а не 12. А на самом-то деле, надо искать такой алгоритм, чтобы при каждом ходу у вас было три варианта (нумеруем их сразу - 1, 2, 3), различающихся по результатам - либо обе равны, либо первая чаша легче, либо первая чаша тяжелее, причем все монетки надо стараться распределять именно между этими тремя "оценками" равномерно, так, чтобы при разном исходе была разная информация, тогда у вас будет аж 27 вариантов. Так вот решение начинается с того, что 12 монет разделяются на три равные кучки - две кучки на тяжелее/легче, одна на равновесие. (далее надо будет тоже так хитро делать, чтобы монеты распределялись на три одинаковые кучки)
Разбираем случаи:
1. равновесие. Значит фальшивка сидит в третьей, отложенной кучке. Тогда берем две из этой кучки, кладем по одной на чаши.
1.1 опять равновесие - значит монетка наша в тех двух, что мы пока еще не трогали, тогда с одной чаши весов снимаем монетку, и заменяем на одну из тех, которые еще не клали
1.1.1 и снова равновесие - значит фальшивка та единственная, которую еще не клали
1.1.2/3 - отклонение весов (через слеш показываю, что тут нам не важно, какая чаша тяжелее, какая легче) - фальшивка та, которую только что положили.
возвращаемся ко второму ходу:
1.2/3 - отклонение весов – значит, фальшива одна из этих двух монеток, какая именно? проверяем, опять же заменив одну из монеток.
1.2/3.1 - равновесие - фальшива та, которую только что убрали
1.2/3.2/3 - снова отклонение - фальшива та, которую оставили.
Теперь случаи, когда фальшивка среди наших восьми. Тут есть два равнозначных варианта - либо в перевесившей чаше одна из монеток фальшива, причем более тяжелая (все эти монетки мы подозреваем в фальшивости и одновременно в «тяжелости», далее будем называть их «т»), либо на противоположной чаше фальшивка, причем легкая (по аналогии будем называть их «л»)
Как же быть тут? Я уже сказала, что бинарность в нашей работе недопустима, а значит делим опять на три кучки. Многие решающие снова хотели делить на равные кучки, а для этого число монеток им надо было довести до девяти за счет одной уже не вызывающей подозрения ("эталонной"). А ведь можно вполне обойтись и нашими восемью. Теперь же нам надо за второй ход методом отсева выделить НЕ БОЛЕЕ трех подозрительных монет, так как за последний ход МАКСИМУМ именно из трех монет сможем однозначно определить нужную (когда известно в чем их подозревать, а это мы уже знаем после первого хода). Значит нам вплоне допустимо, чтобы в одной кучке было не три, а две монетки.
Каков же состав этих трех кучек при восьми монетах? Понятно, что так как на весах должно быть четное количество монет, то в отложенной кучке тоже получится четное. Причем оно не больше трех, а значит это число – 2. И не важно, какие именно у нас будут монетки тут – "лл", "лт", или "тт", ведь в случае, если при втором взвешивании будет равновесие, мы за последний ход с легкостью определим фальшивку. Таким образом состав третьей кучки зависит от того, как нам удобнее обойтись с составами на чашах.
А вот с составом чаш сложнее – многие начинают распределение по чашам методом тыка, и не найдя случайным образом удобного решения, прибегают к эталонным монеткам, и придумывают еще более сложные комбинации.
А тут надо рассуждать. После второго взвешивания сохранят подозрительность те монетки, которые при наших маневрах между взвешиваниями «не поменяют знак своей подозрительности» - то есть остаются подозрительными те «т», которые и при втором взвешивании волею судьбы оказались на перевесившей чаше и те «л», которые будут на противоположной чаше, логично?. И вот таких «не поменявших знак» должно быть при любом раскладе не больше трех. А сейчас мы гипотетически взвесим по три монеты на весах, даже еще не определив, какие монеты где будут лежать. Мы взвесили, и одна чаша перевесила. ВОПРОС, какие монеты лежат в этой чаше, если в условии сказано, что после данного взвешивания у нас останется максимум три подозрительных монеты? Красивый выбор вопроса, очень эффективный, простите за хвастовство. Явно, что три «т» на "тяжелой" мы допустить не можем, ибо на противоположных весах будет хотя бы две «л», то есть у нас сохранится аж пять подозрительных монеток. А если у нас на перевесившей будет две «т» и одна «л»? Ага, значит на этой чаше у нас уже две подозрительных монеты, и тогда на противоположной чаше надо допустить не более одной, это возможно? Да естественно возможно в том случае, если на чашах будет симметрия, если там тоже будет две «т» и одна «л». В этом случае, какая бы чаша ни перевесила (ведь у нас симметрия!) остается две «т» и одна «л». Очевидно, что при сравнении двух «т» на третьем ходу мы получим однозначный ответ!!! Итак решение очевидно, на чашах должно быть либо по две «т» и одной «л», либо по две «л» и одной «т». И куда бы ни перевесили весы у нас всегда выделится по три подозрительных монетки, две из которых будут одного знака, и сравнивая их, мы определим фальшивку. В случае же равновесия у нас в одном случае будет две «л», в другом – две «т», и тут еще тривиальнее!
И вы скажете, что это не композиция? Бетховен отдыхал! )))
-
-
13.06.2006 в 22:16Думаю все быстро догадаются как это сделать...
-
-
13.06.2006 в 23:56-
-
14.06.2006 в 01:01Разбираем случаи: 1. равновесие. Значит фальшивка сидит в третьей, отложенной кучке. Тогда берем две из этой кучки, кладем по одной на чаши. 1.1 опять равновесие - значит монетка наша в тех двух, что мы пока еще не трогали, тогда с одной чаши весов снимаем монетку, и заменяем на одну из тех, которые еще не клали1.1.1 и снова равновесие - значит фальшивка та единственная, которую еще не клали1.1.2/3 - отклонение весов (через слеш показываю, что тут нам не важно, какая чаша тяжелее, какая легче) - фальшивка та, которую только что положили.возвращаемся ко второму ходу:
И не важно, какие именно у нас будут монетки тут – "лл", "лт", или "тт", ведь в случае, если при втором взвешивании будет равновесие, мы за последний ход с легкостью определим фальшивку.
в случае, если при втором взвешивании будет равновесие, мы за последний ход с легкостью определим фальшивку.
Если взять "лт", то не узнаем фальшивка легче или тяжелее
-
-
14.06.2006 в 01:07-
-
14.06.2006 в 04:33Правда? То есть если мы "л" (например) сравним с любой из тех десяти, которые мы уже освободили от подозрений за первые два хода, то мы не узнаем, является ли она фальшивкой, ПРИЧЕМ более ЛЕГКОЙ, или является ли фальшивкой "т", ПРИЧЕМ более ТЯЖЕЛОЙ???? Нет, на нервах в данном случае я пока играть не планировала.
-
-
15.06.2006 в 00:09А на это ты согласилась, если не ответила...
Это не так!
Разбираем случаи: 1. равновесие. Значит фальшивка сидит в третьей, отложенной кучке. Тогда берем две из этой кучки, кладем по одной на чаши. 1.1 опять равновесие - значит монетка наша в тех двух, что мы пока еще не трогали, тогда с одной чаши весов снимаем монетку, и заменяем на одну из тех, которые еще не клали1.1.1 и снова равновесие - значит фальшивка та единственная, которую еще не клали1.1.2/3 - отклонение весов (через слеш показываю, что тут нам не важно, какая чаша тяжелее, какая легче) - фальшивка та, которую только что положили.возвращаемся ко второму ходу:
Тогда это утверждение неверно
Cara во всех наших решениях можно однозначно сказать, тяжелее монетка или легче
Или я неправ..?
-
-
15.06.2006 в 01:04А зачем ты это хотел сказать? Где в условии сказано, что мы не должны привлекать те монетки, которые уже проверили? Нам дали 12 монеток и ими мы в три хода оперируем, какие проблемы-то? К чему ты вообще указал мне на вот это в контексте определения веса фальшивки?
А на это ты согласилась, если не ответила...
Да нет, в первый раз я вообще просто не поняла, к чему ты перекопировал этот огромный кусок текста. Вообще это в твоем репертуаре просто копировать то, что уже сказано и не позволять себе труда хотя бы комментировать - к чему ты это снова показываешь собеседнику.
Что ж, на этот раз перечитала и поняла, что вот этим огромным куском текста ты мне хотел указать всего лишь на случай 1.1.1.
Да, действительно, я не обратила внимание на этот случай, но он единственный из нескольких десятков случаев в задаче, когда знак отклонения монетки невозможно определить за три взвешивания моим методом.
Ну что ж, если требуется еще и определения знака, то придумать способ очень легко. Взвесим три монетки а четвертая будет эталонной, тогда у нас будет либо тт - лэ, либо лл - тэ, либо равновесие. В первом случае сравниваем две "т", во втором - две "л", в третьем сравниваем оставшуюся невзвешенной с эталонной. Так сойдет?
-
-
15.06.2006 в 14:32-
-
15.06.2006 в 18:22-
-
15.06.2006 в 18:23