Меню

Из пяти монет две фальшивые одна из фальшивых монет тяжелее настоящей



Из пяти монет две фальшивые одна из фальшивых монет тяжелее настоящей

Если же одна из чаш весит больше другой, то возьмем ее и разобьем на две кучки по 25 монет. Если они весят одинаково, то фальшивая монета была на другой чаше, значит, фальшивая легче. Если же одна из чаш перевесит, то фальшивая монета была в этих 50, т.е. фальшивая тяжелее.

Покажем, что если в обоих взвешиваниях одна из чаш перевешивала, то за оставшееся взвешивание можно установить фальшивые монеты. Действительно, тяжелая монета не может лежать на легкой чашке, а легкая на тяжелой. Также тяжелая и легкая монеты не могли участвовать в одном взвешивании. Значит, в одном взвешивании участвовали тяжелая и настоящая, а в другом — настоящая и легкая. Т.е. оставшаяся монета настоящая. Остается сравнить ее с монетой с тяжелой чаши, например, в первом взвешивании.

Очевидно, в обоих взвешиваниях чаши не могли находиться в равновесии.

Если же в одном из взвешиваний чаши находились в равновесии, то на ней лежали две настоящие монеты. Теперь взвесим настоящую и оставшуюся. Мы можем узнать тип этой монеты. А далее узнаем тип монет на чашах, находившихся в одном из первых двух взвешиваний не в равновесии.

У нас осталось 94 − 32=62 взвешивания.

Теперь возьмем все «легкие» монеты. Покажем, как за 31 взвешивание определить среди них самую легкую монету. Сначала положим на каждую чашу по монете. А далее будем повторять следующую операцию: после взвешивания будем убирать тяжелую монету, и класть вместо нее любую монету, которая еще не участвовала во взвешиваниях. Ясно, что всего будет проведено 31 взвешивание. А монета, которая останется на весах и будет самой легкой.

Аналогично за 31 взвешивание определим самую тяжелую монету.

Источник

Из пяти монет две фальшивые одна из фальшивых монет тяжелее настоящей

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

Решение 1

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

Решение 2

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

Читайте также:  Сколько стоят монеты 1831 года

Замечания

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

Источники и прецеденты использования

олимпиада
Название Окружная олимпиада (Москва)
год
Год 2013
класс
Класс 5
задача
Номер 5.5

Проект осуществляется при поддержке и .

Источник

Из пяти монет две фальшивые одна из фальшивых монет тяжелее настоящей

Девять одинаковых по виду монет расположены по кругу. Пять из них настоящие, а четыре — фальшивые. Никакие две фальшивые монеты не лежат рядом. Настоящие монеты весят одинаково, и фальшивые — одинаково (фальшивая монета тяжелее настоящей). Как за два взвешивания на чашечных весах без гирь определить все фальшивые монеты?

Решение

Так как монет 9 и никакие две фальшивые не лежат рядом, то какие-то две настоящие монеты лежат рядом, а остальные монеты

чередуются (см. рис.). Заметим, что достаточно найти две настоящие монеты, лежащие рядом (этим расположение остальных монет определяется однозначно). Начав с произвольной монеты, пронумеруем монеты подряд числами от 1 до 9. Взвешивать можно разными способами.

Первый способ. Взвесим монеты 1 и 4. Возможны два случая:

Монеты 1 и 4 весят одинаково. Взвесим монеты 2 и 3. Если 2 и 3 весят одинаково, то они настоящие, поскольку лежат рядом. Пусть одна монета тяжелее (фальшивая), будем считать, что это монета 2, тогда монеты 3, 1 и 4 настоящие. Монеты 3 и 4 —две настоящие рядом.

Монеты 1 и 4 весят по-разному. Пусть монета 4 тяжелее (фальшивая). Тогда монеты 5, 3 и 1 —настоящие, а монета 2 —фальшивая. Взвесим монеты 9 и 6. Если они одинаково весят, то 7 и 8 —настоящие. Если же какая-то из них настоящая, то мы находим две настоящих рядом.

