Решение задач на взвешивание и переливание

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

Скачать:

Предварительный просмотр:

1. Актуализация
2. Задачи на взвешивание
3. Задачи на переливание
4. Заключение
5. Литература

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

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

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

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

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

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

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

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

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

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

Задача 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. Взвешиваем первые две группы монет.(выделенные цветом).

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

• Если монет 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 = 3 2 +1, 28 = 3 3 +1.

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

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

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

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

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

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

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

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

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

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

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

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

- нельзя переливать жидкости "на глаз"

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

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

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

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

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

Восьмиведерный бочонок заполнен доверху квасом. Двое должны разделить квас поровну. Но у них есть только два пустых бочонка, в один из которых входит 5 ведер, а в другой – 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 переливаний. Одновременно с этим заполняем таблицу: