Задача об 11 мешках с монетами, найти фальшивые за 2 взвешив

[Xenia1996]

Имеется 11 мешков монет. В 10 из них монеты настоящие, а в одном — все монеты фальшивые. Все настоящие монеты одного веса, все фальшивые монеты — также одного, но другого веса. Имеются весы, с помощью которых можно определить, какой из двух грузов тяжелее и на сколько. Двумя взвешиваниями определить, в каком мешке фальшивые монеты.

Моё решение:

(Оффтоп)

Кладём на левую чашу по одной монетке из мешков с первого по пятый, на правую - с шестого по десятый.
Если равновесие - фальшивый мешок определён (11-й) и второе взвешивание не понадобится.
Если неравновесие, сразу виден модуль разности между настоящей и фальшивой монетами.

Второе взвешивание:
Кладём 55 монет из 11-го мешка (уже известно, что они - настоящие) на левую, а на правую одну из первого, две из второго, три из третьего, ... , десять из десятого.
Стрелка покажет вес, больший модуля разности между настоящей и фальшивой монетами ровно в число раз, равное номеру "фальшивого" мешка.

Решение "из книжки":
http://problems.ru/view_problem_details ... p?id=78572

1. Не ошибочно ли моё решение?
2. А что если в каждом мешке не более 54 монет?

[Gortaur]

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

[Xenia1996]

Gortaur в сообщении #458681 писал(а):

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

Уже нашла, как обойтись 45-ю монетами.
Во втором взвешивании кладём 45 из 11-го и с 1 по 9 из мешков с первого по девятый. Если равноденствие, то фальшивый мешок - десятый.

А моё решение точно правильное?

[Gortaur]

При первом взвешивании определяете паршивый ли мешок номер 11 - а если нет, то узнаете разницу в весах между монетами. При повторном взвешивании Вы эту разницу используете, чтобы определить паршивый мешок. В чем ошибку подозреваете-то?

[Xenia1996]

Gortaur в сообщении #458690 писал(а):

При первом взвешивании определяете паршивый ли мешок номер 11 - а если нет, то узнаете разницу в весах между монетами. При повторном взвешивании Вы эту разницу используете, чтобы определить паршивый мешок. В чем ошибку подозреваете-то?

В том, что моё решение разнится с "книжным".

[Gortaur]

Xenia1996
Ваше решение через 45 монет тоже разнится с Вашим через 55.

[Xenia1996]

Хотелось бы ещё и доказать, что одним взвешиванием обойтись нельзя...

[Gortaur]

Попробую... пусть $k_i$ где $i = 1,2,...,11$ - сколько монет мы положили на весы из $i$-го мешка. $k_i>0$ значит что мы положили на правую чашу, $k_i<0$ - значит, что на левую. Обозначим $K = \sum\limits_i k_i$Предположим, что в $j$-ом мешке находятся фальшивые монеты. Тогда результат на весах будет

$$ S = \sum\limits_{i\neq j}k_i G+k_j B $$

где $G,B$ - массы настоящих и фальшивых монет соответственно. Все, что мы знаем - так это то, что

$$ S = (K-n)G+nB, $$

где $n\in \mathbb{N}_0$. Нужно найти решение данного уравнения относительно $n$, причем оно должно быть единственно, потому что это необходимое условие для определения мешка с фальшивыми монетами. Все, что мы можем менять - это $k_i$. Легко видеть, что если $S = 0$ и $K=0$ - то это как раз случай, когда решение единственно: а именно, мы не взвешивали фальшивые монеты. В любом другом случае решение будет неединственным, потому что $G,B$ для нас неизвестны.

[Sender]

Xenia1996 в сообщении #458686 писал(а):

Уже нашла, как обойтись 45-ю монетами.

Достаточно и 9-ти монет.

[TOTAL]

Sender в сообщении #458966 писал(а):

Xenia1996 в сообщении #458686 писал(а):

Уже нашла, как обойтись 45-ю монетами.

Достаточно и 9-ти монет.

Достаточно 30 монет всего (побывавших на весах)

[Sender]

TOTAL в сообщении #458988 писал(а):

Достаточно 30 монет всего (побывавших на весах)

Что-то мне кажется, что такое возможно, только если заранее известно, легче фальшивая монета настоящей или тяжелее.

[Xenia1996]

TOTAL в сообщении #458988 писал(а):

Sender в сообщении #458966 писал(а):

Xenia1996 в сообщении #458686 писал(а):

Уже нашла, как обойтись 45-ю монетами.

Достаточно и 9-ти монет.

Достаточно 30 монет всего (побывавших на весах)

Почему?

[TOTAL]

Xenia1996 в сообщении #459061 писал(а):

TOTAL в сообщении #458988 писал(а):

Достаточно 30 монет всего (побывавших на весах)

Почему?

Потому что из 4-х мешков достали по 4 монеты, из 3-х по 3 и т.д.