?

Log in

No account? Create an account

Previous Entry | Next Entry

Легкая монета среди 10

old_surehand предлагает найти легкую монету среди 8 двумя взвешиваниями. Это нам слишком просто. Одну легкую монету среди 9 можно найти тем же способом. А вот как насчет 10? Если можно — то как, если нельзя — надо доказать.

Tags:

Comments

( 23 comments — Leave a comment )
matholimp
Jan. 17th, 2011 03:55 am (UTC)
Нельзя. Каждое взвешивание уменьшает неопределённость в 3 раза. Два взвешивания - в 9 раз. Так как монет больше, то обязательно останется случай, когда невозможно точно указать лёгкую.
(Anonymous)
Jan. 17th, 2011 03:58 am (UTC)
Правильнее сказать "не более чем в 3 раза".
fregimus
Jan. 17th, 2011 04:03 am (UTC)
Умозрительно мне тоже так кажется. Но хотелось бы более строго доказать.
matholimp
Jan. 17th, 2011 04:17 am (UTC)
Допустим кто-то изобрёл нужный алгоритм. Реализуем его.
В зависимости от результата первого взвешивания получаем 3 случая. В каждом из них по 3 подслучая. Всего 9 подслучаев на 10 монет. Принцип Дирихле!
fregimus
Jan. 17th, 2011 05:28 am (UTC)
Дирихле, да, он самый, спасибо. А я через количеством информации считал — некрасиво получилось.
ilanabendery
Jan. 17th, 2011 12:22 pm (UTC)
Я в свое время через количество информации считала и осталась удовлетворена, для такого тупаря, как я, это достаточно красиво ))
crocotiger
Jan. 17th, 2011 04:32 am (UTC)
Как ни раскладывать монетки, два взвешивания дают только 9 возможных результатов : ЛЛ, ЛР, ЛП, РЛ, РР, РП, ПЛ, ПР, ПП. (Где Л - левая чашка легче, Р - равно, П - правая.) Если монет больше девяти, обязательно будет результат, которому соответствует больше, чем одна монетка.
old_surehand
Jan. 17th, 2011 05:47 am (UTC)
Перед финальным взвешиванием должно оставатся не более 3 монет, при каждом взвешивании монеты можно разделить не более чем на 3 группы, поэтому количество взвешиваний должно быть кратно степени 3.
Т.e. минимальное количество взвешиваний n равно ближайшей степени в которую нужно возвести 3, чтобы полученное число было не меньше (больше или равно) количества монет: 3^(n-1) < количество монет < 3^n

(1 взвешивание - 3^1 = 3; 1-3 монеты.
2 взвешивания - 3^2 = 9; 4-9 монет
3 взвешивания - 3^3 = 27; 10-27 монет
4 взвешивания - 3^4 = 81; 28-81 монета
5 взвешиваний - 3^5 - 243; 82-243 монеты итд)

3^2 < 10 < 3^3; для 10 монет ближайшая большая степень тройки = 3 т.е. требуется не менее 3 взвешиваний. QED
brewbuilder
Jan. 17th, 2011 05:58 am (UTC)
Можно одним "взвешиванием":
Кладём половину монет на одну чашу, половину на другую.
Затем снимаем по одной монете с каждой чаши до тех пор,
по равновесие не восстановится.
fregimus
Jan. 17th, 2011 06:10 am (UTC)
Нет, одно взвешивание — это когда мы кладем монеты, отпускаем стрелку, смотрим, куда отклонилась. Каждая снятая пара монет — дополнительное взвешивание.
_winnie
Jan. 17th, 2011 08:40 am (UTC)
Спасибо, красивый "взлом" условий задачи :)
ext_55374
Jan. 17th, 2011 02:48 pm (UTC)
Намного интереснее другая задача: 13 монет, одна из них фальшивая, но не известно, легче она или тяжелее. Можно ли найти её за 3 взвешивания, и если можно, то как?
(Deleted comment)
darth_vasya
Jan. 17th, 2011 07:53 pm (UTC)
не известно, легче она или тяжелее
darth_vasya
Jan. 17th, 2011 07:54 pm (UTC)
(авторская офрография сохранена)
(Deleted comment)
ext_55374
Jan. 17th, 2011 10:12 pm (UTC)
В случае, если {1-5} < {6-10} возможны 10 равновероятных ситуаций, которые за 2 взвешивания не ловятся. Так что незачёт.
ext_55374
Jan. 17th, 2011 10:15 pm (UTC)
> Очевиден вектор (легче или тяжелее монета)

