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

[fregimus]

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

Comments

[matholimp.livejournal.com]

Нельзя. Каждое взвешивание уменьшает неопределённость в 3 раза. Два взвешивания - в 9 раз. Так как монет больше, то обязательно останется случай, когда невозможно точно указать лёгкую.

[(Anonymous)]

Правильнее сказать "не более чем в 3 раза".

[fregimus.livejournal.com]

Умозрительно мне тоже так кажется. Но хотелось бы более строго доказать.

[matholimp.livejournal.com]

Допустим кто-то изобрёл нужный алгоритм. Реализуем его.
В зависимости от результата первого взвешивания получаем 3 случая. В каждом из них по 3 подслучая. Всего 9 подслучаев на 10 монет. Принцип Дирихле!

[fregimus.livejournal.com]

Дирихле, да, он самый, спасибо. А я через количеством информации считал — некрасиво получилось.

[ilanabendery.livejournal.com]

Я в свое время через количество информации считала и осталась удовлетворена, для такого тупаря, как я, это достаточно красиво ))

[crocotiger.livejournal.com]

Как ни раскладывать монетки, два взвешивания дают только 9 возможных результатов : ЛЛ, ЛР, ЛП, РЛ, РР, РП, ПЛ, ПР, ПП. (Где Л - левая чашка легче, Р - равно, П - правая.) Если монет больше девяти, обязательно будет результат, которому соответствует больше, чем одна монетка.

[old-surehand.livejournal.com]

Перед финальным взвешиванием должно оставатся не более 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.livejournal.com]

Можно одним "взвешиванием":
Кладём половину монет на одну чашу, половину на другую.
Затем снимаем по одной монете с каждой чаши до тех пор,
по равновесие не восстановится.

[fregimus.livejournal.com]

Нет, одно взвешивание — это когда мы кладем монеты, отпускаем стрелку, смотрим, куда отклонилась. Каждая снятая пара монет — дополнительное взвешивание.

[http://users.livejournal.com/_winnie/]

Спасибо, красивый "взлом" условий задачи :)

[anatoly borodin (from livejournal.com)]

Намного интереснее другая задача: 13 монет, одна из них фальшивая, но не известно, легче она или тяжелее. Можно ли найти её за 3 взвешивания, и если можно, то как?

[darth-vasya.livejournal.com]

не известно, легче она или тяжелее

[darth-vasya.livejournal.com]

(авторская офрография сохранена)

[anatoly borodin (from livejournal.com)]

В случае, если {1-5} < {6-10} возможны 10 равновероятных ситуаций, которые за 2 взвешивания не ловятся. Так что незачёт.

[anatoly borodin (from livejournal.com)]

> Очевиден вектор (легче или тяжелее монета)

Вовсе неочевиден. Тяжелая монета может быть слева, лёгкая монета может быть справа.

[anatoly borodin (from livejournal.com)]

Правильное решение: http://fregimus.livejournal.com/137464.html?thread=3644152 Там, кстати, есть момент 10 > 9, но ловится он за счёт того, что мы не всегда можем в конце концов узнать, тяжелее монета или легче.

[ilanabendery.livejournal.com]

Мне, кажется, когда-то удавалось решить эту задачу для 12 монет, но сейчас я этот подвиг не повторю.
Но, насколько я помню, там важно при первом взвешивании не бухать всё на чашки, а оставить как можно больше в стороне, потому что при перевесе одной из чашек содержимое обеих оказывается под подозрением, то есть взвешивание всех монет сразу к ответу на главный вопрос почти не приближает.
Сейчас посчитала, вроде количество монет, которое кладется на каждую чашку на первом этапе, должно быть от двух до четырех, но какое лучше (вряд ли их должно быть две, а вот между тремя и четырьмя я сомневаюсь) и что потом со всем этим делать дальше, в упор не помню.
Возможно, надо как-то поиграться с тремя множествами (монеты, среди которых может быть легкая; монеты, среди которых может быть тяжелая; проверенные монеты) и изменениями, которые взвешивание разными способами проделывает с этими множествами, но че-то у меня из этого ничего не выходит...

[anatoly borodin (from livejournal.com)]

А Вы и для 12 напишите.

[ilanabendery.livejournal.com]

Да я уже и для 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, хотя мы и не знаем, легкая она или тяжелая.
...Надеюсь, нигде не накосячила )

[anatoly borodin (from livejournal.com)]

Похоже на правду, спасибо!

ПС Как насчёт 14, 40 и 41? :)

[ilanabendery.livejournal.com]

Э-э... Разве что если смотреть чисто по теории, не расписывая каждый ход, а то ерунду ж напишу, и теория заодно несостоятельной окажется )) Ну 14 — сравнить 5 монет с 4 плюс какая-то сторонняя монета, дальше так же, как для 13, с той разницей, что дополнительная проверяемая монета тоже может быть фальшивой, и вот тогда-то во взвешивании 3ac будет равновесие.
40 четырьмя взвешиваниями — оставить в стороне 14 (с ними понятно что делать дальше), сравнить 13 и 13, и если одна чашка перевесит, то на следующем этапе сравнивать пять «легких» и пять «тяжелых» с четырьмя «легкими», четырьмя «тяжелыми» и двумя проверенными, при любом исходе под подозрением остаются девять или восемь монет с определенной «направленностью», с ними тоже уже понятно, что делать. Сплошная рекурсия, в общем...

[fregimus.livejournal.com]

У Вас три взвешивания.