Как составить алгоритм по взвешиванию монет - Сайт, где вы сможете решить свои вопросы

Время на прочтение
3 мин

Количество просмотров 204K

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

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

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

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

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

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

N >= log₃A,

где 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

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

еще пример:
число монет- 71. По формуле log₃71 =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 >= log₃B + 2,

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

log3B = log₃A — 1,

N >= log₃A + 1

Итог:

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

N >= log₃A

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

N >= log₃A + 1

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

Источник

Содержание

Актуализация
Задачи на взвешивание
Задачи на переливание
Заключение
Литература

Актуальность исследования

Математические задачи на переливание и взвешивания известны с древности. Сейчас их можно встретить в олимпиадных задачах или в компьютерных играх – головоломках. Классическая задача о фальшивых монетах (ФМ) в последнее время нашла применение в теории кодирования и информации – для обнаружения ошибки в коде. Цель нашей работы – найти и описать алгоритмы решения таких задач. Задачи на переливание и взвешивание относятся к типу задач комбинаторного поиска; их решение сводится к работе с информацией.

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

Задачи на взвешивание.

Задачи на взвешивание —это тип задач, в которых требуется установить тот или иной факт (выделить фальшивую монету среди настоящих, отсортировать набор грузов по возрастанию веса и т. п.) посредством взвешивания на рычажных весах без циферблата. Чаще всего в качестве взвешиваемых объектов используются монеты. Реже имеется также набор гирек известной массы.

Очень часто используется постановка задачи, требующая определить либо минимальное число взвешиваний, потребное для установления определённого факта, либо привести алгоритм определения этого факта за определенное количество взвешиваний. Реже встречается постановка, требующая ответить на вопрос, возможно ли установление определённого факта за некоторое количество взвешиваний. Часто такая постановка является не очень удачной, так как при положительном ответе на вопрос задача чаще всего сводится к построению алгоритма, а отрицательный почти не встречается.

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

Изучив литературу по данной теме, мы пришли к выводу о том, что все задачи на взвешивание можно разделить на следующие типы:

Задачи на сравнения с помощью весов.

Задачи на взвешивания на весах с гирями.

Задачи на взвешивания на весах без гирь.

Задача 1.1 Самая классическая головоломка.

Одна из 9 монет фальшивая, она весит легче настоящей. Как определить фальшивую монету (ФМ) за 2 взвешивания?

Решение. Ключевая идея решения таких задач – правильная трисекция, т. е. последовательное деление множества вариантов на три равные части. После первой трисекции должно остаться не более трех подозрительных монет, после второй – не более одной ПМ, которой и является ФМ.

Взвешиваем монеты 123 и 456 , отложив 789.

Если 123 легче, то среди них ФМ; тяжелее, то ФМ среди 456; равны, то ФМ среди 789.

Далее взвешиваем первую и вторую монеты из кучки, где есть ФМ. Если весы в равновесии, то третья монета фальшивая. Если не в равновесии, то ФМ монета на той чашке, которая легче.

Гипотеза. Существуют алгоритмы для определения ФМ за наименьшее количество взвешиваний в случае, если известно, что ФМ тяжелее или легче настоящей (алгоритм 1) и в случае, если это неизвестно (алгоритм 2).

Обобщение 1. Пусть имеется К монет и одна из них – фальшивая (К больше двух). Известно, что она легче настоящей. За какое наименьшее количество взвешиваний можно найти ФМ?

Решение.

АЛГОРИТМ 1. Выложим на чаши по К:3 монет, остальные отложим (если количество монет не кратно 3, то кладем на чаши одинаковое число монет, равное (К-1):3 или (К+1):3 в зависимости от того, какое из них натуральное). Далее, если одна из чаш перевесила, то ФМ на другой чаше, а в случае равновесия – ФМ среди отложенных. Дальше повторяем это для группы монет, среди которых находится ФМ.

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

Рассмотрим задачу с гирями, где также можно применить это правило.

Задача 1.2 Имеется 9 гирек-эталонов весом 100,200,…,900 гр. Одна из них побывала в руках нечестных торговцев и теперь весит на 10 гр. меньше. Как найти ее за 2 взвешивания?

Найдем две различные тройки гирь, одинаковые по весу. Например, взвесим 100+500+900 и

200+600+700 и останутся 300+400+800. Рассуждая также, найдем группу с испорченной гирей. Затем можно найти испорченную гирьку, добавив заведомо настоящие. Например, 200+600 и 700+100.

Следующая задача отличается тем, что заранее неизвестно –легче или тяжелее ФМ чем настоящая.

Задача 1.3 Из трех монет одна фальшивая, причем неизвестно, легче она или тяжелее настоящей. Как найти ее за два взвешивания и определить, легче она или тяжелее настоящей?

В этой задаче 6 вариантов ответа (каждая из трех монет может быть либо легче, либо тяжелее настоящей).

Ответ: да, можно, при этом наименьшее количество взвешиваний равно 2.

Задача 1.4 Имеются 4 гирьки с маркировками 1г, 2г, 3г, 4г. Одна из них дефектная – более легкая или более тяжелая. Можно ли за два взвешивания найти эту гирю и определить, легче она или тяжелее настоящей?

