Задача о фальшивых монетах

[Serge Kotov]

Цитата:

Сообщение от sukhanchik

Че-то не догоняю. У нас 10 кучек. Вот мы положили 5 кучек на одну чашу, а 5 на другую. Понятно - что какая-то чаша легче. Берем из нее 5 кучек и снова делим по чашам (2 и 2 и 1 в остатке). Если весы ровные - значит остаток - фальшивый (итого - 2 взвешивания). Если весы неровные - то кучки из легкой чаши снова дробим по чашам и уже точно узнаем, какая легче (итого - 3 взвешивания).

Верно, это "классический" подход к решению этого класса задач с делением на три кучки, т.е. за три взвешивания определить действительно можно. Но можно ли здесь сократить число взвешиваний?

[ashu]

задача "Какое минимальное число взвешиваний необходимо провести для определения кучки фальшивых монет?"
1. вариант "лотерейный", за одно взвешивание, наугад берем 2 монетки из разных кучек, нам везет- и сразу находим одну кучку с фальшивкой

2. вариант математический (для меня сложный ибо я гуманитарий, но вроде работает). Берем 9 кучек, одну кучку оставляем в сторонке. Делим все монеты на 2 кучки по следующему алгоритму:

в 1 кучку берем 1 монету из первой кучи и 9 монеток из 9, 2 монеты из второй и 8 из восьмой,,3 монеты из третьей и 7 из седьмой, 4 из четвертой и 6 из шестой, и по пять раскладываем из 5 кучки.
в итоге получаем 2 кучи, в каждой из которых по 45 момент. Взвешиваем их и находим разницу в граммах между этими кучами (см условие задачи "Вы имеете весы для взвешивания монет друг с другом с точностью до одного грамма.").
Возможно 2 варианта:
1. Кучки разные по весу, разность весов и есть номер кучки с фальшивкой
2. Кучки равны по весу- это говорит о том что фальшивка или в 10 кучек- которую мы отложили, или в 5- которую мы поделили по пополам, вторым взвешиванием 5 и 10 кучки определяем какая именно нарушает закон о фальсификации деняжек.
Профит.

Итого однозначно можно определить с 2 взвешиваний

[oip]

Цитата:

Сообщение от ashu

2. вариант математический (для меня сложный ибо я гуманитарий, но вроде работает). Берем 9 кучек, одну кучку оставляем в сторонке. Делим все монеты на 2 кучки по следующему алгоритму:

в 1 кучку берем 1 монету из первой кучи и 9 монеток из 9, 2 монеты из второй и 8 из восьмой,,3 монеты из третьей и 7 из седьмой, 4 из четвертой и 6 из шестой, и по пять раскладываем из 5 кучки.
в итоге получаем 2 кучи, в каждой из которых по 45 момент. Взвешиваем их и находим разницу в граммах между этими кучами (см условие задачи "Вы имеете весы для взвешивания монет друг с другом с точностью до одного грамма.").
Возможно 2 варианта:
1. Кучки разные по весу, разность весов и есть номер кучки с фальшивкой
2. Кучки равны по весу- это говорит о том что фальшивка или в 10 кучек- которую мы отложили, или в 5- которую мы поделили по пополам, вторым взвешиванием 5 и 10 кучки определяем какая именно нарушает закон о фальсификации деняжек.

Почти верно, но...

Берем все десять кучек. На каждую чашку весов кладем количество монет соответствующее номеру кучки:

Левая чашка: 1 4 5 8 9
Правая чашка: 3 2 7 6 9 (здесь исключение, из 10-й кучки сюда тоже берем 9 монет).

Итого, на каждой чашке по 27 монет. Разница в граммах - номер кучки с фальшивыми монетами, кроме случая, когда разница составляет 9 грамм. В этом случае фальшивая кучки или 9 или 10 в зависимости от того, какая все-таки чашка легче, левая или правая. Итого - одно взвешивание.