що таке “рішення задач підбором”, і чи можна їх вирішувати інакше?
- хто такий діофант
- діофантові рівняння – “завдання про монетки”
- алгоритми рішень диофантовых рівнянь
- алгоритм евкліда
- приклад №1 (простий)
- приклад №2 (складний)
- вирішуємо завдання на підбір чисел без підбору
- завдання про курей, кроликів і їх лапи
- задача про продавщицю і здачу
за відгуками сибмам, справжнім каменем спотикання в шкільному курсі математики не лише для учнів, але і для батьків стають діофантові рівняння. Що це таке і як їх правильно вирішувати? розібратися нам допомогли вчитель математики освітнього центру “горностай” аеліта бекешева і кандидат фізико-математичних наук юрій шанько.
Хто такий діофант?
Ще стародавні єгиптяни для зручності міркувань придумали спеціальне слово, що позначало невідоме число, але в той час не було ще знаків дій і знака рівності, тому і записувати рівняння вони не вміли.
Першим, хто придумав, як можна записати рівняння, був чудовий вчений діофант олександрійський. Олександрія була великим культурним, торговим і науковим центром стародавнього світу. Це місто існує і зараз, він знаходиться на середземноморському узбережжі єгипту.
Жив діофант, мабуть, в iii столітті н.е. І був останнім великим математиком античності. До нас дійшли два його твори « “арифметика «(з тринадцяти книг збереглося шість) і» про багатокутних числах” (в уривках). Творчість діофанта справила великий вплив на розвиток алгебри, математичного аналізу і теорії чисел.
Але ж ви знаєте дещо про діофантових рівняннях …
Діофантові рівняння знають всі! це завдання для учнів молодших класів, які вирішуються підбором.
Якщо дати діофантовому рівнянню загальне визначення, то можна сказати, що це алгебраїчне рівняння з додатковою умовою: всі його рішення повинні бути цілими числами (а в загальному випадку і раціональними).
” найчастіше мами ( особливо ті, хто закінчив школу ще при розвиненому соціалізмі) вважають, що основна мета таких завдань – навчити дітей розплачуватися дрібницею за морозиво. І ось, коли вони щиро переконані, що розкладання дрібниці купками залишилося далеко в минулому, їх улюблений семикласник (або восьмикласник) підходить з несподіваним питанням: “мамо, як це вирішувати?”, і пред’являє рівняння з двома змінними. Раніше таких задачок в шкільному курсі не було (всі ми пам’ятаємо, що рівнянь повинно бути стільки ж, скільки і змінних), так що мама не-математик нерідко впадає в ступор. Але ж це та ж сама задача про дрібниця і морозиво, тільки записана в загальному вигляді!
До речі, а навіщо до неї раптом повертаються в сьомому класі? все просто: мета вивчення діофантових рівняння – дати основи теорії цілих чисел, яка далі розвивається як в математиці, так і в інформатиці та програмуванні. Діофантові рівняння часто зустрічаються серед задач частини ” с ” єдиного держіспиту. Труднощі, перш за все в тому, що існує безліч методів вирішення, з яких випускник повинен вибрати один вірний. Проте лінійні діофантові рівняння ax + by = c можуть бути вирішені відносно легко за допомогою спеціальних алгоритмів.
Алгоритми для вирішення діофантових рівнянь
– вивчення діофантових рівняння починається в поглибленому курсі алгебри з 7 класу. У підручнику ю.м. Макаричева, н.г. Міндюка наводяться деякі задачі і рівняння, які вирішують з використанням алгоритму евкліда і методу перебору по залишках , – розповідає аеліта бекешева. – пізніше, в 8-9 класі, коли вже розглядаємо рівняння в цілих числах більш високих порядків , показуємо учням метод розкладання на множники , і подальший аналіз рішення цього рівняння, оціночний метод . Знайомимо з методом виділення повного квадрата . При вивченні властивостей простих чисел знайомимо з малою теоремою ферма, однією з основоположних теорем в теорії рішень рівнянь в цілих числах. На більш високому рівні це знайомство триває в 10-11 класах. В цей же час ми підводимо хлопців до вивчення і застосування теорії «порівнянь по модулю», відпрацьовуємо алгоритми, з якими знайомилися в 7 – 9 класах. Дуже добре це матеріал прописаний в підручнику а.г. Мордковича «алгебра і початку аналізу, 10 клас» і г. В. Дорофєєва «математика» за 10 клас.
Алгоритм евкліда
Сам метод евкліда відноситься до іншої математичної задачі – знаходження найбільшого спільного дільника: замість вихідної пари чисел записують нову пару – менше число і різниця між меншим і більшим числом вихідної пари. Ця дія продовжують до тих пір, поки числа в парі не зрівняються – це і буде найбільший спільний дільник. Різновид алгоритму використовується і при вирішенні діофантових рівнянь – зараз ми разом з юрієм шанько покажемо на прикладі, як вирішувати завдання “про монетки”.
– розглядаємо лінійне діофантове рівняння ax + by = c, де a, b, c, x і y — цілі числа. Як бачите, одне рівняння містить дві змінних. Але, як ви пам’ятаєте, нам потрібні тільки цілі коріння, що спрощує справу – пари чисел, при яких рівняння вірно, можна знайти.
Втім, діофантові рівняння не завжди мають рішення. Приклад: 4x + 14y = 5. Рішень немає, тому що в лівій частині рівняння при будь — яких цілих x і y буде виходити парне число, а 5-число непарне. Цей приклад можна узагальнити. Якщо в рівнянні ax + by = c коефіцієнти a і b діляться на якесь ціле d, а число c на це d не ділиться, то рівняння не має розв’язків. З іншого боку, якщо всі коефіцієнти (a, b і c) діляться на d, то на це d можна поділити все рівняння.
Наприклад, в рівнянні 4x + 14y = 8 всі коефіцієнти діляться на 2. Ділимо рівняння на це число і отримуємо: 2 ∙ + 7 ∙ = 4. Цей прийом (ділення рівняння на якесь число) дозволяє іноді спростити обчислення.
Зайдемо тепер з іншого боку. Припустимо, що один з коефіцієнтів у лівій частині рівняння (a або b) дорівнює 1. Тоді наше рівняння вже фактично вирішено. Дійсно, нехай, наприклад, a = 1, тоді ми можемо в якості y взяти будь − яке ціле число, при цьому x = c-by. Якщо навчитися зводити вихідне рівняння до рівняння, в якому один з коефіцієнтів дорівнює 1, то ми навчимося вирішувати будь-яке лінійне діофантове рівняння!
Я покажу це на прикладі рівняння 2x + 7y = 4.
Його можна переписати в наступному вигляді: 2(x + 3y) + y = 4.
Введемо нову невідому z = x + 3y, тоді рівняння запишеться так: 2z + y = 4.
Ми отримали рівняння з коефіцієнтом один! тоді z-будь-яке число, y = 4-2z.
Залишилося знайти x: x = z − 3y = z − 3(4 − 2z) = 7z − 12.
Нехай z=1. Тоді y=2, x=-5. 2*(-5)+7*2=4
Нехай z=5. Тоді y=-6, x=23. 2*(23)+7*(-6)=4
” у цьому прикладі важливо зрозуміти, як ми перейшли від рівняння з коефіцієнтами 2 і 7 до рівняння з коефіцієнтами 2 і 1. В даному випадку (і завжди!) новий коефіцієнт (в даному випадку-одиниця) це залишок від ділення вихідних коефіцієнтів один на одного (7 на 2).
У цьому прикладі нам пощастило, ми відразу після першої заміни отримали рівняння з коефіцієнтом 1. Таке буває не завжди, але і ми можемо повторювати попередній трюк, вводячи нові невідомі і виписуючи нові рівняння. Рано чи пізно після таких замін вийде рівняння з коефіцієнтом 1.
Давайте попрообуем вирішити більш складне рівняння, пропонує аеліта бекешева.
Розглянемо рівняння 13x – 36y = 2.
крок №1
36/13=2 (10 у залишку). Таким чином, вихідне рівняння можна переписати наступним чином: 13x-13 * 2y-10y=2. Перетворимо його: 13 (x-2y)-10y=2. Введемо нову змінну z=x-2y.тепер ми отримали рівняння: 13z-10y=2.
крок №2
13/10=1 (3 у залишку). Вихідне рівняння 13z-10y=2 можна переписати наступним чином: 10z-10y+3z=2. Перетворимо його: 10 (z-y)+3z=2. Введемо нову змінну m=z-y. Тепер ми отримали рівняння: 10m + 3z=2.
крок №3
10/3=3 (1 у залишку). Вихідне рівняння 10m+3z=2 можна переписати наступним чином: 3*3m+3z + 1m=2. Перетворимо його: 3 (3m+z) + 1m=2. Введемо нову змінну n=3m+z. Тепер ми отримали рівняння: 3n + 1m=2.
Ура! ми отримали рівняння з коефіцієнтом одиниця!
M=2-3n, причому n може бути будь-яким числом. Однак нам потрібно знайти x і y. Проведемо заміну змінних в зворотному порядку. Пам’ятайте, ми повинні висловити x і y через n, яке може бути будь-яким числом.
Y=z-m; z=n-3m, m=2-3n ⇒ z=n-3*(2-3n), y=n-3*(2-3n)-(2-3n)=13n-8; y=13n-8
X=2y + z ⇒ x=2(13n-8)+(n-3*(2-3n))=36n-22; x=36n-22
Нехай n=1. Тоді y=5, x=14. 13*(14)-36*5=2
Нехай n=5. Тоді y=57, x=158. 13*(158)-36*(57)=2
так, розібратися не дуже просто, зате тепер ви завжди зможете вирішити в загальному вигляді завдання, які вирішуються підбором!
Вирішуємо задачі на підбір чисел
Приклади задач для учнів молодших класів, які вирішуються підбором: позмагайтеся з дитиною, хто вирішить їх швидше: ви, використовуючи алгоритм евкліда, або школяр-підбором?
Завдання про лапи
умови
У клітці сидять кури і кролики. Всього у них 20 лап. Скільки там може бути курей, а скільки-кроликів?
рішення
Нехай у нас буде x курей і y кроликів. Складемо рівняння: 2х + 4y=20. Скоротимо обидві частини рівняння на два: x+2y=10. Отже, x=10-2y, де x і y – це цілі позитивні числа.
відповідь
Число кроликів і курок: (1; 8), (2; 6), (3; 4), (4; 2), (5; 0)
Погодьтеся, вийшло швидше, ніж перебирати ” нехай в клітці сидить один кролик…”
Завдання про монетки
умови
У однієї продавщиці були тільки п’яти – і двухрублевие монетки. Скількома способами вона може набрати 57 рублів здачі?
рішення
Нехай у нас буде x двухрублевих і y п’ятирублевих монеток. Складемо рівняння: 2х + 5y=57. Перетворимо рівняння: 2 (x+2y)+y=57. Нехай z=x + 2y.тоді 2z+y=57. Отже, y=57-2z , x=z-2y=z-2(57-2z) ⇒ x=5z-114 . Зверніть увагу, змінна z не може бути менше 23 (інакше x, число двухрублевих монеток, буде негативним) і більше 28 (інакше y, число п’ятирублевих монеток, буде негативним). Всі значення від 23 до 28 нам підходять.