Здесь 8 вариантов ответа. Взвесим 1г +2г и 3г, затем 1г+3г и 4г гири.

Получим следующую таблицу вариантов:

Ответ: да, можно.

Обобщение 2. Пусть имеется К монет и одна из них фальшивая. За какое наименьшее количество взвешиваний можно определить ФМ и легче она или тяжелее?

Сначала надо узнать количество вариантов ответов. Их К*2, так как каждая монета может быть легче или тяжелее. Затем определим количество взвешиваний. Одно взвешивание определяет три варианта: <,>,=. Два взвешивания определяет 9 вариантов: <<, <=, <>, =<, =>, <>, >=, >>, ==(их 3*3, но в данной задаче вариант == невозможен).Три взвешивания определяет 3*3*3= 27 вариантов и т.д.

АЛГОРИТМ 2. Делим монеты на три группы. Если К не делится на 3, то либо (К-1) делится на 3, тогда на весы кладем по (К-1):3 монет и останется (К-1):3 монет и еще 1 монета. Либо (К-2) делится на 3, тогда на весы кладем по (К-2):3 монет и останется (К-2):3 монет и еще 2 монеты. Взвешивая первую и вторую группы, а потом вторую и третью, Делаем вывод, в какой группе находится ФМ. Если весы оказались в обоих случаях в равновесии, то ФМ в отложенных монетах и тогда, соответственно количеству отложенных монет, за одно или два взвешивания мы найдем ФМ и легче или тяжелее она настоящей (сравнивая их с настоящими монетами). Далее, если ФМ не оказалась в отложенных монетах, то мы уже можем определить, легче или тяжелее она настоящей. И затем действуем по алгоритму 1. Обозначив группы монет 1, 2, 3, покажем взвешивания 1и2 затем 1и3 в данной таблице.

Зная, тяжелее или легче ФМ настоящей, мы можем воспользоваться алгоритмом1, описанным в обобщении 1. Как видим, здесь деление на три по возможности равные части.

Проверим алгоритм при большем количестве монет.

Задача 1.5 Имеется 80 монет, одна из которых фальшивая. За какое наименьшее число взвешиваний на весах без гирь можно найти фальшивую монету?

Решение. Проводим первое взвешивание: кладем на чаши по (80-2):3=26 монет. В случае равновесия- ФМ среди оставшихся 28; взвешивая настоящие 26 монет с 26 «подозрительными», мы определим, легче ФМ или тяжелее настоящей (в случае равновесия, она в оставшихся двух и далее надо еще 2 взвешивания). Если при первом взвешивании весы не оказались в равновесии, то фальшивая – в какой–то из чаш на весах. Сравниваем первую группу монет с настоящими из третьей и делаем вывод. Потом делим ту группу монет, где есть фальшивая на 9, 9, 8, взвешиваем, далее взвешиваем по 3 монеты, а затем – по одной.

Ответ: за 5 взвешиваний.

Алгоритм 1. Взвешиваем первые две группы монет.(выделенные цветом).

Кол-во монет	1 деление	2 деление	3 деление	4 деление
27	9 9 9	9 по 3,3 и 3	3 по 1,1 и 1
28	9 9 10	10 по 3,3 и 4 9 по 3,3 и 3	3 по 1,1 и 1 4 по 1,1 и 2	2 по 1 и 1
29	10 10 9	10 по 3,3 и 4 9 по 3,3 и 3	3 по 1,1 и 1 4 по 1,1 и 2	2 по 1 и 1
К кратно 3	К:3 К:3 К:3	Далее делим аналогично	Вообще, пусть число монет k удовлетворяет неравенству и среди них имеется одна фальшивая, о которой известно, легче она или тяжелее, чем настоящие. Тогда наименьшее число взвешиваний на чашечных весах без гирь, необходимых для нахождения фальшивой монеты, равно n.
К:3 с ост. 1	(К-1):3 (К-1):3 (К-1):3+1
К:3 с ост. 2	(К+1):3 (К+1):3 (К+1):3-1

Если монет 2 или 3, то для нахождения среди них фальшивой монеты требуется 1 взвешивание.
Если монет от 4 до 9 включительно, то наименьшее число взвешиваний для нахождения фальшивой монеты равно 2.
Если монет от 10 до 27 включительно, то оно равно 3.
Если монет от 28 до 81 включительно (в связи с тем, что 81 = 3*27), то наименьшее число взвешиваний равно 4.

Закономерность. Числа 9, 27, 81 являются последовательными степенями тройки, а числа 4, 10, 28 – соответственно, предыдущими степенями тройки, увеличенными на 1: 4 = 3+1, 10 = 32+1, 28 = 33+1.

Алгоритм 2. Во 2 взвешивании на весы кладем вторую и третью группы монет. В остальных взвешиваем 1 и 2 группы монет.

Кол-во

монет

1 деление

2 взвешивания

2 деление

3 деление

4 деление

9 по 3,3 и 3

3 по 1,1 и 1

9+1

10 по 3,3 и 4

9 по 3,3 и 3

1 и 1

3 по 1,1 и 1

4 по 1,1 и 2

2 по 1 и 1

9+2

10 по 3,3 и 4

9 по 3,3 и 3