Вовсе неочевиден. Тяжелая монета может быть слева, лёгкая монета может быть справа.
ext_55374
Jan. 19th, 2011 01:54 pm (UTC)
Правильное решение: http://fregimus.livejournal.com/137464.html?thread=3644152 Там, кстати, есть момент 10 > 9, но ловится он за счёт того, что мы не всегда можем в конце концов узнать, тяжелее монета или легче.
ilanabendery
Jan. 18th, 2011 06:24 pm (UTC)
Мне, кажется, когда-то удавалось решить эту задачу для 12 монет, но сейчас я этот подвиг не повторю.
Но, насколько я помню, там важно при первом взвешивании не бухать всё на чашки, а оставить как можно больше в стороне, потому что при перевесе одной из чашек содержимое обеих оказывается под подозрением, то есть взвешивание всех монет сразу к ответу на главный вопрос почти не приближает.
Сейчас посчитала, вроде количество монет, которое кладется на каждую чашку на первом этапе, должно быть от двух до четырех, но какое лучше (вряд ли их должно быть две, а вот между тремя и четырьмя я сомневаюсь) и что потом со всем этим делать дальше, в упор не помню.
Возможно, надо как-то поиграться с тремя множествами (монеты, среди которых может быть легкая; монеты, среди которых может быть тяжелая; проверенные монеты) и изменениями, которые взвешивание разными способами проделывает с этими множествами, но че-то у меня из этого ничего не выходит...
ext_55374
Jan. 18th, 2011 08:14 pm (UTC)
А Вы и для 12 напишите.
ilanabendery
Jan. 19th, 2011 04:40 am (UTC)
Да я уже и для 13 поняла как взвешивать ) И заодно что 13=1+3+9 вроде как максимальное число монет, среди которых можно искать тремя взвешиваниями без наличия дополнительных эталонных монет (при наличии эталонной монеты, когда можно будет первым взвешиванием сравнить не 4 и 4, а 4 и 5, максимум повысится до 14).
Ход взвешивания:
1) На каждую чашку по четыре монеты, пять в сторонку.
2а) Одна из чашек перевесила. Обозначим монеты перевесившей четверки как 1, 2, 3, 4, а легкой — как 5, 6, 7, 8. Опять взвешиваем по четыре монеты: на одной чашке 1, 2, 5, 6, на другой 3, 7 и любые две из отложенной пятерки.
3аа) Перевесили две пары подозрительных. Сравниваем 1 и 2.
* Если 1 тяжелее, то она и есть фальшивая.
* Если 2 тяжелее, фальшивая она.
* Если они одинаковые, то фальшивая 7 и она легкая.
3аб) Перевесила другая чашка. Сравниваем 5 и 6.
* Если 5 тяжелее, то 6 фальшивая.
* Если 6 тяжелее, то 5 фальшивая.
* Если весы в равновесии, то 3 — тяжелая фальшивая монета.
3ac) Весы в равновесии. Кладем на одну чашку 4 и 8, а на другую любые две монеты.
* Если подозрительные перевесят, то фальшивая 4.
* Если перевесят проверенные, то фальшивая 8.
* Третий случай невозможен, у нас же 13 монет было изначально, а не 14 )
2b) Обе четверки в равновесии. Значит, под подозрением отложенная пятерка. Обозначим эти монеты как 1, 2, 3, 4 и 5. Сравним 1 и 2 с 3 и любой ранее взвешенной монетой.
3ba) 1 и 2 перевесили. Сравниваем 1 и 2.
* Если 1 тяжелее, то она фальшивая.
* Если 2 тяжелее, то 2 фальшивая.
* Если они одинаковые, то фальшивая — легкая 3.
3bb) Перевесили 3 и эталон. Тоже сравниваем 1 и 2.
* Если 1 тяжелее, то 2 фальшивая.
* Если 2 тяжелее, то 1 фальшивая.
* Если они одинаковые, то 3 фальшивая и тяжелая.
3bc) Весы в равновесии. Под подозрением 4 и 5. Взвешиваем 4, сравнивая с любой проверенной монетой.
* Если одна из чашек перевесит, то 4 фальшивая.
* Если монеты окажутся одинаковые, то фальшивая 5, хотя мы и не знаем, легкая она или тяжелая.
...Надеюсь, нигде не накосячила )
ext_55374
Jan. 19th, 2011 01:52 pm (UTC)
Похоже на правду, спасибо!

ПС Как насчёт 14, 40 и 41? :)
ilanabendery
Jan. 19th, 2011 03:31 pm (UTC)
Э-э... Разве что если смотреть чисто по теории, не расписывая каждый ход, а то ерунду ж напишу, и теория заодно несостоятельной окажется )) Ну 14 — сравнить 5 монет с 4 плюс какая-то сторонняя монета, дальше так же, как для 13, с той разницей, что дополнительная проверяемая монета тоже может быть фальшивой, и вот тогда-то во взвешивании 3ac будет равновесие.
40 четырьмя взвешиваниями — оставить в стороне 14 (с ними понятно что делать дальше), сравнить 13 и 13, и если одна чашка перевесит, то на следующем этапе сравнивать пять «легких» и пять «тяжелых» с четырьмя «легкими», четырьмя «тяжелыми» и двумя проверенными, при любом исходе под подозрением остаются девять или восемь монет с определенной «направленностью», с ними тоже уже понятно, что делать. Сплошная рекурсия, в общем...
(Deleted comment)
fregimus
Jan. 17th, 2011 08:54 pm (UTC)
У Вас три взвешивания.
( 23 comments — Leave a comment )