Время на прочтение
3 мин
Количество просмотров 204K
Сегодня я снова хочу вернуться к теме о задаче нахождении фальшивой монеты методом взвешивания на весах без циферблата.
Наиболее распространенные из таких задач — определение количества взвешиваний для выявления фальшивой монеты, если:
1) неизвестно какая она по весу;
2) известно, что она легче/тяжелее остальных.
Или обратная задача: можно ли за определенное количество взвешиваний выявить фальшивую из заданного количества монет.
1. Давайте сначала разберемся с 2 вариантом, который является частным случаем варианта 1.
Некоторое время назад, я на Хабре уже описывал решение такой задачи, но в одном из комментариев было замечание о немного странном первом разделении монет, по-этому предлагаю другой алгоритм решения. Хотя результат будет тот же и формула решения задачи остается та же:
N >= log3A,
где N — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону;
A — количество монет.
Которая выведена на основании опытов (за 1 взвешивание можно найти одну фальшивую из 3-х монет, за 2 — из 9, за 3 — из 27 и т.д.)
Сам алгоритм решения простой, и я покажу его на примерах
1) Пусть у нас есть 26 монет. Нужно найти одну, которая легче/тяжелее
Первым действием буде разделение монет на три группы, в двух из которых число монет будет одинаковым, важно только что бы в третьей группе — остатке — было меньше монет, чем в каждой из двух других групп. То есть частое округляется к большему натуральному числу. То есть
A = 2 * B + C,
где A — количество монет;
B — частное от деления количества монет на 3, натуральное число, округленное в большую сторону;
C — остаток.
По условию задачи
26/3 = 8.666(6),
26 = 2 * 9 + 8,
При первом взвешивании будут сравниваться две группы: правая (ПГ) — 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 | 0 |
| 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 | 0 |
| 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 — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону;
А — количество монет.
Задача имеет решение, но оно будет актуально только для весов с достаточно вместительной чашей для взвешивания.
Из каждого следующего мешочка с монетами необходимо взять на одну монету больше, чем из предыдущего.
- из первого мешочка одна монета
- из второго мешочка две монеты
- из третьего мешочка три монеты
- из четвертого мешочка четыре монеты
- из пятого 5 монет
- из шестого 6 монет
- из седьмого 7 монет
- из восьмого 8 монет
- из девятого 9 монет
- из десятого десять монет
Итого у нас будет: 1+2+3+4+5+6+7+8+9=45 монет
Выкладываем их, не смешивая между собой, на чашу весов. Полученный вес в граммах сообщит нам в каком мешочке лежали фальшивые монеты. Если бы все монеты являлись настоящими, то на весах у нас должно было быть 45*10=450 грамм, любое отклонение в граммах укажет нам номер мешочка с фальшивками.
- 449 грамм – фальшивые монеты в первом мешочке
- 448 грамм – фальшивые монеты во втором мешочке
- 447 грамм -фальшивые монеты в третьем мешочке
- 446 грамм – фальшивые монеты в четвертом мешочке
- 445 грамм – фальшивые монеты в пятом мешочке
- 444 грамм – фальшивые монеты в шестом мешочке
- 443 грамма – фальшивые монеты в седьмом мешочке
- 442 грамма – фальшивые монеты в восьмом мешочке
- 441 грамм – фальшивые монеты в девятом мешочке
- 440 грамм – фальшивки в десятом мешочке
Задача абсолютно стандартная. Разобрана в миллиарде книг. Мне кажется, даже каждый школьный учитель её рассказывает в какой-то момент своим ученикам. Тем не менее задача встречается на олимпиадах в разных классах едва ли не чаще остальных. И все равно находятся люди, которые не понимают что к чему. Даже среди взрослых.
Давайте разберем одну из таких задач. Имеется 12 монет. Одна из которых фальшивая. Она отличается от подлинных только по весу (но заранее не известно в меньшую или в большую сторону). Как на чашечных весах определить фальшивку за 3 взвешивания и понять легче она или тяжелее, чем остальные? Как вы понимаете количество монет и взвешиваний может быть разным. От этого суть не изменится.
В любом случае нам надо будет разбить монеты на кучки, чтобы взвешивать их группами. В данной задаче удобно разбить монеты на 3 кучки по 4 монеты в каждой.
В какой-то момент в одном из случаев вам может показаться, что для некоторых случаев трех взвешиваний мало и надо бы четвертое. Ну или не получится определить легче или тяжелее фальшивка. Если так, то вы ошибаетесь, надо думать снова. Трех взвешиваний достаточно в любом случае. И в любом случае получится узнать легче фальшивка или тяжелее.
Для наглядности пронумеруем монеты: {1,2, 3, 4}; {5, 6,7, 8}; {9,10, 11, 12} и приступим к решению.
Первое взвешивание
Сравниваем первые две кучки монет {1,2, 3, 4} и {5, 6,7, 8}. Если весы находятся в равновесии, значит фальшивка в третьей кучке. Переходим к пункту а) во втором взвешивании.
Если весы не в равновесии, то фальшивка в одной из этих двух кучек, а в третьей все монеты настоящие. Запоминаем, какая кучка перевесила [я для примера буду считать, что перевесила кучка {1,2,3,4}, но если нет, то решение будет симметричным] и переходим к пункту б) во втором взвешивании.
Второе и третье взвешивания
а) Фальшивка среди монет {9,10, 11, 12}. Взвешиваем {1, 2, 3} и {9,10, 11}. Если весы в равновесии, значит фальшивая монета под номером 12. третьим взвешиванием узнаем, легче она или тяжелее.
Если не равны, значит, фальшивка среди монет 9, 10, 11. При этом уже после второго взвешивания мы будем точно знать легче фальшивка или тяжелее. Третьим взвешиванием однозначно находим фальшивку: взвешиваем монеты 9 и 10. Если они равны, то фальшивка – 11. Если не равны, то фальшивка либо 9, либо 10 в зависимости от того, какая монета легче (оригинал или фальшивка), ведь эту информацию мы узнали после второго взвешивания.
б) Фальшивка в одной из первых двух кучек. Для того, чтобы понять в какой, взвесим {1, 2, 5} и {3, 4, 9} [опечатки нет, монета 9 заведомо настоящая]. Если весы в равновесии, значит, фальшивка среди 6, 7, 8, причем одна из них легче остальных [это потому что мы для ясности рассматриваем случай, когда первое взвешивание показало, что первая кучка тяжелее]. Третьим взвешиванием сравниваем монеты 6 и 7. Если они равны, то фальшивка – 8. Если нет, то фальшивка та, которая весит меньше.
Если весы после второго взвешивания оказались не в равновесии, возникает два случая
б.1) Если перевесила кучка {1, 2, 5}, то фальшивка среди монет 1 и 2. Третьим взвешиванием мы узнаем, какая из них тяжелее и это и есть фальшивка.
б.2) Если перевесила кучка {3, 4, 9}, то фальшивка среди монет 3, 4 и 5. Если фальшивка – 5, то она будет легче других. А если 3 или 4, то фальшивка тяжелее настоящих. Третьим взвешиванием сравниваем монеты 3 и 4. Если одна из них тяжелее, то это фальшивка. Если они равны, то фальшивка – 5 и она легче.
Всё. Как вам задачка? Как видите, рассмотрены все случаи и трех взвешиваний достаточно даже для того, чтобы определить не только фальшивку, но и её относительный вес.
Ещё интересно:
Взвешивания и переливания
Вероятности
Есть 10 мешков с золотом. В каждом по 10 монет. В девяти мешках монеты настоящие, а в одном – все фальшивые. Одна настоящая монета весит 5 грамм, а фальшивая – 4 грамма. Есть весы, показывающие вес в граммах.
Необходимо за одно взвешивание точно определить, в каком мешке фальшивые монеты
Мешки можно раскрывать и вытаскивать монеты
Ответ:
Пронумеруем мешки от 1 до 10. Вытащим из первого 1 монету, из второго 2, из третьего 3 и так далее. Затем возьмем всю эту кучу монет и положим на весы. Если бы они все были настоящие, то общий вес составил бы 275 грамм (т.к. мы вытащили в общей сложности 55 монет). Но в одном из мешков были фальшивые. Если это был первый мешок, то вес будет на 1 грамм меньше (т.к. мы взяли оттуда 1 монету). Если фальшивые были во втором, то на 2 грамма меньше. И так далее.
Как найти фальшивую монету двумя взвешиваниями – логическая задача
Загадки на логику
Перед нами логическая задача, чтобы решить которую нужно немного пораскинуть мозгами.
Итак условия задачи следующие:
На столе лежат 9 монет. Известно, что одна из монет фальшивая. Фальшивая монета весит меньше чем остальные. У нас имеются весы для взвешивания.
Вопрос:
Как при помощи двух взвешиваний найти фальшивую монету?
.jpg)
Внимание!
Ниже приведен правильный ответ!
Правильный ответ:
Вначале на каждую чашу весов нужно положить по три монеты.
Если после этого весы приходят в равновесие, значит среди этих монет нет фальшивой, берем две из трех оставшихся монет, кладем на разные чаши весов. Если фальшивая монета среди этих двух, то мы поймем на какой она чаше, эта чаша поднимется выше.
А если весы снова придут в равновесие, значит фальшивая монета осталась на столе.
Если же при первом взвешивании весы не пришли в состояние равновесия, значит фальшивая монета уже находится на весах, берем 2 монеты из тех трех, что оказались легче, кладем по 1 на каждую чашу, если одна чаша поднялась выше, значит фальшивая монета на ней, если чаши уравновесились, значит фальшивая – оставшаяся третья.
Похожие новости
Все загадки
Все загадки
Все загадки
Все загадки
Все загадки
Все загадки