Второй способ. Разобьём монеты на три группы 147, 258, 369. В двух из них по одной фальшивой монете, а в ещё одной две фальшивые. Взвесим группы 147 и 258. Если одна из них перевесит, то в ней две фальшивые. Если равенство, то две фальшивые в оставшейся группе 369. После того как мы нашли группу, где две фальшивые, взвесим две монеты из этой группы. Если одна из них легче, то это и есть настоящая, а две другие —фальшивые. Если они равны, то они обе фальшивые. Две монеты, лежащие между найденными фальшивыми, —соседние настоящие.

Третий способ. Разобьём монеты на три группы 123, 456, 789. В двух из них по одной фальшивой, в ещё одной —две фальшивые. Взвесим группы 123 и 456. Если одна из чашек перевесила, то в ней две фальшивые. Если равенство, то две фальшивые в оставшейся группе 789. То есть мы нашли группу, в которой две фальшивые. В силу симметрии далее достаточно разобрать с случай, когда две фальшивые монеты среди монет 123. Так как по условию никакие две фальшивые монеты не стоят рядом, то монеты 1 и 3 фальшивые.

Читайте также:  Сколько стоят монеты 1426 года

Значит, монеты 9, 2 и 4 настоящие (см. рис.). Взвесим монеты 8 и 5. Если 8 тяжелее, то 5 настоящая, 4 и 5 две рядом стоящие настоящие, значит, 6 фальшивая, 7 настоящая, 8 фальшивая. Если 5 тяжелее, то аналогично 8 настоящая, 8 и 9 две рядом стоящие настоящие, значит, 7 фальшивая, 6 настоящая, 5 фальшивая. Наконец, если 5 и 8 одной массы, то они не могут обе быть настоящими, значит, они обе фальшивые, а 6 и 7 —обе настоящие.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 62
Год 2006
вариант
Класс 8
задача
Номер 4

Проект осуществляется при поддержке и .

Источник

Из пяти монет две фальшивые одна из фальшивых монет тяжелее настоящей

Известно, что среди нескольких монет имеется ровно одна фальшивая (отличается по весу от настоящих). С помощью двух взвешиваний на чашечных весах без гирь определите, легче или тяжелее фальшивая монета настоящей (находить ее не надо), если монет
а) 100;
б) 99;
в) 98?

Решение

а) Положим сначала на каждую чашу по 50 монет. Затем возьмем более тяжелую часть, разобьем ее на кучки по 25 монет и взвесим их. Если их массы равны, то фальшивая монета легче остальных, иначе — тяжелее остальных.
б) Разделим монеты на 3 кучки по 33 монеты и взвесим любые две из них. Если их массы равны, то сравним любую из них с третьей; если третья кучка легче, то и фальшивая монета легче остальных, иначе фальшивая монета тяжелее остальных.
Если же массы первых двух кучек различны, то взвесим более тяжелую из них с третьей. Если их массы окажутся равны, то фальшивая монета легче остальных, если же третья окажется легче, то фальшивая монета тяжелее остальных.
в) Отложим сначала две монеты в сторону, а остальные разобьем на 2 части по 48 монет и взвесим их. Если их массы равны, то взвесим две отложенные монеты с любыми двумя другими; если отложенные монеты окажутся легче, то и фальшивая монета легче остальных, иначе — тяжелее.
Если же массы первых двух кучек различны, то аналогично пункту а) разобьем более тяжелую на 2 части по 24 монеты и взвесим их. Если весы покажут равенство, то фальшивая монета легче остальных, иначе — тяжелее.

Источники и прецеденты использования

Кружок
Название ВМШ 57 школы
класс
Класс 7
год
Год 2001/02
Место проведения 57 школа
занятие
Номер 8
Название Про мунги и граммы
Тема Неопределено
задача
Номер 05

Проект осуществляется при поддержке и .

Источник

Решение задач на определение фальшивой монеты взвешиванием 2.0

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

Наиболее распространенные из таких задач — определение количества взвешиваний для выявления фальшивой монеты, если:

