Тема устарела (в устаревшие темы писать нельзя).

Количество сообщений: 117
Страница: <<первая <назад | 1 | 2 | 3 | 4 | 5

Разгадавшим - приз. 13.03.2010 17:43:53 rtr3 ↑ 26 монет. Первое деление на (9+3+1),(9+3+1) Соответвенно после первого взвешивания имеем правильные весы. К частям применяем метод рекурсивного спуска Hamstera 14.03.2010 04:31:27 Hamster ↑ Да, надо подобрать функцию, растущую быстрее экспоненты. 14.03.2010 09:56:35 rtr3 ↑   Hamster писал(а): Да, надо подобрать функцию, растущую быстрее экспоненты.   Всмысле подобрать? подойдет любая. ЗЫ Вопрос существует ли другой путь 17.03.2010 12:24:15 Миклуха-Маклай ↑ Я на приз не претендую :) Но когда известно, легче или тяжелее монета (и заведомо исправных весах) можно определить фальшивую монету из 3^n монет :) 17.03.2010 12:27:19 Миклуха-Маклай ↑ Легче или тяжелее фальшивая монета :) Заведомо исправные весы :) Берем 3 кучки по 27 монет.... 3 кучки по 9 3 кучки по 3 3 кучки по 1 :) 17.03.2010 12:39:20 Миклуха-Маклай ↑ И тогда при 54 на последнем шаге определяем правильные ли были весы :) 2 кучки по 1 - если равно - весы неправильные 3 кучки по 2 3 кучки по 6 3 кучки по 18 Итого 54 :) Может есть и более емкое решение :) 17.03.2010 13:03:53 Миклуха-Маклай ↑ Или взвешиваем сразу 2 по 27 и определяем правильные весы, или нет..., ага, значит в третьей кучке может быть... Ааа, лень решать :)... Так, на последнем шаге... Итого :) 2 кучки по 27 монет и одна кучка из 26 монет :) При 80 монетах мы на последнем шаге будем знать правильные весы, или нет :) Или на первом, что правильные :) 17.03.2010 13:10:54 Миклуха-Маклай ↑ При том, что известно легче или тяжелее фальшивая монета. Подводим итог: При 81 монете я скажу какая монета фальшивая и не смогу сказать на каких весах я это делал правильных или нет :) При 80 монетах я или скажу какая монета правильная и что весы правильные, или скажу, что весы неправильные и не смогу указать фальшивую монету. Но ведь задачи смены весов в процессе измерения на правильные не стояло? :) 17.03.2010 16:58:19 rtr3 ↑   Миклуха-Маклай писал(а): При 81 монете я скажу какая монета фальшивая и не смогу сказать на каких весах я это делал правильных или нет :) При 80 монетах я или скажу какая монета правильная и что весы правильные, или скажу, что весы неправильные и не смогу указать фальшивую монету. Но ведь задачи смены весов в процессе измерения на правильные не стояло? :)   Можно вопрос по твоему решению: Что делать если при взвешивании 2 кучек по 27 монет(мы ведб так начинаем) они оказываются равными у нас остается 3 взвешивания причем нам надо провести как минимум одно взвешивание по 27 монет на других весах, чтобы определить какие весы правильные? Или я неправильно понял? К тому же странно что из 81 монет мы можем извлечь всю инфу а из 80 можем и не извлечь. 18.03.2010 09:04:43 Миклуха-Маклай ↑ Я же не зря написал - при правильных весах Из 81 одной монеты, при двух весах... При неправильных весах мы вообще не сможем извлечь никакой информации :) Мы однозначно скажем - эта монета фальшивая... Если весы были неправильные - мы будем неправы и об этом не узнаем. Если весы правильные - может так получится что мы будем знать об этом, а может так - что и не будем знать :) Вероятность этого маленькая, но все же есть :) 18.03.2010 14:16:03 Миклуха-Маклай ↑ А, ну да... условие неправильно прочитал... 18.03.2010 15:02:58 Миклуха-Маклай ↑ Зато при 26 точно можно определить неправильные весы :) Просто поделив первое взвешивание по 13.... А за 3 взвешивания на правильных весах можно аж 27 определить... Что-то не верится мне, что максимум 27 :) 18.03.2010 16:35:46 studend ↑ Вариант на бонус-задачу:  20 монет Взвешиваем 9 и 9 на одних весах, потом их же на вторых весах. 2 лежат сбоку Теперь варианты: 1) Если одно из первых двух взвешиваний показало разницу, то имеем  знание правильных весов  и 9 монет, среди которых одна фальшивая. Остается 2 взвешивания, Взвешиваем 3 и 3 на правильных весах. Еще 3 лежат сбоку. По результату узнаем кучку из трех монет, одна из которых фальшивая. Взвесим на правильных же весах 1 и 1, еще 1 лежит сбоку. По результату определяем фальшивую монету. 2) если первые два взвешивания не показали разницы, то имеем 2 монеты, одна из которых фальшивая, и два взвешивания, но правильных весов мы не знаем. Взвешиваем 1 и 1 на одних весах, потом их же на вторых. По результату опять же определяем фальшивую монету и пра. 18.03.2010 16:53:43 Миклуха-Маклай ↑ :) Я ж написал выше :) 26 делим по 13 - взвешиваем... Есть разница - весы правильные и 13 монет... Нет разницы - весы неправильные и 26 монет на 3 взвешивания, а можно 27 :) Здесь уже нет необходимости увеличивать сущности... 18.03.2010 20:04:24 rtr3 ↑ Ну решение про 26 монет было высказано ранее   rtr3 писал(а): 26 монет. Первое деление на (9+3+1),(9+3+1) Соответвенно после первого взвешивания имеем правильные весы. К частям применяем метод рекурсивного спуска Hamstera   19.03.2010 00:45:45 studend ↑ нда... заплесневел у меня мозг, однако... тока-тока досоображал до 26... даже жалко, раньше ничего такой был мозг, сообразительный :)) Пока в интернет не зачастил :))) 19.03.2010 13:00:31 Олег ↑ 1 чашечные весы по своей конструкции таковы, что неисправные видно сразу: одна чашка перевешивает другую без груза. (Есть вариант затирания механизма, тогда надо чуть толкнуть чашки, и они уравновесятся в разном положении), то есть определение сломанных весов происходит без взвешивания. Итак, имеем определенные без взвешивания работающие весы. Дальше, делим количество монет на равные по количеству кучки и взвешиваем. Если мы делим на две равные кучки (при нечетности общего количества одну монету оставляем в стороне), то при равности обоих чаш весов фальшивая — та монета, что осталась лишней, если же какая-то чаша перевесила — делим ее содержимое пополам и взвешиваем опять. При таком подходе последнее взвешивание должно затрагивать три монеты (две на чашах весов, одна — в "запасе"). Предпоследнее — 7 монет (по три на чашах весов, одна — в запасе), второе — 15 монет, первое — 31 монету. Максимум для этого способа — 31 монета. Второй способ — делить все монеты на три равные кучки. При этом последнее взвешивание также должно охватить три монеты. Предпоследнее — 9 монет, второе — 27 монет, первое — 81 монету. Итак, 81 монету мы делим на три кучки, любые две взвешиваем. Если показатели равны, то фальшивка -- среди невзвешенных, если одна из чаш перевесила -- ее следует искать там. Затем кучку из 27 монет мы вновь делим на три, получаем 9 "подозрительных" монет, и их делим, а как найти фальшивку среди трех мы уже знаем. Теперь посмотрим, что будет, если разделить первоначальную кучу на четыре равные кучки. Взвешиваем любые две из них. Если они равны — обе отбрасываем, а оставшиеся делим на четыре кучки. Если одна больше -- оставляем только ее, делим на четыре кучки, а остальное отбрасываем (что легче, а мы не ищем легких путей, потому эту удачу рассматривать дальше не будем). Второе взвешивание — опять две кучки из четырех, третье, — две монеты на одной чаше, две — на другой, одна может быть в "запасе", если одна чаша перевесила -- снимаем с каждой чаши по монете, если стало равновесие, значит, фальшивая -- та, которая снята с перевешивавшей чаши, если перевес остался -- фальшивая лежит на чаше, что очевидно. Итак, максимум, который можно так взвесить — 20 монет. Любой комбинированный способ хуже, чем "тройной". Ответ: 81 монета.

Страница: <<первая <назад | 1 | 2 | 3 | 4 | 5

Вы не вошли в игру.