Стрибки Вієта • Костянтин Кноп • Науково-популярні завдання на "Елементи" • Математика

Стрибки Вієта

завдання

Натуральні числа a і b такі, що a2 + b2 + 1 ділиться на ab без залишку. Доведіть, Що приватна одно 3.


Підказка 1

Однією з можливих пар чисел, що задовольняють умові, є (1, 1), а ще двома – (1, 2) і (2, 1). Переконайтеся, що для всіх цих пар приватне дорівнює 3.


Підказка 2

Як пари (a, b) Можна брати будь-які два сусідніх числа в послідовності 1, 1, 2, 5, 13, 34, 89, 233, … Спробуйте вгадати, як утворена ця послідовність, і довести цей факт.


Підказка 3

Постарайтеся довести, що інших рішень, крім пар чисел, перерахованих у другій підказці, немає.


Рішення

Спочатку наведемо "рафінована" (в тому ж сенсі, в якому рафінують рослинне масло, тобто очищене від сторонніх домішок) міркування, в якому ніяк не використовуються ті сакральні відомості, які ми згадували в підказках.

Нехай \ (k = \ frac {a ^ 2 + b ^ 2 + 1} % \). Якщо (а чому б і ні?) a = b, То умова полягає в тому, що 2a2 + 1 ділиться на a2. оскільки 2a2 завжди ділиться на a2, То 1 також має ділитися на a2, звідки a = 1. Але при a = b = 1 отримуємо \ (k = \ frac {1 + 1 + 1} % = 3 \), тобто для цього випадку ми все довели.

нехай тепер ab. Без обмеження спільності можна вважати a бпрольшим з двох чисел (тобто a > b).Спробуємо знайти іншу пару натуральних чисел (a ', b '), Яка також буде задовольняти умові завдання, але буде менше вихідної.

Перепишемо рівняння, що зв'язує a, b і k, у вигляді a2kab + b2 + 1 = 0. А щоб було ще краще зрозуміло, що ми збираємося робити, замість a напишемо x. Це – квадратне рівняння (щодо x): \ (X ^ 2-kb \ cdot x + (b ^ 2 + 1) = 0 \). Ми не будемо його вирішувати, але згадаємо, що його коріння x1 і x2 (Якщо вони є!) Задовольняють теоремі Вієта:

\ [X_1 + x_2 = kb, \] \ [x_1 \ cdot x_2 = b ^ 2 + 1. \]

Один з цих коренів ми знаємо: x1 = a. Отже, ми можемо сказати, що є і другий корінь \ (x_2 = kb-a = \ frac {b ^ 2 + 1} % \). Перша умова гарантує, що x2 є цілим, а друге – що він є позитивним. Тобто x2 – це натуральне число.

Таким чином, числа x2 і b теж задовольняють умові завдання, тобто \ (x_2 ^ 2 + b ^ 2 + 1 \) ділиться на x2b, І частка від ділення дорівнює тому самому числу k. При цьому, оскільки ми припустили, що a > b, То \ (x_2 = \ frac {b ^ 2 + 1} % \ le \ frac {b ^ 2 + 1} {b + 1} <b \) при b > 1. Тоді як меншою пари ми можемо взяти пару (b, x2).

Виходить, що якщо b > 1, то теорема Вієта дає нам можливість зробити "стрибок" від рішення (a, b) До меншого рішенням (a ', b ') = (b, kb a).

А що буде, коли стрибки приведуть нас до b = 1 (очевидно адже, це рано чи пізно має статися)?

при b = 1 рівняння матиме вигляд x2kx + 2 = 0. Оскільки воно має натуральний корінь a, А по теоремі Вієта твір коренів одно 2, то другий корінь дорівнює 2 /a. А оскільки він же дорівнює цілому числу ka, то a має бути дільником числа 2. Це дає дві можливості:

1) якщо a = 2, то 4 – 2k + 2 = 0, звідки k = 3.
2) якщо a = 1, то 1 – k + 2 = 0, звідки знову k = 3.

оскільки k залишалося одним і тим же при всіх зроблених "стрибках", то k = 3 для будь-якої пари чисел (a, b). На цьому рішення закінчено.

А тепер спробуємо розібратися, що саме ми робили і як прийшли до потрібного результату. Завдяки підказкам було відомо, що пара чисел (a, b), Яка задовольнить умові завдання, це якась із пар (1, 1), (1, 2), (2, 5), (5, 13), (13, 34), (34, 89) і т. д. Закономірність, яка прямо не впадала в очі, але напевно була помічена при спробах вирішення, виглядає так: якщо між кожними двома числами пари вписати ще їх різницю, то вийдуть числа Фібоначчі 1, 1, 2, 3, 5, 8, 13 , 21, 34, 55, 89, … Для цієї послідовності співвідношення, що зв'язує три її послідовних члена, дуже добре відомо: fn+2 = fn + fn+1. А так як "нашої" послідовністю є числа Фібоначчі з парними номерами, то можна записати рекурентне співвідношення і для неї:

