Метод нескінченного спуску
Л. Курляндчик, Г. РозенблюмМетод нескінченного спуску
Яке ірраціональне число найстаріше? Безперечно, √ 2 . Ми не знаємо точно, хто перший довів ірраціональність цього числа, проте ми переконані, що це було зроблено приблизно так.
Оскількиc2 = 2a2, то
Таким чином, трикутникKEC, подібний до трикутникаACD, прямокутний рівнобедрений, і ми можемо виконати на його сторонах таку ж побудову, як на сторонах трикутникаACD. Відкладемо на [EC] відрізокEK1:EK1 =KC; на [KC] відрізокKE1:KE1 =K1C. КрапкиK1 іE1 знову потраплять у точки поділу. ТрикутникK1CE1 знову виявиться прямокутним рівнобедреним. Для нього ми тим самим способом побудуємо трикутникK2CE2; цю процедуру можна продовжувати без кінця. При цьому трикутникиKjCEjстають все дрібнішими, але щоразу точкиKjіEjпотраплятимуть у початкові точки поділу відрізківACіCD. Але ж цихточок тільки кінцеве число! А трикутниківKjCEjнескінченно багато. Це протиріччя доводить ірраціональність √ 2 .
Минуло століття. З'явився доказ алгебри, мабуть, простіший.
Ірраціональність √ 2 означає, що у рівнянняx2 = 2y2 немає рішень у натуральних числахx,y. Припустимо, що такі рішення є, іx=m,y=n- одне з них.
З рівняння випливає, щоm- парне число,m= 2m1. Підставляючиm= 2m1 рівняння, отримуємоn2 = 2m1 2 , тобтоx=n,y=m1 теж рішення. Зазначимо при цьому, що n 2 = 2n1 2 . Таким чином,x=m1,y=n1 рішення рівняння, при цьомуm1n>m1 >n1 > . а нескінченної спадної послідовності натуральних чисел бути не може! Отже, наше припущення було помилковим, і число √ 2 ірраціонально.
Обидві міркування по суті проходили за однією схемою: припустивши, що завдання має рішення, ми будували деякий нескінченний процес, тоді як по самому сенсу завдання цей процес повинен на чомусь закінчуватися. Подібний метод і називається методом нескінченного спуску.
Часто метод спуску застосовується у простішій формі. Припустивши, що ми вже дісталися природного кінця процесу, бачимо, що «зупинитися» не можемо.
Нехайx=m,y=nрішення рівнянняx2 = 2y2 з найменшим можливимx. Числоmмає бути парним,m= 2m1, отже,x=m,y=m1 теж рішення нашого рівняння. Однакm>n, що суперечить вибору рішенняm,nяк «найменшого».
З цього варіанта доказу видно, що метод спуску схожий на метод математичної індукції. Обидва методи засновані на тому факті, що будь-яка непорожня множина натуральних чисел має мінімальний елемент. Метод спуску найбільш зручний для доказу «заперечних» теорем.
Метод спуску в задачах
Завдання 1 .Довести нерозв'язність у натуральних числах рівняння
Рішення . Припустимо, що рішення є іx=m,y=n,z=p,t=rрішення з найменшим можливимx. З рівняння видно, що парне число,r= 2r1.
Підставляючи це рішення в рівняння та ділячи на 2, отримуємо
Тепер ясно, щоp?парне,p= 2p1, отже,
Далі діємо так само:n= 2n1,
Так якx2 +y2 +z2 +t2 ? парне число, то серед чиселx,y,z,t♦ парне число непарних, тобто або чотири, або два, або нуль. Якщо всі числа непарні, тоx2+y2+z2+t2 ділиться на 4, а 2xyzt не ділиться. Якщо ж лише два непарні числа, то 2 +y2 +z2 +t2 не ділиться на 4, a 2xyztділиться. Тому всі числа парні, тобтоx=x1,y=y1,z=z1,t=t1. Підставивши ці значення до рівняння, отримуємо
Як і раніше, бачимо, що всі чотири числа непарними бути не можуть, інакшеx1 2 +y1 2 +z1 2 +t1 2 не ділиться на 8. Також не можуть бути непарними рівно два числа, бо і тодіx1 2 +y1 2 +z1 2 +t1 2 не ділиться на 8. Отже, ми отримуємо, що всі числа парні, тобто
Розмірковуючи, як і раніше, отримуємо, щоx2,y2,z2,t2 - парні числа і так далі. Легко зрозуміти, що при будь-якому натуральномуs
Тобто за будь-якого натуральногоsчисла
Цілі. Ну, а це неможливо за жодних натуральнихx,y,z,t.
А ось рівняння, у якого безліч рішень, але яке досліджується тим же методом.
Завдання 3 .Знайти всі рішення в натуральних числах рівняння
Рішення . Очевидно, щоx1 = 3,y1 = 2 рішення цього рівняння. Доведемо, що якщо пара (x,y) рішення, то пара (3x+ 4y, 2x+ 3y) теж рішення. Це випливає з тотожності
Ми вказали нескінченну послідовність рішень (x1,y1), (x2,y2), . Доведемо тепер, що інших чисел, які відповідають рівнянню, немає.
Нехай (x,y) деяке рішення. У такому випадку (3x4y, 3y2x) також рішення, бо
З умови 9 = 9x2 18y2 > 2y2 слід, що 3x> 4y; а приy> 2 з умови 4 = 4x2 8y2 2 слід, що 3y> 2x. Тобто заy> 2 ми з рішення (x,y) отримуємо рішення (x(1) ,y(1) ) у натуральних числах, причомуx(1) (1) (n) ,y(n) ), деy(n) ≤ 2. Оскількиy(n) , очевидно, не може дорівнювати 1, тоy(n) = 2. Отже,x(n) = 3. І це означає, що числаxіyналежать побудованої раніше послідовності.
Досі ми розглядали лише рівняння. Тепер вирішимо нашим методом «текстове» завдання.
Завдання 4 .Є2N+1гір, кожна з яких важить ціле число грамів.Відомо, що будь-які2Nз них можна так розкласти на чашки ваг, N на кожну, що настане рівновагу. Довести, що всі гирі мають однакову вагу.
Рішення . Ясно, що всі гирі одночасно мають або парну або непарну вагу: вага будь-яких гир четний. Віднімемо тепер з ваг усіх гир вага найлегшої гирі (або найлегших, якщо їх кілька). Нова система гир, очевидно, також задовольняє умову завдання, причому серед гир є «гирі» нульової ваги. Тому ваги всіх гир нової системи парні. Розділивши ваги всіх гир навпіл, ми знову отримуємо систему гир, яка б задовольняла умовам завдання, серед яких є «гирі» нульової ваги. Тому знову ж таки отримуємо, що вага всіх гир четний, і так далі. З «нескінченного спуску» випливає, що всі «гирі» нульові, а це означає, що всі вихідні гирі мають однакову вагу.
Ідея нескінченного спуску дозволяє вирішувати деякі завдання комбінаторної геометрії.
Завдання 5 .Чи можна куб розрізати на кілька різних кубиків?
Рішення . Зробимо спочатку одне очевидне зауваження. Нехай квадратPрозбитий на кінцеве число різних квадратів. Тоді найменший квадрат не прилягає до межі квадратаP.
Допустимо тепер, що кубQвдалося розрізати на різні кубиQj, нехайPодна з гранейQ. КубиQj, прилеглі доP, породжують розбиттяPна попарно різні квадрати. НехайP1 найменший з цих квадратів,Q1 відповідний куб.P1 не прилягає до кордонуP, отже, він оточений великими квадратами. Відповідні куби утворюють «колодязь», у якому лежить кубикQ1.
НехайP'1 «верхня» грань (протилежна граніP1) кубаQ1. Куби,прилеглі доP'1, породжують розбиттяP'1 різні квадрати. Знову найменший з них,P2, розташований всерединіP'1, отже, куби, що оточують відповідний кубикQ2, більшеQ2 і знову утворюють «колодязь». Продовжуючи побудову і далі, ми отримаємо нескінченну «вежу», що складається з кубів, що все зменшуються, а це неможливо.
На завершення завдання на картатому папері.
Завдання 6 .Даний аркуш картатого паперу. Довести, що приn≠ 4не існує правильногоn-кутника з вершинами у вузлах ґрат.
Рішення . Спочатку доведемо, що немає правильного трикутника з вершинами у вузлах. Дійсно, нехай довжина сторони цього трикутника; тодіa2 | ціле число за теоремою Піфагора. Площа трикутника дорівнюєa2 √ 3 /4, тобто ірраціональна. З іншого боку, очевидно, що площа будь-якого багатокутника з вершинами у вузлах є раціональною.
Нехайn≠ 3, 4, 6. Припустимо, щоP1,P2, .Pnn-кутник з вершинами у вузлах. Відкладемо від точокP1,P2, .Pnвектори, відповідно рівні векторамP2P3,P3P4, .P1P2 (див. рис.). Нові точки знову потраплять у вузли ґрат і утворюють правильнийn-кутник усередині початкового. З новимn-кутником можна зробити так само, і так далі, без кінця. Однак квадрат довжини сторониn-кутника є цілим числом, а при наших побудовах воно весь час зменшується!
Довести, що основа та бічна сторона рівнобедреного трикутника з кутом при вершині 36°непорівнянні.