1 и 1

4 по 1,1 и 2

1 и 1

3 по 1,1 и 1

2 по 1 и 1

К кратно 3

К:3

Если в первом либо во втором случаях весы не были в равновесии, то можно определить группу монет, содержащих ФМ, а также сделать вывод о том, легче или тяжелее она, чем настоящая монета. Далее действуем по алгоритму 1.

(иначе *)

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

К:3 с ост. 1

(К-1):3

(К-1):3+1

(К-1):3

(К-1):3+1

К:3 с ост. 2

(К-2):3

(К-2):3+2

(К-2):3

(К-2):3+2

*Во втором взвешивании находим группу монет, содержащую ФМ. Если в 1 и 2 взвешиваниях весы были в равновесии, то ФМ среди оставшихся одной или двух. Если осталась 1 монета, то она ФМ и взвешивая ее с настоящей, узнаем, легче или тяжелее она, чем настоящая монета. Если осталось 2, то взвешивая их между собой, а затем одну из них с настоящей, отвечаем на вопрос задачи. Если в первом либо во втором случаях весы не были в равновесии, то можно определить группу монет, содержащих ФМ, а также сделать вывод о том, легче или тяжелее она, чем настоящая монета.

Если монет 2, то задача 2 не имеет решения.
Если монет 3, то для нахождения среди них фальшивой монеты требуется 2 взвешивания.
Если монет от 4 до 9 включительно, то наименьшее число взвешиваний для нахождения фальшивой монеты равно 3.
Если монет от 10 до 27 включительно, то оно равно 4.
Если монет от 28 до 81 включительно (в связи с тем, что 81 = 3*27), то наименьшее число взвешиваний равно 5.

Подведем итог задачам.

Пусть число монет k удовлетворяет неравенству

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

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

Гипотеза подтвердилась. Мы описали алгоритмы для определения ФМ за наименьшее количество взвешиваний в случае, если известно, что ФМ тяжелее или легче чем настоящая (алгоритм 1) и в случае, если это неизвестно (алгоритм 2).

Задачи на переливание.

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

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

– все сосуды без делений,

– нельзя переливать жидкости “на глаз”

– невозможно ниоткуда добавлять жидкости и никуда сливать.

Мы можем точно сказать, сколько жидкости в сосуде, только в следующих случаях:

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

Чаще всего используются словесный способ решения (т.е. описание последовательности действий) и способ решения с помощью таблиц, где в первом столбце (или строке) указываются объемы данных сосудов, а в каждом следующем — результат очередного переливания. Таким образом, количество столбцов (кроме первого) показывает количество необходимых переливаний. Эти же способы (словесный и табличный) использовались и при решении задач на взвешивание. Однако мы обнаружили еще один интересный способ, которым можно решать такие задачи. Это метод математического бильярда. Я.И. Перельман в своей книге «Занимательная геометрия» предложил решать задачи на переливание с помощью «умного» шарика. Для каждого случая предлагалось строить бильярдный стол особой конструкции из равносторонних треугольников, длины двух сторон которого численно равны объему двух меньших сосудов. Далее, из острого угла этого стола вдоль одной из сторон нужно «запустить» шарик, который по закону «угол падения равен углу отражения» будет сталкиваться с бортами стола, показывая тем самым последовательность переливаний. На бортах стола нанесена шкала, цена деления которой соответствует выбранной единице объема. В результате движения шарик либо ударяется о бортик в нужной точке (тогда задача имеет решение), либо не ударяется (тогда считается, что задача решения не имеет). Бильярдный шар может перемещаться только вдоль прямых, образующих сетку на параллелограмме. После удара о стороны параллелограмма шар отражается и продолжает движение вдоль выходящего из точки борта, где произошло соударение, полностью характеризует, сколько воды находится в каждом из сосудов.

Старинная занимательная задача.

Восьмиведерный бочонок заполнен доверху квасом. Двое должны разделить квас поровну. Но у них есть только два пустых бочонка, в один из которых входит 5 ведер, а в другой – 3 ведра кваса. Спрашивается, как они могут разделить квас, пользуясь только этими тремя бочонками?

2 3	В рассматриваемой задаче стороны параллелограмма должны иметь стороны 3 единицы и 5 единиц. По горизонтали будем откладывать количество кваса в ведрах в 5-ведерном бочонке, а по вертикали – в 3-ведерном бочонке.

