Старая новая задача

[apis]

Все знают задачу про 10 мешков с золотыми монетами, в одном из них фальшивые. Предлагаю подумать и усложить задачу когда: всего мешков с золотыми монетами m, среди них есть n мешков с фальшивыми монетами. Золотая монета весит 10 гр, фальшивая 9 гр. Есть электронные весы, которые показывают вес с точностью до грамма. Считаем, в мешках неограниченное количество монет.  Нужно за одно взвешивание найти все мешки с фальшивыми монетами. Задачу необходимо решить самым оптимальным рядом (использовать минимальное количество монет при взвешивании)

[☭-Изделие 20Д]

Все знают задачу про 10 мешков с золотыми монетами, в одном из них фальшивые. Предлагаю подумать и усложить задачу когда: всего мешков с золотыми монетами m, среди них есть n мешков с фальшивыми монетами. Золотая монета весит 10 гр, фальшивая 9 гр. Есть электронные весы, которые показывают вес с точностью до грамма. Считаем, в мешках неограниченное количество монет.  Нужно за одно взвешивание найти все мешки с фальшивыми монетами. Задачу необходимо решить самым оптимальным рядом (использовать минимальное количество монет при взвешивании)

Н7у тогда и применять - новое старое оптимальное решение
Из всех сундуков/мешков по порядку берем монеты начиная от 1 и кончая М - взвешиваем все разом - в зависимости от результата получаем номера фальшивых вместилищ.
ПыСы: - с весами монет 9 и 10 - вроде существует только 1 вариант попадания в неблагоприятное расположение монет, т.е. сложность с идентификацией 10-го сундука.

[Валерий]

Показать скрытый текст

Из первого мешка берем 2 монеты, а из каждого последующего мешка, берем такое минимальное количество монет, что бы это число невозможно было получить суммируя любое количество предыдущих взятий.
Например:  2 3 4 8 16  и т д
ps наверное можно поискать и более оптимальный вариант для первого мешка

 

[apis]

ответ как в старой доброй не подходит. Если брать с первого мешка одну монету, со второго две, с третьего 3, с m мешка m монет. Ложим это на весы. Получаем разницу например 4. Так как фальшивых мешков больше одного, т.е. n, то вариантов фальшивых мешков может быть много. Т.е.

1. 4 мешкок
2. 1 и 3 мешок

Если разница будет больше, например 10, вариантов будет еще больше.

[замат]

может поможет великая теорема Ферма? с 1 мешка берём одну монету, со 2 мешка берем 8 монете, с 3 берём 27 , и тд.По разнице определить где могут быть фальшивые, так как никакие совпадения невозможны.Не хочу расписывать варианты так как лень, может чистые програмисты помогут?

[apis]

Применить Ферма конечно можно. Но очень сложно применить... Это решение не оптимально. Так как на если будет мешков больше 15 будет просто очень сложно оперировать числами. А если  фальшивых мешков будет тоже много, то надо будет подбором вычислять из каких чисел получается сумма. Например, мешков 10:
Числа ферма: 1, 5, 7, 17, 257, 65537, 4294967297, 18446744073709551617.... и т.д ещё больше
проще взять тогда просто например 1, 10, 100, 1000, 10000, 100000, и т.д. Но тоже не оптимально.
Нужно самое оптимальное и "экономное" с точки зрения расхода монет решение.

[apis]

2, 3, 8, 16 это подбор... нужна формула

[замат]

Что есть одно взвешивание на электронных весах? Это взвешивыаешь,подбавляешь вес, подбавляешь...,подбавляешь и тд ,пока не снимешь груз и не начнёшь следующее взвешивание. Если с каждого мешка ложить последовательно по одной монете и смотреть на дисплей , то это самый экономный вариант и есть.

[☭-Изделие 20Д]

Что есть одно взвешивание на электронных весах? Это взвешивыаешь,подбавляешь вес, подбавляешь...,подбавляешь и тд ,пока не снимешь груз и не начнёшь следующее взвешивание. Если с каждого мешка ложить последовательно по одной монете и смотреть на дисплей , то это самый экономный вариант и есть.

Как в принципе ипринятоделать на любом базаре. Но на назве в таких задачах используются "коммерческие" весы т.е. для каждой возможности вывести цифирьку на экран - на посмотреть или распечатать на чеке надо бросить монетку, коих обычно столько же, кокое количество взвешиваний разрешена в задаче.  Практически как в банкоматах НАДРАбанка

[apis]

Одно взвешивание - это когда насобирал какое-то количество монет, положил один раз на весы получил вес и всё. Добавлять по одной монеты нельзя.

[Лев]

У нас этих задач решено уже столько, что их тоже нужно мерить мешками 
Просто посмотрите в поиске по тегу "взвешивания"

Вот, к примеру, один из топиков

Если мы подозреваем фальшивую монетку среди Х монеток как более лёгкую или среди Y монеток как более тяжёлую, то:
Если 3К-1 < Х+Y<= 3К, мы можем определить фальшивую монетку не более чем за К взвешиваний.