1) неизвестно какая она по весу;
2) известно, что она легче/тяжелее остальных.

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

1. Давайте сначала разберемся с 2 вариантом, который является частным случаем варианта 1.

Некоторое время назад, я на Хабре уже описывал решение такой задачи, но в одном из комментариев было замечание о немного странном первом разделении монет, по-этому предлагаю другой алгоритм решения. Хотя результат будет тот же и формула решения задачи остается та же:

N >= log3A,

где N — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону;
A — количество монет.
Которая выведена на основании опытов (за 1 взвешивание можно найти одну фальшивую из 3-х монет, за 2 — из 9, за 3 — из 27 и т.д.)

Читайте также:  1 грош 2014 монета

Сам алгоритм решения простой, и я покажу его на примерах

1) Пусть у нас есть 26 монет. Нужно найти одну, которая легче/тяжелее

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

A = 2 * B + C,

где A — количество монет;
B — частное от деления количества монет на 3, натуральное число, округленное в большую сторону;
C — остаток.

По условию задачи

При первом взвешивании будут сравниваться две группы: правая (ПГ) — 9 монет и левая (ЛГ) — 9 монет.

Далее у нас возможны два варианта:

1) фальшивая монета в левой/правой группе (9 монет)
2) фальшивая монета в остатке (8 монет)

для 1 варианта следующее деление на группы будет — 9 = 2 * 3 + 3;
для 2 варианта — 8 = 2 * 3 + 2

Ну и за одно взвешивание можно определить какая из 2 или 3 монет легче/тяжелее

Этот же результат я приведу в таблице

№ взвешивания Число монет ЛГ ПГ Остаток
1 26 9 9 8
2 8 3 3 2
2 9 3 3 3
3 2 1 1
3 3 1 1 1

по формуле — log326 =2.9656 — соответственно количество взвешиваний — 3.

еще пример:
число монет- 71. По формуле log371 =3.8800 — количество взвешиваний — 4. Проверяем

№ взвешивания Число монет ЛГ ПГ Остаток
1 71 24 24 23
2 23 8 8 7
2 24 8 8 8
3 7 3 3 1
3 8 3 3 2
4 2 1 1
4 3 1 1 1

Ну с алгоритм решения этих задач, я думаю, понятен.

2. Теперь перейдем к задачам, в которых не известно легче монета или тяжелее.

В данном случае я предлагаю такое первое действие: разделить монеты на четыре группы, три — с максимально одинаковым количеством монет, а в четвертой группе — остаток. Причем в остатке должны быть 1 или 2 монеты. То есть при делении на 3 частное округляется до меньшего натурального числа.

A = 3 * B + C,

где A — количество монет;
B — частное от деления количества монет на 3, натуральное число, округленное в меньшую сторону;
C — остаток.

Например, для 58-ми монет — это будет 58 = 3 * 19 + 1, для 23 = 3 * 7 + 2, для 15 = 3 * 5 + 0 и т. д.

Далее выполняем два взвешивания:
1) первая и вторая группы;
2) первая и третья группы;
и анализируем результат.
Здесь возможны четыре варианта:1, 2, 3 — это первая, вторая или третья группа отличаются по весу от двух остальных, или они равны, тогда нам повезло, так как фальшивая — в остатке. Так же два взвешивания помогают определить определить тяжелее фальшивая монета или легче. Кстати, если в остатке две монеты, то нужно выполнить еще 2 взвешивания для определения фальшивой монеты.

Теперь у нас есть задача: определить одну фальшивую монету из группы, которая легче/тяжелее.
Что касается формулы, то она примет следующий вид

N >= log3B + 2,

где N — максимально необходимое количество взвешиваний, натуральное число;
B — количество монет в группе после второго взвешивания.
А если учесть, что B = A/3, где A — количество всех монет, тогда получим:

log3B = log3A — 1,
N >= log3A + 1

1) если известно, что фальшивая монета легче/тяжелее, тогда максимальное число взвешиваний определяется по формуле:

N >= log3A

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

N >= log3A + 1

где N — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону;
А — количество монет.

Источник