Пусть шар находится в точке О и после удара попадает в точку А. Это означает, что 5-ведерный бочонок наполнен до краев, а 3-ведерный пуст. Отразившись упруго от правого борта, шар покатится вверх и влево и ударится о верхний борт в точке с координатами 2 по горизонтали и 3 по вертикали. Это означает, что в 5-ведерном бочонке осталось всего 2 ведра кваса, а ведра из него перелили в меньший бочонок. Отразившись упруго от верхнего борта, шар покатится вниз и влево и ударится о нижний борт в точке с координатами 2 по горизонтали и 0 по вертикали. Это означает, что в 5-ведерном бочонке осталось 2 ведра кваса, а из 3-ведерного сосуда перелили квас в 8-ведерный бочонок. Отразившись упруго от нижнего борта, шар покатится вверх и влево и ударится о левый борт в точке с координатами 0 по горизонтали и 2 по вертикали. Это означает, из 5-ведерного бочонка вылили 2 ведра кваса в 3-ведерный бочонок. Отразившись упруго от левого борта, шар покатится вправо и ударится о правый борт в точке с координатами 5 по горизонтали и 2 по вертикали. Это означает, в 5-ведерный бочонок налили 5 ведер кваса, а в 3-ведерном бочонке осталось 2 ведра. Отразившись упруго от правого борта, шар покатится вверх и влево и ударится о верхний борт в точке с координатами 4 по горизонтали и 3 по вертикали. Это означает, из 5-ведерного бочонка вылили 1 ведро кваса в 3-ведерный бочонок, где стало 3 ведра, а в 5-ведерном осталось 4 ведра. Отразившись упруго от верхнего борта, шар покатится вниз и влево и ударится о нижний борт в точке с координатами 4 по горизонтали и 0 по вертикали. Это означает, что в 5-ведерном бочонке осталось 2 ведра кваса, а из 3-ведерного бочонка перелили квас в 8-ведерный бочонок. Задача решена с помощью 7 переливаний. Одновременно с этим заполняем таблицу:

№ переливаний	0	1	2	3	4	5	6	7
8 л	8	3	3	6	6	1	1	4
5 л	0	5	2	2	0	5	4	0
3 л	0	0	3	0	2	2	3	4

Посмотрим, как будет вести себя наш бильярдный шарик, если сначала наполнить 3-ведерный бочонок квасом.

№	8	5	3
0	8	0	0
1	5	0	3
2	5	3	0
3	2	3	3
4	2	5	1
5	7	0	1
6	7	1	0
7	4	1	3
8	4	4	0

Наглядно видно, что данная задача решена в результате 8 переливаний.

Решим методом бильярда знаменитую задачу Пуассона.

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

понравилась задача про два сосуда. «Эта задача определила мою судьбу, – говорил он впоследствии. – Я решил, что непременно буду математиком

Задача. Некто имеет 12 пинт вина и хочет подарить из него половину. Но у него нет сосуда в 6 пинт. У него 2 сосуда. Один в 8, другой в 5 пинт. Спрашивается, каким образом налить 6 пинт в сосуд в 8 пинт?

Построим бильярдный стол в виде параллелограмма. Стороны возьмем равными 5 единиц и 8 единиц. По горизонтали будем откладывать количество вина в сосуде в 8 пинт, а по вертикали – в 5 пинт. Рассуждаем аналогично.

Заполним таблицу.

№ переливаний	0	1	2	3	4	5	6	7
12 л	12	4	4	9	9	1	1	6
5 л	0	0	5	0	3	3	5	0
8 л	0	8	3	3	0	8	6	6

Получается 7 переливаний. Однако, если налить сначала в сосуд в 5 пинт, то потребуется 18 переливаний.

Всегда ли задачи этого типа имеют решения?

Метод бильярдного шара можно применить к задаче о переливании жидкости с помощью не более чем трех сосудов. Если объемы двух меньших сосудов не имеют общего делителя (т. е. взаимно просты), а объем третьего сосуда больше или равен сумме объемов двух меньших, то с помощью этих трех сосудов можно отмерить любое целое число литров, начиная с 1 литра и кончая объемом среднего сосуда. Имея, например, сосуды вместимостью 15, 16 и 31 литр, можно отмерить любое количество воды от 1 до 16 литров. Такая процедура невозможна, если объемы двух меньших сосудов имеют общий делитель. [10] Когда объем большего сосуда меньше суммы объемов двух других, возникают новые ограничения. Если, например, объемы сосудов равны 7, 9 и 12 литрам, то у ромбического стола надо отсечь нижний правый угол. Тогда шар сможет попасть в любую точку от 1 до 9, за исключением точки 6. Несмотря на то, что 7 и 9 взаимно просты, отмерить 6 литров воды оказывается невозможным из-за того, что самый большой сосуд имеет слишком маленький объем. Легко видеть, что точки с цифрой 6 образуют на диаграмме правильный треугольник, и мы не можем никак попасть на этот треугольник из любой другой точки, лежащей вне него. Отметим также, что обобщение метода математического бильярда на случай четырех сосудов сводится к движению шара в пространственной области (параллелепипеде). Но возникающие при этом трудности изображения траекторий делают метод неудобным.

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

Заключение

Подведя итог, можно сказать, что в ходе исследовательской работы:

1. Собран теоретический и практический материал по проблеме исследования.

2. По итогам данной работы нами были систематизированы задачи на переливания и взвешивание.

3. Составлены алгоритмы решения.

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

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

Список использованных источников

1. Гальперин Г.А., Математические бильярды — М.: Наука,- 1990.- 290с.

2. Гальперин Г.А., Периодические движения бильярдного шара/ Квант. 1989. № 3.

3. Ф.Ф.Нагибин, Е.С.Канин Математическая шкатулка М.: Просвещение, 1988

4. Я.И.Перельман Занимательная геометрия М.: ГИФМЛ, 1959

5. В.Н.Русанов Математические олимпиады младших школьников М., Просвещение, 1990