\ [F_ {2n + 2} = f_ % + f_ {2n + 1} = f_ % + (f_ % + f_ {2n-1}) = 2f_ % + (f_ % -f_ {2n-2}) = 3f_ % -f_ {2n-2}. \]

Дійсно, 5 = 3 · 2 – 1, 13 = 3 · 5 – 2, 34 = 3 · 13 – 5 і так далі.

Тут множник 3 – той самий, який ми позначили на початку рішення буквою k. Але ми-то не можемо спиратися на те, що нам потрібно довести, правда? І ось тут на допомогу і приходить теорема Вієта, завдяки якій перехід від одного рішення до сусіднього робиться зовсім просто – "стрибком". При стрибку ми можемо не знати, чому дорівнює значення k, Але гарантовано зрушимо від більшого рішення до меншого, зберігши те ж саме значення k. А значить, рано чи пізно дійдемо до "найменшого" рішення. Подальше вже – справа техніки.


Післямова

У статті англійської Вікіпедії Vieta jumping стверджується, що цей прийом вирішення завдань з'явився тільки в 1988 році в зв'язку із завданням, що пропонувалася від Австралії на Міжнародну олімпіаду школярів. Ось це завдання:

Нехай a і b – натуральні числа, для яких a2 + b2 ділиться на ab + 1. Доведіть, що частка від цього розподілу – точний квадрат.

При цьому переказується кумедна історія, вперше описана в книзі Артура Енгеля "Стратегії вирішення завдань":

"Ніхто з шести членів Австралійського задачного комітету не зміг розв'язати цю проблему.Двома з цих членів були Дьордь Секереш та його дружина, обидва відомі автори і вирішувачі завдань. Оскільки ця задача ставилася до теорії чисел, її послали чотирьом найбільш відомим фахівцям з теорії чисел в Австралії. Їх попросили подумати над завданням не більше шести годин. У відведений час ніхто з них не вклався. Тому задачний комітет запропонував завдання в журі XXIX Міжнародної олімпіади, позначивши її двома зірочками, що означало дуже високу складність, можливо, занадто високу для олімпіади. Після тривалої дискусії, журі погодилося вибрати її в якості останньої, найважчої завдання олімпіади. 11 учасників отримали повні рішення. "

Насправді, безумовно, прийом "стрибка" був відомий задовго до цієї олімпіади. Зокрема, завдання, яке ми обговорювали, є окремим випадком дослідження добре відомого діофантових рівнянь Маркова, вперше дослідженого чудовим російським математиком Андрієм Андрійовичем Марковим ще в XIX столітті.

Рівняння Маркова має вигляд

\ [A ^ 2 + b ^ 2 + c ^ 2 = 3abc. \]

Якщо покласти в ньому c = 1, вийде рівно то рівняння, яким ми займалися. А чи існують у рівняння Маркова рішення, в яких c не дорівнює 1? Безумовно, існують.І у читача вже є все необхідне для того, щоб їх знайти.

Мал. 1. Приклад сімейства кіл Аполлонія. Малюнок з сайту en.wikipedia.org

Ще однією цікавою ілюстрацією ідеї "стрибка Вієта" можуть служити безлічі Аполлонія – сімейства кіл, в якому кожна стосується трьох інших (рис. 1, див .: Apollonian gasket).

Якщо з такого сімейства взяти четвірку кіл, які попарно стосуються, то для їх радіусів справедлива формула, вперше відкрита знаменитим хіміком (!) Фредеріком Содді:

\ [\ Frac1 {r_1 ^ 2} + \ frac1 {r_2 ^ 2} + \ frac1 {r_3 ^ 2} + \ frac1 {r_4 ^ 2} = \ frac12 \ left (\ frac1 {r_1} + \ frac1 {r_2} + \ frac1 {r_3} + \ frac1 {r_4} \ right) ^ 2. \]

Якщо замість радіусів ri кіл розглядати їх кривизни ki (Величини, зворотні радіусів), то з формули йдуть складні дроби:

\ [K_1 ^ 2 + k_2 ^ 2 + k_3 ^ 2 + k_4 ^ 2 = \ frac12 (k_1 + k_2 + k_3 + k_4) ^ 2. \]

Наприклад, для чотирьох найбільших кіл на малюнку 1 кривизни рівні -1, 2, 2 і 3 (знак "мінус" довелося поставити через те, що дотик внутрішнє). А звідси, як може здогадатися проникливий читач, залишилося всього півкроку до твердження про те, що кривизна кожного кола в (нескінченному) безлічі Аполлонія – ціле число, і всі ці числа можуть бути отримані одна з одної за допомогою стрибків Вієта.

Про рівнянні Маркова можна прочитати в чудовій статті М. Г.Крейна "діофантових рівнянь А. А. Маркова", про фрактальних множинах Аполлонія – в дослідженні К. Міллер (англійською). Кілька красивих задач, в рішенні яких використовується прийом стрибка, можна знайти тут і тут.


Like this post? Please share to your friends:
Залишити відповідь

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: