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

[S.Kuskov]

Ход мыслей. На левую чашу весов кладем одну монету из первой группы, две монеты из второй, три из третьей и т.д. ... всего 1 + 2 + 3 + ... + 9 = 45 монет (из десятой группы пока ничего не берем) На правую чашу кладем по пять монет из каждой группы кроме десятой, т.е тоже всего 5 * 9 = 45 монет.

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

Остается ситуация когда весы показывают равенство. При такой раскладке монет возможна неопределенность. Фальшивки либо в пятой группе, либо в десятой, которая вообще не взвешивалась. Для снятия этой неопределенности скорректируем первоначальное решение. На правой чаше весов (можно и на левой, но не одновременно на двух) монеты пятой группы (их там всего пять) заменим на пять монет из десятой группы. При таком раскладе ситуация равновесия весов будет невозможна, а вместо неё будет разница в 5 грамм. С какой стороны чаша будет легче на 5 грамм, с той и лежат фальшивые 5 монет.

[S.Kuskov]

Цитата:

Сообщение от S.Kuskov

Ход мыслей. На левую чашу весов кладем одну монету из первой группы, две монеты из второй, три из третьей и т.д. ... всего 1 + 2 + 3 + ... + 9 = 45 монет (из десятой группы пока ничего не берем) На правую чашу кладем по пять монет из каждой группы кроме десятой, т.е тоже всего 5 * 9 = 45 монет.

Только сейчас понял что в моем решении ошибка. Не учтено ограниченное число монет в группах.

[Ruff]

left  = 1*x[1] + 2*x[2] + 3*x[3] + 4*x[4] + 5*x[5];
right = 1*x[6] + 2*x[7] + 3*x[8] + 4*x[9] + 5*x[10];

diff = left - right;
index = diff < 0 ? -diff : 5 + diff;

return index;

[Serge Kotov]

Прекрасно! oip , honest и Ruff справились с задачей!

Все три решения основаны на том факте, что фальшивая монета на 1 грамм легче. Теперь давайте усложним задачу. Нам известно, что фальшивая монета отличается по весу на один грамм, но неизвестно - легче она или тяжелее настоящей.

Как в этом случае за одно взвешивание определить, какая кучка содержит фальшивые монеты?

Для удобства привожу новое условие головоломки полностью:

У вас имеется десять кучек монет по десять монет в каждой кучке. Известно, что одну из кучек полностью составляют фальшивые монеты, а все остальные монеты настоящие. Неизвестно, сколько весит настоящая монета, но известно, что вес фальшивой - отличается на один грамм от настоящей. Вы имеете весы для взвешивания монет друг с другом с точностью до одного грамма.

Как за одно взвешивание определить, какая из кучек содержит фальшивые монеты?

Если найдутся новые решения, предлагаю авторам публиковать их завтра после 14:00 - чтобы не перебивать аппетит тем, кто решит найти решение самостоятельно. Интернет можно не шерстить - там этой задачи с решением пока нет.

[oip]

Цитата:

Сообщение от Serge Kotov

Прекрасно! honest и Ruff справились с задачей!

А я где-то неправ был?

[Serge Kotov]

Олег, вы правы, пропустил ваше решение. Дополнил текст выше.

[dn]

Обозначим кучки монет как ABCDEFGHIJ. Составляем две кучки для взвешивания K и L.
K=2A+3B+6E+7F+9H всего 27
L=4C+5D+8G+10I всего 27
Смотрим разницу по модулю при взвешивании:
A:2;B:3;C:4;D:5;E:6;F:7;G:8;H:9;I:10;J:0

[S.Kuskov]

Из каждой группы возьмем число монет равное номеру группы. На одной чаше весов разместим монеты из 1, 2, 3, 4, 6, 7 групп. На другой - из 5, 8 и 10 групп. Взвешиваем. Ненулевая разница в граммах укажет на номер группы с фальшивыми монетами. Равновесие будет означать что фальшивки в 9-ой группе.

[Serge Kotov]

Браво, dn и S.Kuskov!

В принципе путь решения наметил еще oip, необходимо было обеспечить уникальность индекса в двух группах. Маленькая хитрость заключалось в том, что для десяти (n) групп с десятью элементами это возможно при количестве элементов во взвешивании n - 1.

Интересно, что в математическом смысле количество взвешиваемых монет, похоже, может быть сколь угодно большим, необходимо лишь соблюдение следующего простого условия:

Сумма индексов множества из n чисел натурального ряда в двух подмножествах, состоящих из n или n - 1 - элементов должна быть равна друг другу.