6. Е.П.Коляда Развитие логического и алгоритмического мышления учащихся //Информатика и образование. 1996. N1.

7. И.Ф.Шарыгин Математический винегрет М., АГЕНТСТВО “ОРИОН”, 1991

8. http://www.i-u.ru/biblio/archive/makovelskiy_logic_history/4.aspx (сайт русского гуманитарного интернет университета, статья история логики)

9. http://ru.wikipedia.org/wiki/ (ВИКИПЕДИЯ-современная энциклопедия)

10. http://wiki.syktsu.ru/index.php/Способы решения логических задач.

11. Байиф Ж-К. Логические задачи. М.: Мир, 1983. 171 с.

12. Балк М.Б., Балк Г.Д. Математика после уроков. М.: Просвещение,1971.

13. Барабанов А.И., Чернявский И.Я. Задачи и упражнения по математике. Саратов: Саратовский ун-т, 1965. 234 с.

14. Барр С. Россыпи головоломок. М.: Мир, 1978. 414 с.

15. Беррондо М. Занимательные задачи. М.: Мир, 1983. 229 с.

16. Болл У., Коксетер Г. Математические эссе и развлечения. М.: Мир,1986. 472 с.

17. Перельман Я.И. Занимательная арифметика.

18. Перельман Я.И. Занимательная алгебра.

19. Перельман Я.И. Занимательная геометрия.

20. Перельман Я.И. Живая математика.

21. http://m.10-bal.ru/reshebnik/19177/index.html?page=5

Источник

Задачи на взвешивание — тип олимпиадных задач по математике, в которых требуется установить тот или иной факт (выделить фальшивую монету среди настоящих, отсортировать набор грузов по возрастанию веса и т. п.) посредством взвешивания на рычажных весах без циферблата. Чаще всего в качестве взвешиваемых объектов используются монеты. Реже имеется также набор гирек известной массы.

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

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

Анализ с точки зрения теории информации[править | править код]

При решении этих задач часто используется следующее соображение^[1]: весы могут пребывать в одном из трёх состояний:

перевесила левая чашка;
перевесила правая чашка;
чашки находятся в равновесии.

Таким образом, единственное взвешивание сообщает нам один разряд в троичной системе счисления, а взвешиваний позволяют разделить не более чем ${displaystyle 3^{m}}$ различных ситуаций. Особенно это соображение полезно при доказательстве минимальности необходимого количества взвешиваний и при доказательстве невозможности определить некий факт за данное количество взвешиваний (в последнем случае обычно требуется комбинаторный анализ пространства возможных ответов).

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

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

Задача отыскания одной фальшивой монеты, вес которой может быть больше или меньше веса правильной монеты[править | править код]

Из нетривиальных задач на взвешивание изучена и хорошо известна задача, в которой требуется определить, имеется ли среди 12 монет фальшивая и, если имеется, найти ее и определить ее относительный вес. Эта задача и ее решение впервые были опубликованы в 1945 Р. Л. Гудстейном в «The Mathematical Gazette» (см. статью ^[2]). В данной задаче существует статический алгоритм (т. е. алгоритм, в котором взвешивания определены заранее и не зависят от результатов предыдущих взвешиваний), обеспечивающий нахождение фальшивой монеты за 3 взвешивания. Этот алгоритм можно представить следующей таблицей:

0 0 1 0 0 2 2 2 1 1 1 2

0 1 0 2 2 2 1 0 0 1 2 1

1 0 0 2 1 0 0 2 2 2 1 1

В таблице номера столбцов соответствуют номерам монет, а строки определяют взвешивания: 0 – монета не участвует во взвешивании, 1 – кладется на первую чашу, 2 – кладется на вторую чашу. В результате трех взвешиваний определяется так называемый синдром, т. е. тройка чисел, которая однозначно указывают на номер фальшивой монеты. Этот номер равен номеру столбца с соответствующим синдромом. Например, если синдром равен (2,2,0), то фальшивой является монета с номером 6 и она тяжелее эталонных монет.

В других вариантах подобных задач может быть указано, что нужно найти фальшивую монету среди 13 (без определения ее относительного веса), если известно, что в тестируемой группе точно одна фальшивая монета. Очевидно, для такой задачи можно использовать уже построенный выше алгоритм, предварительно отложив одну монету и сделать вывод о ее подлинности по результатам взвешиваний остальных 12-ти монет.

Достаточно общую картину о числе монет n, из которых можно найти одну фальшивую за m взвешиваний, можно составить из ^[3]. Пусть из данного количества монет можно найти фальшивую за m взвешиваний. Тогда максимально возможное количество монет равно:

если относительный вес фальшивой монеты известен заранее – ${displaystyle 3^{m}}$ (независимо от наличия запаса настоящих монет);

если относительный вес не известен и его требуется узнать:

– при отсутствии запаса настоящих монет – ${displaystyle (3^{m}-3)/2}$ ;

– при наличии – ${displaystyle (3^{m}-1)/2}$ ,

если не требуется узнать относительный вес:

– при отсутствии запаса настоящих монет – ${displaystyle (3^{m}-1)/2}$ ;

– при наличии – ${displaystyle (3^{m}+1)/2}$ .

Обобщения[править | править код]

Обобщенное описание задач такого типа приведено в ^[4].

