Фальшивые монеты

Среди 100 одинаковых на вид монет есть несколько фальшивых. Все фальшивые монеты весят одинаково, все настоящие - тоже, фальшивая монета легче настоящей. Имеются также весы (с двумя чашами без стрелки), на каждой чашке умещается только по одной монете. При этом весы слегка испорчены: если монеты разного веса, перевешивает более тяжёлая монета, а если одинакового - перевесить может любая чашка. Как с помощью этих весов найти хотя бы одну фальшивую монету? 

Ответ: Разделим монетки на 33 кучки по 3 монетки + 1 монетка.
Каждое трио взвешиваем между собой, получим 3 неравенства, в результате которых увидим, либо каждая монетка будет по одному разу весить меньше от других двух, либо два раза будет весить меньше других двух.
1>2 (возможны такие варианты: н=н, ф=ф, 2-фальшивка)
1<3 (н=н, ф=ф, 1- фальшивка)
2>3 (н=н, ф=ф, 3- фальшивка)
такое возможно, если все три монетки имеют одинаковый вес вежду собой, то есть из них откладываем в сторонку любую одну
1<2(н=н,ф=ф,1-ф)
1<3(н=н,ф=ф,1-ф)
2>3(н=н,ф=ф,3-ф)
У 1 больше вероятностьть оказаться фальшивой, так что ее и откладываем.
И так проделываем с каждой из 33-х кучек, в результате отложим 11 монет +1, которая не попала ни в одну из кучек.
 Эти 12 монет опять разделям на 4 кучки по 3 монетки, проделываем те же манипуляции, в результате получим 4 монетки, разделяем на 1 кучку+1, та монетка из кучки, которая окажется легче, вновь откладываем и сравниваем с одинокой монеткой. Та, которая легче и будет фальшивой.

 

Обсуждение задачи на форуме - Фальшивые монеты

Ваша оценка: Нет Средняя: 3.6 (44 оценки)


Комментарии

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

Там же указоно, настоящея манета,немного отличается от фальштвой

Не имеет разницы по парам или сравнивать с одной в итоге получится тоже 99 взвешиваний:
1 круг - 50 взвешиваний (осталось 50 монет)
2 круг - 25 взвешиваний (осталось 25 монет)
3 круг - 12 взвешиваний, 1 монетку перекладываем (осталось 13 монет)
4 круг - 6 взвешиваний, 1 монетку перекладываем (осталось 7 монет)
5 круг - 3 взвешиваний, 1 монетку перекладываем (осталось 4 монет)
6 круг - 2 взвешиваний, (осталось 2 монет)
7 круг - 1 взвешивание - монета найдена

Итого 50+25+12+6+3+2+1=99 взвешиваний

Для начала хочу заметить, что в условии допущена опечатка: не «Среди ста одинаковых монет на вид есть несколько фальшивых», а «Среди ста одинаковых на вид монет есть несколько фальшивых». Монеты какие? — одинаковые на вид.

А теперь, собственно, к делу. Давайте посчитаем, сколько взвешиваний придётся выполнить, чтобы выполнить Ваш алгоритм.

Чтобы взвесить 3 монеты между собой, нужно выполнить 3 взвешивания. У Вас 33 кучки по 3 монеты. Так что на первом этапе придётся выполнить 3*33=99 взвешиваний. Затем ещё 3*11=33 взвешивания. В результате получим 12 монет, 4 кучки по 3 монеты. Ещё раз сравним их между собой. Это ещё 3*4=12 взвешиваний. В результате получим 1 кучку из 3 монет и одну одинокую монету. Сравним монеты в кучке: ещё 3 взвешивания. Теперь сравним последнюю монету с одинокой. Ещё одно. Итого: 99+33+12+3+1=146 взвешиваний. Строго говоря, несложно показать, основываясь на формуле суммы геометрической прогрессии (я выкладок не привожу), что если обозначить количество монет буквой N, количество взвешиваний (назовём его Q) при N, стремящемся к бесконечности, будет стремиться к Q ? 1,5·N. Например, при N=1000, Q = 999+333+111+36+12+6+1 = 1498, почти 1500. Ещё пример: при N=10 000, Q = 9999+3333+1110+372+123+42+12+6+1 = 14 998, почти 15 000. И так далее…

