Теперь Кью работает в режиме чтения

Мы сохранили весь контент, но добавить что-то новое уже нельзя
Андрей Саускан
Я, Саускан Андрей пишу для детских математических...  · 24 мая 2023

Нерешенная задача на взвешивание.

Задача такая. Предложена П. Эрдешем и А. Реньи в 1963 г.
Имеется N монет, некоторые из них правильные и весят по 10 гр.,
а остальные фальшивые, весом по 9 гр.За какое наименьшее
число взвешиваний на одночашечных весах со стрелкой можно
определить все фальшивые монеты?
/////////////////////////////////////////
Наверное, не сам П. Эрдеш или А.Реньи приклеили прилагательное,
знаменитая задача, в интернете несколько раз встречалось именно
такое прилагательное к этой задаче. Самое веселое, что при определенном везении эту задачу решит и младшеклассник, что
еще раз подтверждает, что математика это не соревнование
по количеству знаний формул и теорем, а задачка действительно
интересная.
Виктор Воеводов
 ЗА ОДНО!!!  Задачка прикольная! ПОПРАВКА: Невнимательно прочитал условие задачи. За одно взвешивание можно... Читать дальше
Дарья Ковалева
@Виктор Воеводов, за одно взвешивание можно определить количество фальшивых монет, но в задаче спрашивается "определить все фальшивые монеты", т.е. необходимо для каждой монеты дать ответ, фальшивая она или настоящая, а это явно не 1 взвешивание
Андрей Бахматов
За два взвешивания: первое взвешивание даёт нам информацию о количестве K фальшивых монет (то, насколько масса меньше чем 10N), во втором взвешивании берём K монет и по счастливому стечению обстоятельств оказывается, что их масса как раз равна 9*K, а значит нам удалось найти все фальшивые монеты.
Андрей Саускан
@Андрей Бахматов, Первым взвешиванием Вы нашли общее
количество фальшивых монет.Но если счастливое стечение обстоятельств отсутстует, как вторым взвешиванием определить
вес каждой из N монет?
Как пример. Если N=10. Провели первое взвешивание,поместили все 10 монет на чашу весов получили, например, такой возможный результат.
Среди 10 монет какие-то 6 монет весят по 10 гр. и какие-то 4 монеты
весят по 9 гр. Каков следующий выбор монет для второго взвешивания,
которое должно определить вес каждой из 10 монет?
Николай Перов.
А в чем проблема с прилагательным одночашечных? И безмены тогда были популярны. И в магазинах достаточно часто были весы с одной чашей и стрелкой, полагаю.
Мне кажется, в общем случае, алгоритм следующий: делим на 3 (по возможности равных) кучи. И каждую завешиваем.  
Затем, каждую из полученных куч делим на к+1 частей, где к - количество фальшивых или настоящих монет в этой куче, что меньше. С каждой из "смешанных" кучек (а как минимум одна кучка у нас "однотонная") проделываем то же самое  пока все кучки не станут однотонными. 
А, что по цифрам получается, и почему вначале именно 3 кучки, а к именно +1,и главное - доказывать оптимальность, сейчас не готов время тратить. 
Андрей Саускан
@Николай Перов., Не то,что проблема с прилагательным,просто оно такое,скажем,так,громогласное. А прилагательное, не одночашечные,а
знаменитая.В интернете встречается именно такое прилагательное к
этой задачке. У меня есть несколько знакомых,профессиональных математиков. Про эту задачу и слыхом не слыхивали. Поэтому мне и
захотелось узнать,насколько она (задачка) знаменитая? А по алгоритму,
который Вы предложили,вполне возможно,что он приведет к оптимальному результату.