Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет ded_mitya ([info]ded_mitya) в [info]seminar
@ 2016-05-23 21:51:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Монеты и взвешивания

Вот о том как за 3 взвешивания найти фальшивую монету из 13и
одинаковых (не зная а приори, тяжелее она или легче настоящих),
все знают. А вот из скольки монет можно отыскать фальшивую
при помощи 4х взвешиваний, на тех же условиях? У меня получается,
что задача решается для 39 монет. Можно ли отыскать из большего
количества?


(Добавить комментарий)


(Анонимно)
2016-05-24 10:55 (ссылка)
>все знают
отучаемся говорить за всю фифу

(Ответить)


[info]sasha_a
2016-05-24 13:00 (ссылка)
Если мне не изменяет память, задача решена для произвольного числа монет.
Когда вернусь в Бразилию, спрошу у моего бывшего студента как именно, ну или ссылку (он в молодости этим интересовался).

(Ответить)


[info]freir
2016-05-24 13:32 (ссылка)
https://habrahabr.ru/post/243461/

(Ответить) (Ветвь дискуссии)


[info]freir
2016-05-24 13:50 (ссылка)
там в комментах длинная простыня, из которой
получается, что при помощи 4 взвешиваний
можно отыскать фальшивую среди 40-ка монет

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]ded_mitya
2016-05-24 18:31 (ссылка)
Да, из 40, если не свсе сводить к предыдущим
задачам, а воспользоваться тем, что после первого
взвешивания у нас есть пул хороших монет.

(Ответить) (Уровень выше)


(Анонимно)
2016-05-24 14:11 (ссылка)
а если число фальшивых неизвестно?

(Ответить) (Ветвь дискуссии)


[info]ded_mitya
2016-05-25 04:17 (ссылка)
Тогда перебором, полагаю.

(Ответить) (Уровень выше)


(Анонимно)
2016-05-24 17:07 (ссылка)
> Вот о том как за 3 взвешивания найти фальшивую монету из 13и
> одинаковых (не зная а приори, тяжелее она или легче настоящих),

Не решается. Или 12 монет, или 13 + одна настоящая.

(Ответить) (Ветвь дискуссии)


[info]ded_mitya
2016-05-24 18:32 (ссылка)
В случае с 13 монетами есть шанс не узнать,
легче она или тяжелее. Но решается.

(Ответить) (Уровень выше) (Ветвь дискуссии)


(Анонимно)
2016-05-24 18:53 (ссылка)
https://en.wikipedia.org/wiki/Balance_puzzle

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]ded_mitya
2016-05-24 19:25 (ссылка)
>> and a more complex variant with 39 coins in four weighings

Это замечательно, но задача 3/13 и 4/40 решается, если не требовать
определить к концу решения, тяжелее фальшивая монета или легче.
Решения задачи 3/13 легко находится в сети. Решение задачи 3/39
конструируется простой индукцией из 3/13, задача 4/40 решается несколько
по-другому.

Вверху [info]freir упомин ает решение 4/40 в комментах на хабре.
Я не читал (мне лень), но в принципе, после 3/13 ничего сложного там нет.

(Ответить) (Уровень выше)