Пусть $mathbb{R}^n$ — -мерное евклидово пространство, ${displaystyle [mathrm {e} ^{1},mathrm {e} ^{2}]}$ — скалярное произведение векторов ${displaystyle mathrm {e} ^{1}}$ и ${displaystyle mathrm {e} ^{2}}$ из ${displaystyle mathbb {R} ^{n},}$ Для элементов ${displaystyle mathrm {e} =(e_{1},dots ,e_{n})in mathbb {R} ^{n}}$ и подмножеств ${displaystyle E={mathrm {e} ^{j}}subseteq mathbb {R} ^{n},}$ используются операции ${displaystyle (cdot )^{*}}$ и ${displaystyle (cdot )^{+}}$ результаты применения которых определяются соотношениями ${displaystyle mathrm {e} ^{*}=(sign(e_{i}))_{i}}$ ; ${displaystyle E^{*}={(mathrm {e} ^{j})^{*}}}$ , ${displaystyle mathrm {e} ^{+}=(|sign(e_{i})|)_{i}}$ , ${displaystyle E^{+}={(mathrm {e} ^{j})^{+}}.}$ Символом ${displaystyle I^{n}}$ будем обозначать дискретный [−1; 1]-cube в $mathbb{R}^n$ ; т. е. множество всех последовательностей длины над алфавитом . Множество ${displaystyle I_{t}^{n}={mathrm {x} in I^{n}|w(mathrm {x} )leq t}subseteq I^{n}}$ представляет собой дискретный шар радиуса (в метрика Хэмминга ) с центром в точке Пусть имеются объектов, относительные веса которых задаются вектором ${displaystyle mathrm {x} =(x_{1},dots ,x_{n})in I^{n},}$ определяющим конфигурацию весов множества объектов: -й объект имеет стандартный вес, если ${displaystyle x_{i}=0;}$ вес -го объекта больше (меньше) на постоянную (неизвестную) величину, если ${displaystyle x_{i}=1}$ (соответственно, ${displaystyle x_{i}=-1}$ ). Вектор ${displaystyle mathrm {x} ^{+}}$ характеризует типы объектов: стандартный, нестандартный (т. е. конфигурацию типов), и не содержит информации об относительных весах нестандартных объектов.

Взвешивание (проверка) задается вектором ${displaystyle {textbf {h}}in I^{n},}$ при этом результат взвешивания для ситуации ${displaystyle {textbf {x}}in I^{n}}$ равен
Взвешивание, определенное вектором ${displaystyle {textbf {h}}=(h_{1},dots ,h_{n}),}$ имеет следующую интерпретацию: при данной проверке -й объект участвует во взвешивании, если ${displaystyle h_{i}neq 0;}$ он кладется на левую чашку весов, если ${displaystyle h_{i}<0}$ и на правую — если ${displaystyle h_{i}>0.}$ При каждом взвешивании на обеих чашках должно быть одинаковое число объектов, недостающее на какой-либо чашке число объектов пополняется эталонными объектами, число
которых равно
Результат взвешивания описывает
случаи: при — равновесие, при — левая чашка перевешивает, при — правая чашка перевешивает.
Взвешивание, не использующее дополнительных эталонных объектов ( ), называется центрированным.
Неполнота исходной информации относительно распределения весов
рассматриваемой группы объектов характеризуется множеством
допустимых распределений весов объектов ${displaystyle Zsubseteq I^{n},}$
которое также называется множеством допустимых ситуаций,
элементы называются допустимыми ситуациями.

Каждое взвешивание определяет разбиение множества
${displaystyle I^{n}}$ плоскостью на три части ${displaystyle W(s|I^{n},{textbf {h}})={{textbf {x}}in I^{n}|s({textbf {x}},{textbf {h}})=s},sin I,}$ и соответствующее разбиение множества где ${displaystyle W(s|Z,{textbf {h}})=W(s|I^{n},{textbf {h}})cap Z.}$ С учетом этого будем говорить, что взвешивание классифицирует элементы по
типам, соответствующим подмножествам при
этом величина ${displaystyle d(Z,{textbf {h}})=max _{sin I}|W(s|Z,{textbf {h}})|}$ называется
диаметром классификации
множества взвешиванием

Определение 1. Алгоритм взвешивания длины — это последовательность ${displaystyle {mathcal {A}}=langle mathrm {A} _{1},dots ,mathrm {A} _{m}rangle }$ , где ${displaystyle mathrm {A} _{j}:I^{j-1}to I^{n}}$ — функция, определяющая
проверку ${displaystyle {textbf {h}}^{j}=mathrm {A} _{j}({textbf {s}}^{j-1}),}$ ${displaystyle {textbf {h}}^{j}in I^{n},}$ на каждом -м шаге алгоритма по результатам взвешиваний на предыдущих шагах ${displaystyle {textbf {s}}^{j-1}=(s_{1},dots ,s_{j-1})in I^{j-1}}$ ${displaystyle ({textbf {h}}^{1}=mathrm {A} _{1}()}$ — заданная исходная проверка).

