Разделить монеты

Знаем на 5! — ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ НА ВЗВЕШИВАНИЕ

Разделить монеты

У Буратино есть 27 золотых монет. Но известно, что Кот Базилио заменил одну монету на фальшивую, а она по весу тяжелее настоящих.

Как за три взвешивания на чашечных весах без гирь Буратино определить фальшивую монету? 
Решение
Разделим монеты на 3 кучки по 9 монет.

Положим на чаши весов первую и вторую кучки; по результату этого взвешивания мы точно узнаем, в какой из кучек находится фальшивка (если весы покажут равенство, то она — в третьей кучке).

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

Золушка

Мачеха послала Золушку на рынок. Дала ей девять монет: из них 8 настоящих, а одна фальшивая – она легче чем настоящая. Как найти ее Золушке за два взвешивания? 
Решение
Разделим 9 монет на 3 равных кучки.

Положим на чаши весов первую и вторую кучки; по результату этого взвешивания мы точно узнаем, в какой из кучек находится фальшивка (если весы покажут равенство, то она — в третьей кучке).

Остается из трех монет определить более легкую: кладем на чаши весов по 1 монете — фальшивкой является более легкая; если же на весах равенство, то фальшивой является третья монета.

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

Среди 101 одинаковых по виду монет одна фальшивая, отличающаяся по весу. Как с помощью чашечных весов без гирь за два взвешивания определить, легче или тяжелее фальшивая монета? Hаходить фальшивую монету не требуется. 
Решение
Взвешиваем 50 и 50 монет: два случая. 1 случай. Равенство.

Берем оставшуюся монету и ставим ее в левую кучку вместо одной из имеющихся там: а) Левая кучка тяжелее => фальшивая монета тяжелее; б) Левая кучка легче => фальшивая монета легче. 2 случай. Неравенство.

Берем более тяжелую кучку и разбиваем ее на две кучки по 25 монет: а) Вес кучек одинаковый => фальшивая монета легче; 

б) Вес кучек неодинаковый => фальшивая монета тяжелее.

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

Имеется 8 монет. Одна из них фальшивая и легче настоящей монеты. Определите за 3 взвешивания какая из монет фальшивая. 
Решение
Делим монеты на две равные кучки – по 4 монеты в каждой. Взвешиваем.

Ту кучку, которая легче, опять делим на две одинаковых кучки – теперь по две монеты в каждой. Взвешиваем. Определяем, какая из них легче. Кладем на чаши весов по 1 монете из этой кучки. Фальшивая та, которая легче. Задача решена.

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

Имеется 10 монет. Одна из них фальшивая и легче настоящей монеты. Как, с помощью чашечных весов без гирь, определить какая из монет фальшивая? 
Решение
Разделим 10 монет на 2 равных кучки – по 5 монет. Положим на чаши весов. Определим, в какой из этих кучек находится фальшивая монета.

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

Теперь кладем на чаши весов по 1 монете из этой кучки – фальшивкой является более легкая. Задача решена.

Лиса Алиса и Кот Базилио

Лиса Алиса и Кот Базилио – фальшивомонетчики. Базилио делает монеты тяжелее настоящих, а Алиса – легче. У Буратино есть 15 одинаковых по внешнему виду монет, но какая-то одна – фальшивая.

Как двумя взвешиваниями на чашечных весах без гирь Буратино может определить, кто сделал фальшивую монету – Кот Базилио или Лиса Алиса? 
Решение
Буратино может разделить свои монеты на три кучки по 7, 4, 4, или по 5, 5, 5, или по 3, 6, 6, или по 1, 7, 7 монет.

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

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

Если же при первом взвешивании весы оказались не в равновесии, значит, все монеты в оставшейся кучке настоящие. Тогда Буратино уберет с весов легкую кучку, а монеты из тяжелой кучки разделит на две равные части и положит на весы (если в кучке было 5 или 7 монет, предварительно добавит к ним одну настоящую монету). Если при втором взвешивании весы оказались в равновесии, значит, фальшивая монета легче настоящих, а если нет, то тяжелее. Задача решена.

Буратино

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

Как Буратино определить фальшивую монету? Какое минимальное число взвешиваний ему потребуется? 
Решение
Разделим монеты на 2 равных кучки – по 2 монеты. Положим на чаши весов. В более легкой кучке находится фальшивая монета.

Теперь кладем на чаши весов по 1 монете из этой кучки – фальшивкой является более легкая. Буратино потребуется два взвешивания. Задача решена.

Дядюшка Скрудж

Дядюшке Скруджу принесли 8 одинаковых по виду монет, одна из которых не золотая, а фальшивая и легче других. Помогите Скруджу определить фальшивую монету. Какое минимальное число взвешиваний ему потребуется? 
РешениеРазделим монеты на кучки по 3, 3, 2 монеты.

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

 

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

Задача решена.

Источник: https://znaemna5.ucoz.ru/index/primery_reshenija_zadach_na_vzveshivanie/0-105

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

Разделить монеты

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

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 монет легче/тяжелее

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

№ взвешиванияЧисло монетЛГПГОстаток
126998
28332
29333
32110
33111

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

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

№ взвешиванияЧисло монетЛГПГОстаток
171242423
223887
224888
37331
38332
42110
43111

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

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 — количество всех монет, тогда получим:

Итог:

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

N >= log3A

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

Поделиться:
Нет комментариев

    Добавить комментарий

    Ваш e-mail не будет опубликован. Все поля обязательны для заполнения.

    ×
    Рекомендуем посмотреть