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

[Serge Kotov]

Привет всем любителям "покурить" над занимательными задачами!

Вот новый вариант головоломки из серии занимательных задач на взвешивание монет, который я случайно придумал в один прекрасный момент:

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

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

[sukhanchik]

Или я чего-то не понимаю или...
Мы взвешиваем парами. Значит вероятность угадывания - 2/10 = 1/5. Т.е. математическое ожидание равно 5. Т.е. за 5 взвешиваний мы гарантированно "наткнемся" на фальшивку. Ну... может конечно "повезти" и с первого раза...

Или я неправильно понял смысл задачи?

[oip]

Я не понял, какие весы? Что значит "весы для взвешивания монет друг с другом"? Навскидку, за одно, при условии, что весы сравнивают вес двух чашек и дополнительно показывают разницу в граммах. За два, если весы просто показывают вес одной чашки, а не сравнивают две чашки между собой. За три, если весы просто показывают "больше-меньше", но разницу в граммах не показывают. Нет?

[sukhanchik]

За одно? Методом половинного деления 3 получится. Нет?

[oip]

Если мы знаем разницу в весе двух кучек в граммах, то да, за одно.

[sukhanchik]

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

[oip]

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

[Serge Kotov]

Цитата:

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

Если мы знаем разницу в весе двух кучек в граммах, то да, за одно.

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

[oip]

Фразу можно читать как "Если мы знаем (весы показывают) разницу в весе двух чашек весов в граммах, то да, за одно." Так какие весы-то? Что значит "весы для взвешивания монет друг с другом"? Весы обычные рычажные?

[Serge Kotov]

Цитата:

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

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

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

[S.Kuskov]

Цитата:

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

за одно, при условии, что весы сравнивают вес двух чашек и дополнительно показывают разницу в граммах. За два, если весы просто показывают вес одной чашки, а не сравнивают две чашки между собой. За три, если весы просто показывают "больше-меньше", но разницу в граммах не показывают. Нет?

Да.

Serge Kotov, расписать процесс взвешивания?

[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 взвешиваний

[Serge Kotov]

S.Kuskov: распишите процесс за единственное взвешивание

[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 в зависимости от того, какая все-таки чашка легче, левая или правая. Итого - одно взвешивание.

[Lucky13]

По-моему, это вариант классической задачи, показывающей, как избыточность позволяет сократить кол-во измерений. Только звучала она: как с помощью одного взвешивания определить в какой куче фальшивые монеты. То есть правильные ответ 1 взвешивание. А взвешивать надо из каждой кучи по n+1 монеты, где n - номер кучки. В итоге остаток от деления веса на 10 укажет ответ. В данном варианте не очень понятно что значит "для взвешивания монет друг с другом", по-моему, достаточно просто весов с точность до грамма

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

Цитата:

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

В данном варианте не очень понятно что значит "для взвешивания монет друг с другом", по-моему, достаточно просто весов с точность до грамма

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

[oip]

Цитата:

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

По-моему, это вариант классической задачи, показывающей, как избыточность позволяет сократить кол-во измерений. Только звучала она: как с помощью одного взвешивания определить в какой куче фальшивые монеты. То есть правильные ответ 1 взвешивание. А взвешивать надо из каждой кучи по n+1 монеты, где n - номер кучки. В итоге остаток от деления веса на 10 укажет ответ. В данном варианте не очень понятно что значит "для взвешивания монет друг с другом", по-моему, достаточно просто весов с точность до грамма

Ну это же не так, если мы не знаем веса настоящей монеты. Для его определения нужно второе взвешивание. А если просто взвесить (только из кучки номер n берем n монет, а не n+1, по условиям задачи у нас по десять монет и из 10-й кучки 11 мы никак не возьмем, поэтому почему n+1, а не n не очень понял), то не получится. Пример:

Пусть вес искомых 55 монет 542 грамма. Это может означать как то, что вес настоящей монеты 10 грамм, вес фальшивой 9 грамм, фальшивая монета в кучке номер 8, так и то, что вес настоящей монеты 9,92(72) грамма, фальшивой 8,92(72) и фальшивая кучка 4-я.

Я не прав? В классическом варианте добавляется, что вес настоящей монеты 10 грамм. Тогда да, за одно взвешивание остатком от деления.

[Lucky13]

Цитата:

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

только из кучки номер n берем n монет, а не n+1, по условиям задачи у нас по десять монет и из 10-й кучки 11 мы никак не возьмем, поэтому почему n+1, а не n не очень понял)

Моя ошибка, конечно же n

Цитата:

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

Я не прав? В классическом варианте добавляется, что вес настоящей монеты 10 грамм. Тогда да, за одно взвешивание остатком от деления.

По-моему, разницы нет сколько весят монеты. Моя формула вообще для задачи, где фальшивая монета на 1 г тяжелее настоящей, если легче, то по другому считать надо, но все равно вес будет отличаться от идеального (когда все монеты настоящие) на номер кучки

[S.Kuskov]

Цитата:

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

вес будет отличаться от идеального (когда все монеты настоящие) на номер кучки

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