Принцип дирихле

 

 МІНІСТЕРСТВО  ОСВІТИ І НАУКИ УКРАЇНИ

МАЛА АКАДЕМІЯ НАУК УКРАЇНИ

 

ВІННИЦЬКЕ ТЕРИТОРІАЛЬНЕ  ВІДДІЛЕННЯ МАН

 

ТИВРІВСЬКИЙ ЛІЦЕЙ  – ІНТЕРНАТ

ПОГЛИБЛЕНОЇ ПІДГОТОВКИ В ГАЛУЗІ НАУКИ

 

НАУКОВЕ ТОВАРИСТВО «НОВА ДОБА»

 

НАУКОВО – ТЕХНІЧНЕ ВІДДІЛЕННЯ

СЕКЦІЯ ПРИКЛАДНОЇ МАТЕМАТИКИ

 

 

 

Принцип Діріхле.

Узагальнений  принцип 

Діріхле.

Умова збігу.

 

 

 

                                                                          Роботу виконала член ВМАН

                                                                    Горбатюк Інна Леонідівна

                                                        учениця 3-го курсу

                                                                                    фізико – математичного факультету

                                                                             Тиврівського ліцею – інтернату

 

 

                                                                           Науковий керівник: вчитель –

                                                                          методист Тиврівського ліцею

                                                                      Шастун Василь Федорович

 

 

 

 

Вінниця 2012

Зміст

Вступ……………………………………………………………3

Біографія Петера Густава Лежена Діріхле…………..…..………....4

Розділ 1. Принцип Діріхле…………………………………….....5

Розділ 2. Узагальнений принцип Діріхле. Умова збігу…………...16

Розділ 3. Геометричне застосування принципу Діріхле……………24

Розділ 4. Принцип Діріхле для площ. Узагальнений принцип

                  Діріхле для площ……………..…………………………….28

Висновки………………………………………………………………31

Список  використаної літератури………………………….……32

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                          Вступ

Досягнення сучасної науки i техніки неможливе без застосування i подальшого розвитку математики. Сьогодні математичні теорії та методи є визначальними майже в усіх сферах людської діяльності, тому підвищення рівня математичної освіти в Україні - одне з найважливіших завдань як вищої, так i середньої школи. Однак математична освіта в загальноосвітній школі спрямована в основному на засвоєння учнями алгоритмів розв'язування стандартних задач, а цього недостатньо для потреб практики i розвитку здібностей до самостійного математичного мислення.

Розв'язуванню нестандартних математичних задач  учні навчаються на факультативних заняттях, в математичних гуртках та шляхом наполегливої самостійної роботи, а перевіряються їх знання i вміння на математичних олімпіадах різних рівнів.

Тема моєї науково – дослідницької роботи – принцип Діріхле, узагальнений принцип Діріхле. Незважаючи на свою простоту, принцип Діріхле не входить до навчальних програм з математики загальноосвітніх шкіл. Проте традиційно розглядається на заняттях математичного гуртка. Принцип Діріхле є очевидним твердженням. Кожна навіть не обізнана з математикою людина, розуміє, що розсадити ( n + 1 ) – го кролика в n клітинок так, щоб в кожній клітці було не більше від одного кролика не можна. За допомогою цього принципу розв’язуються цікаві змістовні задачі, які зустрічаються на олімпіадах з математики різних рівнів.

Задачі на принцип Діріхле – чудовий матеріал для розвинення хисту учнів до наукових досліджень. У моїй науковій роботі читач знайде приклади переростання задачі на принцип Діріхле в маленьке, доступне учням, наукове дослідження. За допомогою такого очевидного і простого твердження можна дістати глибокі результати про наближення ірраціональних чисел раціональними.

 

 

 

Біографія Петера Густава Лежена Діріхле

Петер Густав Лежен  Дирихле(13.2.1805 - 5.5.1859) - німецький математик. Народився в Дюрені. У 1822-1827 роках був домашнім учителем в Парижі. Входив в гурток молодих учених, які групувалися навкруги Ж. Фур'є. У 1827 році зайняв місце доцента у Бреславі; з 1829 року працював у Берліні. У 1831-1855 роках - професор Берлінського університету, після смерті К. Гауса(1855) - Геттингенського університету. Зробив ряд великих відкриттів в теорії чисел; встановив формули для числа класів бінарних квадратичних форм із заданим визначником і довів теорему про нескінченність кількості простих чисел в арифметичній прогресії з цілих чисел, перший член і різниця якої взаємно прості. До рішення цих завдань застосував аналітичні функції, названі функціями(рядами) Дирихле. Створив загальну теорію алгебри, одиниць в числовому полі алгебри. У області математичного аналізу уперше точно сформулював і досліджував поняття умовної збіжності ряду, дав строгий доказ можливості розкладання в ряд Фур'є кусочно-безперервної і монотонної функцій, що послужило обгрунтуванням для багатьох подальших досліджень. Значні праці Дирихле в механіці і математичній фізиці, зокрема в теорії потенціалу. З ім'ям Дирихле пов'язано завдання, інтеграл(ввів інтеграл з ядром Дирихле), принцип, характер, ряди. Лекції Дирихле мали величезний вплив на видатних математиків пізнішого часу, у тому числі на Г. Римана, Ф. Ейзенштейна, Л. Кронекера, Ю. Дедекинда.

 

 

 

