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

[Lucky13]

Цитата:

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

Т.е. идеальный вес полагается известным?

Да. Я говорю про решение немного другой задачи, так решить именно этот вариант мыслей пока нет

[honest]

Необходимо сформировать две кучи монет. В первую кучу берем 1 монету из 1 группы, 2 из 2 и т.д. до 9 группы (10 группу не трогаем). Во вторую кучу берем 1 монету из 10, 2 монеты из 8, 3 монеты из 7 ... 9 монет из 1 (9 группу не трогаем). В каждой куче по 45 монет. Обозначаем за Х - вес нормальной монеты. Тогда если фальшивые монеты в 1 группе, то имеем: вес левой чаши = 45Х -1, вес правой чаши = 45Х - 9. Левая чаша тяжелее правой на 8 грамм. Перебрав все варианты можно получить следующую разницу: 8, 6, 4, 2, 0, -2, -4, -6, -9, 1 (минус означает что левая чаша легче правой). Повторяющихся значений нет, следовательно можно однозначно определить группу с фальшивыми монетами.

[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;

[S.Kuskov]

Цитата:

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

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

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

[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 - элементов должна быть равна друг другу.