Итак, Q?1,5·N. Странный алгоритм. Можно поступить намного проще с точки зрения понятности решения, да и количество взвешиваний будет меньше.

Ниже приведён мой алгоритм. Во избежание путаницы кучки буду именовать буквами.

  1. Сложить все монеты в кучку Н (Не взвешенные). Перейти к следующему шагу.
  2. Взять из кучки Н одну монету и положить её в кучку Т (Текущее взвешивание). Перейти к следующему шагу.
  3. Если в кучке Н есть хотя бы одна монета, перейти к следующему шагу, иначе перейти к шагу 6.
  4. Взять любую одну монету из кучки Н и положить её в кучку Т. Перейти к следующему шагу.
  5. Взвесить монеты в кучке Т (их на данном этапе будет ровно 2 штуки). Монету, которая, по результатам взвешивания, оказалась тяжелее, переместить в кучку В (Взвешенные). Перейти к шагу 3.
  6. Решение найдено: монета в кучке Т (на данном этапе в кучке Т ровно одна монета) является фальшивой.


Проще говоря, нужно взять одну монетку, сравнить её с любой другой, затем тяжёлую убрать в сторонку, а лёгкую снова сравнить с любой не взвешенной, и так повторять до тех пор, пока все монетки, кроме одной, не будут отложены в сторонку. Эта-то одна и есть фальшивая!

Почему это работает? Всё очень просто. Постепенно, по мере того как мы взвешиваем ещё не взвешенные монетки, их количество уменьшается. Если среди ста монет есть хоть одна фальшивая (а условия задачи говорят нам, что это так), она рано или поздно будет взвешена (то есть попадёт в кучку Т). А из кучки Т она уже никогда не выберется, так как мы всякий раз убираем только тяжёлую монету. Почему это так?

Давайте разберёмся. Если мы взвешиваем две монеты, возможны три варианта: либо обе они настоящие, либо обе фальшивые, либо одна фальшивая, а другая настоящая. Если обе настоящие, то убирая тяжёлую в сторонку, мы убираем настояющую (они же обе настоящие). Если одна настоящая, а другая фальшивая, то убирая тяжёлую в сторонку, мы убираем настоящую (настоящая же тяжелее), а фальшивая остаётся до следующего взвешивания. Наконец, если обе монеты фальшивые, тяжёлая тоже будет фальшивая, и убирая тяжёлую, мы убираем фальшивую, но фальшивая остаётся (они же обе фальшивые). Таким образом, если из двух взвешиваемых монет ни одна не фальшивая, то убирая одну монетку в сторонку, мы просто «сужаем круг подозреваемых», уменьшаем количество не взвешенных монет; если из двух взвешиваемых одна фальшивая, она останется на следующее взвешивание; если же обе, одна из них останется. Так что как только фальшивая монета попадёт на весы, она уже с них не сойдёт, а если и сойдёт, то только при условии, что на противоположной чаше весов останется другая фальшивая. Вот так.

Теперь подсчитаем взвешивания в случае решения моим алгоритмом: Q=99. Строго говоря, Q=N-1. Что означает, что требуется чуть более чем в полтора раза меньше взвешиваний! Да и понять мой алгоритм проще.

>требуется чуть более чем в полтора раза меньше взвешиваний
Поправлюсь: не чуть более, а примерно. Например, нельзя сказать, что 99 чуть более чем в полтора раза меньше чем 146: на самом деле, конечно, 99 менее чем в полтора раза меньше.

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

Можно сделать проще....
Взять, например, нормально работающие весы.

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

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

> если монеты разного веса, перевешивает более тяжёлая монета, а если одинакового - перевесить может любая чашка.
Если я правильно понял, то:
* когда на весах нормальная монета и фальшика, весы в 100% случаев работают верно;
* когда на весах две фальшивки или два оригинала, весы в 50% случаев дают правильный ответ.

А раз так, то делаем просто:
Берем любые 2 монеты, взвешиваем их, скажем, 10 раз (или больше - по настроению ;).
Если весы все 10 раз показали одно и то же, значит тяжелая монета - настоящая, а легкая - фальшивка.
Если весы за эти 10 взвешиваний выдавали разные результаты, то монеты равны по весу (обе настоящие или обе фальшивки).

Да, тут возможны ошибки, но их можно свести к минимуму, увеличив количество взвешиваний.