Розділ 1. Принцип Діріхле

Якщо у n клітках розміщено не менше ніж n+1 кроликів, то знайдеться клітка, яка містить принаймні  два кролики.

Це очевидне твердження носить ім’я видатного німецького математика Перта Густава Лежена Діріхле  і називається принципом Діріхле.

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

Принцип Діріхле  є очевидним твердженням. Кожна  навіть не обізнана людина, розуміє, що розсадити n+1 кроликів в n кліток так, щоб  в кожній клітці було не більше від  одного кролика, не можна. Інакше кажучи, якщо в клітках знаходиться n+1 або більше кроликів, то принаймні в одній клітці сидить не менше від двох кроликів.

 Якщо А  – множина кроликів, а В –  множина кліток, в яких треба  розмістити кроликів, то визначивши клітку для одного кролика, дістанемо відображення множини А у множину В (мал.1).

Якщо  кожному елементу а множини  А поставлено у відповідність деякий елемент b множини В, тоді кажуть, що задано відображення множини А у множину В. Елемент b називають образом елемента а.

У термінах теорії множин принцип Діріхле можна сформулювати так.

Нехай  т  п. тоді при будь – якому відображенні множини А у множину В занйдуться два елементи множини А, які мають один і той же образ.

Інакше кажучи, якщо т зайців розміщено в п клітках (т п) , то знайдуться зва зайці, які потраплять в ту саму клітку.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

мал.1

 

 

Задача  № 1.

В урні знаходяться чорні  та білі кульки. Кульки з урни виймають навмання. Яке найменше число кульок необхідно вийняти, щоб бути впевненим у тому, що серед витягнутих кульок є хоча б дві кульки одного кольору?

Розв’язання.

Двох кульок може не вистачити, адже можна витягнути  чорну і білу кульки. Дістанемо  з урни три кульки. За принципом  Діріхле, серед них обов’язково  будуть хоча б дві кульки одного кольору. Зрозуміло, що тут кроликами є кульки, а клітками – кольори: чорний і білий.

 

Задача  № 2.

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

Розв’язання.

Зауважимо, що з  двох букв можна утворити 2· 2= 4 різних пар ініціалів.(Якщо це. Наприклад, букви А і Б, то матимемо: А.А., А.Б., Б.А., Б.Б.). в українському алфавіті 31 буква, що може входити до складу ініціалів. Тому всього можна утворити

31· 31= 961 різних  пар ініціалів. Візьмемо 961 ящик і на кожному з них нанесемо пару ініціалів. Напишемо для кожного учня його ініціали на картці, і кожну картку покладемо у той ящик, на якому написано таку саму пару ініціалів. Оскільки розкладаємо 962 картки в 961 ящик, то, відповідно до принципу Діріхле, принаймні в  одному ящику буде не менше від однієї картки.

 

Задача  № 3.

У турнірі бере участь n шахістів. Кожні два з них повинні зіграти між собою одні партію. Довести, що в будь – який момент змагань є два шахісти, що зіграли однакову кількість  партій.

Розв’язання.

Розглянемо  два випадки: 1) у даний момент є шахіст, який не зіграв ще жодної партії, 2) у даний момент  немає шахіста, який не зіграв жодної партії.

 Пронумеруємо  шахістів і запишемо для кожного  шахіста число партій, які він  зіграв на даний момент. Дістанемо числа a₁, a₂…… a_n. у випадку 1) кожне з чисел дорівнює одному з чисел 0,1,…,n-2 (шахіста, який зіграв усі n-1 партії. Немає, бо відомо, що є шахіст, який не зіграв ще жодної партії). Серед n чисел, які набувають одне з даних n-1 значень, є принаймні два однакових. Таким чином у випадку 1) твердження задачі справедливе.

У випадку 2) кожне  з чисел a₁, a₂…… a_n дорівнює одному з чисел 0,1,…,n-1, і знову за принципом Діріхле випливає справедливість твердження задачі.

 

Задача  № 4.

Учень протягом року розв’язує задачі. Щодня він розв’язує принаймні одну задачу, але щотижня – не більше ніж 12. Довести, що знайдеться кілька послідовних днів, протягом яких учень розв’яже 20 задач.

Розв’язання.

Припустимо, що за перший день учень розв’язав а₁ задач, за перші два дні – а₂ задач, за перші 77 днів (11 тижнів) – а₇₇ задач. Розглянемо числа

 

а₁, а₂,….., а₇₇,

а₁+20, а₂+20,….., а₇₇+20.

