- актуалізація
- Завдання на зважування
- Завдання на переливання
- висновок
- література
Математичні завдання на переливання і зважування відомі з давніх-давен. Зараз їх можна зустріти в олімпіадних задачах або в комп'ютерних іграх - головоломках. Класична задача про фальшиві монетах (ФМ) останнім часом знайшла застосування в теорії кодування та інформації - для виявлення помилки в коді. Мета нашої роботи - знайти і описати алгоритми вирішення таких завдань. Завдання на переливання і зважування відносяться до типу завдань комбинаторного пошуку; їх рішення зводиться до роботи з інформацією.
В ході дослідження виявилося, що різних сюжетів даних завдань дуже багато. Тому ми розглянули найбільш поширені сюжети для кожного виду.
Завдання на зважування.
Завдання на зважування це тип завдань, в яких потрібно встановити той чи інший факт (виділити фальшиву монету серед справжніх, впорядкувати набір вантажів по зростанню ваги і т. П.) За допомогою зважування на важільних вагах без циферблата. Найчастіше в якості зважуваних об'єктів використовуються монети. Рідше є також набір гирьок відомої маси.
Дуже часто використовується постановка завдання, що вимагає визначити або мінімальне число зважувань, потрібне для встановлення певного факту, або привести алгоритм визначення цього факту за певну кількість зважувань. Рідше зустрічається постановка, що вимагає відповісти на питання, чи можливо встановлення певного факту за кілька зважувань. Часто така постановка є не дуже вдалою, так як при позитивній відповіді на питання завдання найчастіше зводиться до побудови алгоритму, а негативний майже не зустрічається.
Пошук рішення здійснюється шляхом операцій порівняння, причому, не тільки одиночних елементів, але і груп елементів між собою. Завдання даного типу найчастіше вирішуються шляхом міркувань.
Вивчивши літературу з даної теми, ми прийшли до висновку про те, що всі завдання на зважування можна розділити на наступні типи:
Завдання на порівняння за допомогою ваг.
Завдання на зважування на вагах з гирями.
Завдання на зважування на вагах без гир.
Завдання 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 зважуваннях ваги були в рівновазі, то ФМ серед решти однієї або двох. Якщо залишилася 1 монета, то вона ФМ і зважуючи її зі справжньою, дізнаємося, легше чи важче вона, ніж справжня монета. Якщо залишилося 2, то зважуючи їх між собою, а потім одну з них до цієї, відповідаємо на питання завдання. Якщо в першому чи в другому випадках ваги не були в рівновазі, то можна визначити групу монет, що містять ФМ, а також зробити висновок про те, легше чи важче вона, ніж справжня монета.
- Якщо монет 2, то задача 2 не має рішення.
- Якщо монет 3, то для знаходження серед них фальшивої монети потрібно 2 зважування.
- Якщо монет від 4 до 9 включно, то найменше число зважувань для знаходження фальшивої монети дорівнює 3.
- Якщо монет від 10 до 27 включно, то воно дорівнює 4.
- Якщо монет від 28 до 81 включно (в зв'язку з тим, що 81 = 3 * 27), то найменше число зважувань дорівнює 5.
Підіб'ємо підсумок завданням.
- Нехай число монет k задовольняє нерівності
і серед них є одна фальшива, про яку відомо, легше вона чи важче, ніж справжні. Тоді найменше число зважувань на чашкових вагах без гир, необхідних для знаходження фальшивої монети, так само n. - Нехай число монет k задовольняє нерівності
і серед них є одна фальшива, про яку невідомо, легше вона чи важче, ніж справжні. Тоді найменше число зважувань на чашкових вагах без гир, необхідних для знаходження фальшивої монети, так само n.
Гіпотеза підтвердилася. Ми описали алгоритми для визначення ФМ за найменшу кількість зважувань в разі, якщо відомо, що ФМ важче або легше ніж справжня (алгоритм 1) і в разі, якщо це невідомо (алгоритм 2).
Завдання на переливання.
Опис: маючи кілька судин різного об'єму, один з яких наповнений рідиною, потрібно розділити її в будь-якому відношенні або відлити яку-небудь її частину за допомогою інших судин за найменше число переливань.
У завданнях на переливання потрібно вказати послідовність дій, при якій здійснюється необхідне переливання і виконані всі умови задачі. Якщо не сказано нічого іншого, вважається, що
- всі судини без поділів,
- не можна переливати рідини "на око"
- неможливо нізвідки додавати рідини і нікуди зливати.
Ми можемо точно сказати, скільки рідини в посудині, тільки в наступних випадках:
- знаємо, що посудина порожній,
- знаємо, що посудина повний, а в задачі дана його місткість,
- в задачі дано, скільки рідини в посудині, а переливання з використанням цього судини не проводилися,
- в переливанні брали участь дві посудини, в кожному з яких відомо, скільки було рідини, і після переливання вся рідина помістилася в один з них,
- в переливанні брали участь дві посудини, в кожному з яких відомо, скільки було рідини, відома місткість того судини, в який переливали, і відомо, що вся рідина в нього не помістилася: ми можемо знайти, скільки її залишилося в іншій посудині.
Найчастіше використовуються словесний спосіб вирішення (тобто опис послідовності дій) і спосіб вирішення за допомогою таблиць, де в першому стовпці (або рядку) вказуються обсяги даних судин, а в кожному наступному - результат чергового переливання. Таким чином, кількість стовпців (крім першого) показує кількість необхідних переливань. Ці ж способи (словесний і табличний) використовувалися і при вирішенні задач на зважування. Однак ми виявили ще один цікавий спосіб, яким можна вирішувати такі завдання. Це метод математичного більярду. Я І. Перельман у своїй книзі «Цікава геометрія» запропонував вирішувати завдання на переливання з допомогою «розумного» кульки. Для кожного випадку пропонувалося будувати більярдний стіл особливої конструкції з рівносторонніх трикутників, довжини двох сторін якого чисельно дорівнюють обсягу двох менших сусідів. Далі, з гострого кута цього столу уздовж однієї зі сторін потрібно «запустити» кульку, який за законом «кут падіння дорівнює куту відбиття» буде стикатися з бортами столу, показуючи тим самим послідовність переливань. На бортах столу нанесена шкала, ціна ділення якої відповідає обраному об'єкті обсягу. В результаті руху кулька або вдаряється об бортик в потрібній точці (тоді завдання має рішення), або не вдаряється (тоді вважається, що завдання рішення не має). Більярдна куля може переміщатися тільки уздовж прямих, що утворюють сітку на параллелограмме. Після удару об боку паралелограма куля відбивається і продовжує рух уздовж виходить з точки борту, де сталося зіткнення, повністю характеризує, скільки води знаходиться в кожному з судин.
Старовинна цікава задача.
Виходить 7 переливань. Однак, якщо налити спочатку в посудину в 5 пінт, то буде потрібно 18 переливань.
Чи завжди завдання цього типу мають рішення?
Метод більярдної кулі можна застосувати до задачі про переливанні рідини за допомогою не більше ніж трьох судин. Якщо обсяги двох менших сусідів не мають спільного дільника (т. Е. Взаємно прості), а обсяг третього судини більше або дорівнює сумі обсягів двох менших, то за допомогою цих трьох судин можна відміряти будь-яке ціле число літрів, починаючи з 1 літра і закінчуючи обсягом середнього судини. Маючи, наприклад, судини місткістю 15, 16 і 31 літр, можна відміряти будь-яку кількість води від 1 до 16 літрів. Така процедура неможлива, якщо обсяги двох менших сусідів мають спільний дільник. [10] Коли обсяг більшого судини менше суми обсягів двох інших, виникають нові обмеження. Якщо, наприклад, обсяги судин рівні 7, 9 і 12 літрів, то у ромбического столу треба відсікти нижній правий кут. Тоді куля зможе потрапити в будь-яку точку від 1 до 9, за винятком точки 6. Незважаючи на те, що 7 і 9 взаємно прості, відміряти 6 літрів води виявляється неможливим через те, що найбільший посудину має занадто маленький обсяг. Легко бачити, що точки з цифрою 6 утворюють на діаграмі правильний трикутник, і ми не можемо ніяк потрапити на цей трикутник з будь-якої іншої точки, що лежить поза ним. Відзначимо також, що узагальнення методу математичного більярду на випадок чотирьох судин зводиться до руху кулі в просторової області (параллелепипеде). Але виникають при цьому труднощі зображення траєкторій роблять метод незручним.
Перевага цього витонченого методу математичного більярду полягає, перш за все, в його наочності та привабливості.
Підбивши підсумок, можна сказати, що в ході дослідницької роботи:
1. Зібраний теоретичний і практичний матеріал з проблеми дослідження.
2. За підсумками даної роботи нами були систематизовані завдання на переливання і зважування.
3. Складено алгоритми рішення.
4. Складена презентація, щоб ознайомити однокласників з даними завданнями і допомогти їм у підготовці до олімпіади.
Таким чином, можна зробити висновок про те, що виконана нами робота виявилася плідною, учні ознайомилися зі способами і методами вирішення завдань на зважування і переливання. Навчилися правильно застосовувати оптимальні способи для їх вирішення. За відгуками учнів, проведена робота дозволила їм оволодіти методами вирішення завдань на переливання, розширила їх кругозір. Учні відзначили можливість і практичність застосування більярдного методу при вирішенні даного типу завдань. Продовжуючи надалі дане дослідження, можна ще спробувати знайти формулу для обчислення найменшого кількості зважувань (переливань).
Список використаних джерел
2. Гальперін Г.А. Періодичні руху більярдної кулі / Квант. 1989. № 3.
3. Ф.Ф.Нагібін, Е.С.Канін Математична скринька М. Просвещение, 1988
4. Я. І. Перельман Цікава геометрія М. ГІФМЛ, 1959
11. Байіф Ж-К. Логічні завдання. М. Світ, 1983. 171 с.
12. Балк М.Б. Балк Г.Д. Математика після уроків. М. Просвітництво, 1971.
13. Барабанов А.І. Чернявський І.Я. Завдання і вправи з математики. Саратов: Саратовський ун-т, 1965. 234 с.
14. Барр С. Розсипи головоломок. М. Світ, 1978. 414 с.
15. Беррондо М. Цікаві завдання. М. Світ, 1983. 229 с.
16. Болл У. Коксетер Г. Математичні есе і розваги. М. Світ, 1986. 472 с.
17. Перельман Я. І. Цікава арифметика.
18. Перельман Я. І. Цікава алгебра.
19. Перельман Я. І. Цікава геометрія.
20. Перельман Я. І. Жива математика.
Підписи до слайдів:
Рішення задач на зважування і переливання