Пусть — множество всех
-синдромов,
${displaystyle W({textbf {s}}|{mathcal {A}})subseteq I^{n}}$ — множество
ситуаций, имеющих одинаковый синдром т. е.
${displaystyle W({textbf {s}}|{mathcal {A}})={{textbf {z}}in I^{n}|{textbf {s}}({textbf {z}}|{mathcal {A}})={textbf {s}}};}$

Определение 2. АВ называется

a) идентифицирующим ситуации в множестве , если для
всех выполняется условие

b) идентифицирующим типы объектов в множестве , если
для всех выполняется
условие ${displaystyle |W^{+}({textbf {s}}|Z,{mathcal {A}})|=1.}$

В ^[4] доказано, что для установленного класса множеств (называемых подходящими) алгоритм, идентифицирующий типы объектов, идентифицирует также ситуации в .

В качестве примера построены динамические (двухкаскадные) алгоритмы взвешивания с параметрами = 11, = 5, = 2, которые соответствуют параметрам совершенного код Голея (Virtakallio-Golay code).

Каждый из построенных алгоритмов за 5 взвешиваний находит из 11 тестируемых монет до двух фальшивых, веса которых могут быть больше или меньше веса настоящей монеты на фиксированную величину. В этом случае область неопределенности содержит ${displaystyle 1+2C_{11}^{1}+2^{2}C_{11}^{2}=3^{5}}$ ситуаций, т. е. построенный АВ лежит на верхней граница Хэмминга и в этом смысле является совершенным (см. троичный код Голея). В то же время установлено, что статического АВ (кода взвешивания) с параметрами = 11, = 5, = 2 не существует.

К настоящему времени неизвестно, существуют ли другие совершенные АВ, идентифицирующие ситуации в ${displaystyle I_{t}^{n}}$ при каких-либо значениях . Более того, не известно, существуют ли при некотором решения уравнения ${displaystyle sum _{i=0}^{t}2^{i}C_{n}^{i}=3^{m},}$ соответствующего граница Хэмминга для троичных кодов, что, очевидно, является необходимым для существования совершенного АВ. Известно лишь, что при совершенных АВ не существует, а при указанное уравнение имеет единственное нетривиальное решение, определяющее параметры построенного совершенного АВ.

«Нестандартные» задачи на взвешивание[править | править код]

Иногда встречаются «нестандартные» задачи на взвешивание, например:

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

К. Кноп придумал такую задачу. Мы имеем n монет, одна из которых фальшивая (не известно большего или меньшего веса, чем настоящие монеты, которые имеют одинаковый вес). Имеется 2 рычажных весов, которые могут использоваться параллельно. Каждое взвешивание занимает минуту времени. Каково максимальное число монет n, среди которых можно найти фальшивую монету за 5 минут?^[5]

Примечания[править | править код]

↑ Яглом А. М., Яглом И. М. Вероятность и информация. М.: Наука, Москва, 1973
↑ Шестопал Г. Как обнаружить фальшивую монету. Квант, 1979, №10. С. 21-25.
↑ Канель-Белов, A.Я.; Френкин, Б. Р. Дополнение к статье Д. А. Михалина, И. М. Никонова «Одна задача о нахождении фальшивой
монеты» // Математическое просвещение : журнал. — 2007. — Т. 11. — С. 149—158.
↑ ¹ ² Чуднов А. М. “Алгоритмы классификации и идентификации ситуаций на основе взвешивания”, Дискрет. матем., 26:4 (2014), 119–134, DOI: https://doi.org/10.4213/dm1310 (рус.); Discrete Math. Appl., 25:2 (2015), 69–81. https://doi.org/10.1515/dma-2015-0007 (eng).
↑ http://arxiv.org/pdf/1310.7268.pdf Архивная копия от 16 августа 2017 на Wayback Machine Solution to the Counterfeit Coin Problem and its Generalization

Источник

Приветствую читателей и подписчиков канала!

Рассмотрим одну из задач , которые задают на собеседованиях. Задач про взвешивание.

Задача.

Дано 12 монет, из которых 11 – настоящие, и только 1 – фальшивая. Фальшивая монета отличается от настоящих по массе. Какое минимальное количество взвешиваний необходимо, чтобы обнаружить фальшивую монету? Для взвешивания используются чашечные весы.

Т_М

Так какое минимальное количество взвешиваний на чашечных весах нужно для выявления одной фальшивой монеты из 12?

Одно, два, три, больше? Ответить на вопрос можно, разработав алгоритм определения этой монеты. Причём, в условии не сказано, вес фальшивой монеты больше или меньше остальных. Чашечные весы не имеют гирек, определяют вес по методу сравнения.

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

Спасибо за просмотр статьи и решение задачи. Ответ пишите в комментариях. Ответ в форме теста. Пишите ответы в комментариях, и проверяйте в форме теста.

Форма теста.

Источник

Взвешивания

ЗАДАЧА

Из набора гирек с массами 1, 2, …, 101 г
потерялась гирька массой 19 г. Можно ли оставшиеся 100 гирек разложить на две
кучки по 50 гирек в каждой так, чтобы массы обеих кучек были одинаковы?

РЕШЕНИЕ

Положим в первую кучку две гирьки массой
101 г и 1 г, а во вторую — 100 г и 2 г; затем в первую две гирьки — 99 г и 3 г,
а во вторую — 98 г и 4 г. Так будем действовать, пока не положим во вторую
кучку гирьки в 84 г и 18 г. К этому моменту в каждой кучке будет лежать по 18
гирек. Теперь положим в первую кучку две гирьки массой 83 г и 20 г, а во вторую
— 82 г и 21 г. Так будем продолжать до тех пор, пока во вторую кучку не
придется положить последнюю пару гирек массой 52 г и 51 г.

Ответ. Да.

ЗАДАЧА

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

РЕШЕНИЕ

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

ЗАДАЧА

В корзине лежит 13 яблок. Имеются весы, с
помощью которых можно узнать суммарный вес любых двух яблок. Как за 8
взвешиваний выяснить суммарный вес всех яблок?

РЕШЕНИЕ

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

ЗАДАЧА

Одна из девяти монет фальшивая, она весит
легче настоящей. Как определить фальшивую монету за 2 взвешивания?

РЕШЕНИЕ

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

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

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

Сахарный песок

У
завхоза есть 32 килограмма сахарного песку и чашечные весы без гирь. За какое
наименьшее количество взвешиваний он сможет отмерить 12 кг? Песок можно сыпать
прямо на чаши — они чистые.

Подсказка 1 из 2

За одно взвешивание мы можем разделить
весь песок пополам, уравновесив чаши.

Решение
задачи

За
одно или два взвешивания отвесить 12 кг не получится. Трех взвешиваний хватит.

За
одно взвешивание мы можем разделить песок пополам — разложив его на чаши так,
чтобы весы пришли в равновесие.

Песок
с одной из чаш (16 кг) убираем в пакет, вторую чашу точно так же делим пополам,
раскладывая песок на чаши весов, чтобы они пришли в равновесие. Итого, на
каждой чаше весов по 8 кг сахара.

Песок
с одной из чаш убираем в другой пакет (не к 16 кг). Остаток опять же делим
пополам, уравновешивая чаши весов. Теперь на каждой чаше по 4 кг. Песок с одной
из чаш добавляем в тот пакет, где лежат 8 кг. Теперь в этом пакете 12 кг.

Гири

Есть
чашечные весы и гири весом 1 г, 2 г, 4 г, 8 г, 16 г.

Какие грузы удастся уравновесить на весах
с помощью этих гирь?

32
грамма

31
грамм

3
грамма

10
грамм

11
грамм

26
грамм

19
грамм

50
грамм

Решение
задачи

Если на одну чашу весов поставить все
гири, то, чтобы весы пришли в равновесие, на другую чашу нужно положить груз
весом 1+2+4+8+16=31 грамм. Поэтому груз весом больше 31 грамма
взвесить не получится.

Любой вес от 1 грамма до 31 грамма
взвесить можно. Покажем, как это сделать для грузов из списка:

3 = 1 + 2

10 = 2 + 8

11 = 1 + 2 + 8

26 = 16 + 8 + 2

19 = 16 + 2 + 1

Взвешиваем и другие фрукты

Яблоко
и апельсин вместе весят столько же, сколько груша и персик. Яблоко вместе
с грушей весят меньше, чем апельсин с персиком, а груша вместе с
апельсином весят меньше, чем яблоко с персиком. Какой из
фруктов самый тяжелый?

Выберите
самый тяжелый фрукт

·
Апельсин

·
Яблоко

·
Груша

·
Персик

Решение
задачи

Напишем данные нам в условии взвешивании
в виде равенств и неравенств:

яблоко+апельсин=груша+персик

яблоко+груша<апельсин+персик

груша+апельсин<яблоко+персик.

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

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

8 монет

У
ювелира есть 8 серебряных монет, одна из которых фальшивая — немного легче
настоящей. За какое наименьшее количество взвешиваний на чашечных весах без
гирь он сможет наверняка найти фальшивую монету?

Решение
задачи

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

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

Двухчашечные весы со
стрелкой

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

Среди
21 внешне неотличимая монета: 10 настоящих и 11 фальшивых (фальшивая на 1 грамм
легче настоящей). Антон взял одну из монет.

За
какое наименьшее количество взвешиваний на двухчашечных весах со стрелкой он
сможет узнать, фальшива ли она?

Решение
задачи

За
1. Положим на каждую чашу по 10 из оставшихся монет. Если разность весов будет
четна, то монета в руках Антона — фальшивая, если нечетна — то настоящая.

Источник

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

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

N >= log3A,

A = 2 * B + C,

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

A = 3 * B + C,

N >= log3B + 2,

log3B = log3A — 1,

N >= log3A + 1

Итог:

N >= log3A

N >= log3A + 1

Анализ с точки зрения теории информации[править | править код]

Задача отыскания одной фальшивой монеты, вес которой может быть больше или меньше веса правильной монеты[править | править код]

Обобщения[править | править код]

«Нестандартные» задачи на взвешивание[править | править код]

Примечания[править | править код]

Вам также может понравиться

Как составить тех задание на проведение работ

Дыхание ртом как исправить

Как найти сулакский каньон

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

N >= log₃A,

N >= log₃B + 2,

log3B = log₃A — 1,

N >= log₃A + 1

N >= log₃A

N >= log₃A + 1