Всього цих  чисел 154. Число  а₇₇ не перевищує 12· 11= 132. Отже кожне з написаних чисел не перевищує 152 і тому серед них є принаймні два однакових. Проте всі числа в першому рядку різні, бо щодня учень розв’язував принаймні одну задачу. Тому всі числа другого рядка також різні. Залишається припустити, що деяке число першого рядка дорівнює якомусь числу другого рядка, тобто при деяких k і l таких, що

a_k = a_l+20

і  a_k - a_l = 20, що й треба було довести.

 

Задача № 5.

Якщо пряма т лежить у півплощині трикутника АВС і не проходить через кожну з його вершин, то вона не може перетинати всі три сторони трикутника. Довести це.

Розв’язання.

Позначимо через Р₁ і Р₂ півплощини, на які розбиває площину трикутника пряма т. Півплощини вважатимемо відкритими, тобто не включаємо до них прямої т. три вершини А, В, С трикутника АВС належать двом півплощинам Р₁ і Р₂. Отже, принаймні в одній з півплощин знаходяться дві вершини. Якщо, наприклад, точки А і В лежать в одній півплощині, то вони знаходяться по один бік від прямої т і пряма т не перетинає сторону АВ. Таким чином, у трикутнику АВС знайшлася сторона, яку пряма т не перетинає.

 

Задача № 6.

 Серед будь  – яких n + 1 цілих чисел можна вибрати два таких, різниця яких ділиться на n. довести це.

Розв’язання.

При діленні  будь – якого числа на n в остачі буде одне з чисел: 0,1,2, …., п – 1. Тому, за принципом Діріхле, принаймні два з n + 1 чисел при ділені на п дадуть однакову остачу. Різниця таких двох чисел поділиться без остачі на п.

 

Задача № 7.

В олімпіаді  приймає участь n учасників. Довести, що принаймні два учасники мають однакову кількість знайомих серед інших учасників.

Розв’язання.

Розглянемо  два випадки: 1) кожний учасник знайомий принаймні з одним іншим і 2) є учасник, який ні з ким не знайомий. Кожний з учасників напише на окремій  картці скільки в нього знайомих. У випадку 1) матимемо n карток, на кожній з яких написане одне з чисел 1,2,3,…, n – 1. Оскільки чисел n – 1, а карток n, то за принципом Діріхле,  щонайменше на двох картках будуть однакові числа. У випадку 2) на кожній картці буде написано одне з чисел 0, 1, 2,…., n -2. Знову матимемо n – 1 чисел, написаних на п картках, тому за принципом Діріхле, принаймні на двох з них будуть написані однакові числа.

 

Задача № 8.

Якщо цілі числа а і b взаємно прості, то існує таке натуральне число k, що a^k – 1 ділиться на b. Довести це.

Розв’язання.

Розглянемо числа 1, а, а² ,а³,….., a^b; випишемо їхні остачі від ділення на b. Оскільки чисел b+1, а різних остач від ділення на b є тільки b (а саме, 0, 1, 2,…., b-1), то серед цих чисел трапляється два таких, які при діленні на b дають однакову остачу. Нехай це числа a^m1 і a^m2(m₁< m₂). Тоді різниця a^m2 - a^m1 = a^m1( - 1) ділиться на b. Але число a^m1 взаємно просте з b, бо за умовою а і b взаємно прості. Тому - 1 ділиться на b.

 

Задача  № 9.

У лісі ростуть 800 000 ялинок і на кожній з них не більше 600 000 хвойних голок. Доведіть, що принаймні дві ялинки мають однакове число голок.

Розв’язання.

Маємо 800 000 «зайців» - ялинок і лише 600 001 клітку з номерами від 0 до 600 000 (за кількістю голок, що може мати ялинка). Але зайців аж 800 000 – більше ніж 600 002. Унаслідок принципу Діріхле, знайдуться два кролики, які потрапили до однієї клітки, тобто принаймні дві ялинки мають однакове число голок.

Цю задачу можна  легко узагальнити і провести деяке дослідження.

 

Задача  № 10.

У лісі ростуть  k ялинок і на кожній з них не більше п  хвойних гілок. Для кожного невід’ємного цілого числа n знайдіть найменше натуральне число k 2, для якого принаймні дві ялинки мають однакове число голок (можливо не мають жодної голки).

Розв’язання.

Маємо k «зайців» - ялинок і лише n +1 кліток з номерами від 1 до n (по числу голок, що може мати ялинка). Якщо зайців k n+2, то, внаслідок принципу Діріхле, знайдуться два зайці, які потраплять до однієї клітки, тобто принаймні дві ялинки мають однакове число голок. Очевидно для k = n +1 не обов’язково знайдуться дві ялинки з однаковим числом голок. Тому для кожного невід’ємного цілого числа n  найменше натуральне число k 2, для я якого принаймні дві ялинки мають однакове число голок (можливо, не мають жодної голки) дорівнює n+2.