Принцип дирихле
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
МАЛА АКАДЕМІЯ НАУК УКРАЇНИ
ВІННИЦЬКЕ ТЕРИТОРІАЛЬНЕ ВІДДІЛЕННЯ МАН
ТИВРІВСЬКИЙ ЛІЦЕЙ – ІНТЕРНАТ
ПОГЛИБЛЕНОЇ ПІДГОТОВКИ В ГАЛУЗІ НАУКИ
НАУКОВЕ ТОВАРИСТВО «НОВА ДОБА»
НАУКОВО – ТЕХНІЧНЕ ВІДДІЛЕННЯ
СЕКЦІЯ ПРИКЛАДНОЇ МАТЕМАТИКИ
Принцип Діріхле.
Узагальнений принцип
Діріхле.
Умова збігу.
Вінниця 2012
Зміст
Вступ……………………………………………………………3
Біографія Петера Густава Лежена Діріхле…………..…..………....4
Розділ 1. Принцип Діріхле…………………………………….....5
Розділ 2. Узагальнений принцип Діріхле. Умова збігу…………...16
Розділ 3. Геометричне застосування принципу Діріхле……………24
Розділ 4. Принцип Діріхле для площ. Узагальнений принцип
Діріхле для площ……………..…………………………….28
Висновки…………………………………………………………
Список використаної літератури………………………….……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) у даний момент немає шахіста, який не зіграв жодної партії.
Пронумеруємо
шахістів і запишемо для
У випадку 2) кожне з чисел a1, a2…… an дорівнює одному з чисел 0,1,…,n-1, і знову за принципом Діріхле випливає справедливість твердження задачі.
Задача № 4.
Учень протягом року розв’язує задачі. Щодня він розв’язує принаймні одну задачу, але щотижня – не більше ніж 12. Довести, що знайдеться кілька послідовних днів, протягом яких учень розв’яже 20 задач.
Розв’язання.
Припустимо, що за перший день учень розв’язав а1 задач, за перші два дні – а2 задач, за перші 77 днів (11 тижнів) – а77 задач. Розглянемо числа
а1, а2,….., а77,
а1+20, а2+20,….., а77+20.
Всього цих чисел 154. Число а77 не перевищує 12· 11= 132. Отже кожне з написаних чисел не перевищує 152 і тому серед них є принаймні два однакових. Проте всі числа в першому рядку різні, бо щодня учень розв’язував принаймні одну задачу. Тому всі числа другого рядка також різні. Залишається припустити, що деяке число першого рядка дорівнює якомусь числу другого рядка, тобто при деяких k і l таких, що
ak = al+20
і ak - al = 20, що й треба було довести.
Задача № 5.
Якщо пряма т лежить у півплощині трикутника АВС і не проходить через кожну з його вершин, то вона не може перетинати всі три сторони трикутника. Довести це.
Розв’язання.
Позначимо через Р1 і Р2 півплощини, на які розбиває площину трикутника пряма т. Півплощини вважатимемо відкритими, тобто не включаємо до них прямої т. три вершини А, В, С трикутника АВС належать двом півплощинам Р1 і Р2. Отже, принаймні в одній з півплощин знаходяться дві вершини. Якщо, наприклад, точки А і В лежать в одній півплощині, то вони знаходяться по один бік від прямої т і пряма т не перетинає сторону АВ. Таким чином, у трикутнику АВС знайшлася сторона, яку пряма т не перетинає.
Задача № 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, що ak – 1 ділиться на b. Довести це.
Розв’язання.
Розглянемо числа 1, а, а2 ,а3,….., ab; випишемо їхні остачі від ділення на b. Оскільки чисел b+1, а різних остач від ділення на b є тільки b (а саме, 0, 1, 2,…., b-1), то серед цих чисел трапляється два таких, які при діленні на b дають однакову остачу. Нехай це числа am1 і am2(m1< m2). Тоді різниця am2 - am1 = am1( - 1) ділиться на b. Але число am1 взаємно просте з 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.
Задача № 11.
У клітинках
квадратної таблиці 3х3 стоять
числа -1, 0, 1. Розглянемо вісім
сум: суми трьох чисел у
Розв’язання.
Суми можуть набувати не більше семи значень : усі цілі число від -3 до 3 включно. Всього сум вісім. Тому за принципом Діріхле принаймні дві суми набувають однакових значень. Отже різними ці суми бути не можуть.
Задача № 12.
Серед будь – яких n+1 цілих чисел можна вибрати два числа, різниця яких ділиться на n.
Розв’язання.
Поділимо кожне з даних чисел на n. При цьому можуть бути остачі 0, 1, 2,….,
n-1. Оскільки чисел n+1, то за принципом Діріхле, принаймні два з них при ділені на n дають однакову остачу. Зрозуміло, що різниця цих чисел ділиться на n.
Задача № 13.
Довести, що серед n натуральних чисел, записаних у певному порядку, можна вибрати кілька сусідніх чисел, сума яких ділиться на n.
Розв’язання.
Нехай a1, a2…… an – задані числа. Розглянемо n чисел a1, a1 + a2, … , a1 + a2 +…+ an. Якщо одне з цих чисел ділиться на n, то твердження задачі правильне. Припустимо, що жодне з цих чисел не ділиться на n. Тоді при діленні на n ці числа дають одну з n-1 остач : 1,2,…, n-1. Всіх чисел n, і кожне з цих чисел при діленні на n дає одну з n-1 остач. Отже, за принципом Діріхле, принаймні два числа при діленні на n дають однакову остачу. Різниця цих двох чисел буде кратна n. Проте будь – яка різниця є сумою кількох сусідніх чисел. Таким чином, твердження задачі є правильним.
Задача № 14.
Довести, що для кожного натурального n є число, яке записується тільки за допомогою цифр 1 і 0 і ділиться націло на n.
Розв’язання.
Розглянемо n+1 число : 1, 11, 111, …, 11…1(останнє число записується n+1 одиницею ). Якщо одне з цих чисел ділиться на n, то твердження задачі є справедливим. Якщо це не так, то, за принципом Діріхле, серед цих чисел є принаймні два, які при діленні на n дають однакову остачу. Це означає, що їх різниця буде кратна n. Залишається лише зауважити, що різниця будь – яких двох розглядуваних чисел записується за допомогою цифр 1 і 0.
Задача № 15.
Довести, що серед будь – яких n+1 різних натуральних чисел, менших за 2n, можна знайти три числа, сума двох з яких дорівнює третьому.
Розв’язання.
Нехай a1, a2…… an, ап+1 – задані числа. Розглянемо n чисел виду a2 - a1, а3 - a1, … , ап+1 - a1 і n чисел виду a2…… an, ап+1. Кожне з цих чисел менше за 2n, а всього їх 2n, при чому числа першого і другого виду всі різні. За принципом Діріхле, принаймні одне число першого виду зорівнює числу другого виду. Залишається припустити, що деяке число ak- a1 першого виду дорівнює числу al другого виду:
ak- a1 = al,
ak = a1 + al.
Задача № 16.
Нехай a, b, x0 - деякі натуральні числа. Довести, що серед членів послідовності
x0, x1 = ax0 + b, x2 = ax1 + b, … , xn = axn – 1 + b, …
нескінченно багато чисел, які не є простими.
Розв’язання.
Задана послідовність є монотонно зростаюча, при чому всі її члени, починаючи з першого, більші від а. справді,
xn = axn
– 1 + b
Якщо числа a і b не взаємно прості і НСД(a, b) = d, то всі члени послідовності, починаючи з першого, діляться на d, d 1. У цьому разі твердження задачі справедливе.
Припустимо, що a і b взаємно прості. Тоді числа a і xk, k 1, також взаємно прості. Справді, НСД(a, xk) = l 1 і оскільки b = xk - axk, то b ділиться на l. Отже ,
НСД (a, b) = l, що суперечить припущенню. Отже, a і xk взаємно прості.
Розглянемо деяке xk, позначимо його через s. Доведемо, що серед s+1 чисел xk, xk+1, … , xk+s обов’язково знайдеться складене число. Поділимо кожне з цих чисел на s. При цьому можливі остачі : 0, 1, 2, …, s – 1. Оскільки чисел всього s+1, а можливих остач s, то серед чисел xk, xk+1, … , xk+s знайдуться два, наприклад xp і xq, p q, які при діленні на s дають однакові остачі. Різниця цих чисел ділиться на s. Оскільки
xp - xq = a(xp-1 – x q-1) і НСД(a, s) = 1, то xp-1 – x q-1 ділиться на s. Аналогічно, на s ділиться
xp-2 – x q-2 і т. д. повторюючи міркування, дійдемо до числа xk+p-q – xk . Проте число xk ділиться на s = xk тому число xk+p-q ділиться на s і отже, це число не є простим. Таким чином, серед чисел xk, xk+1, … , xk+s є число, яке не є простим. Розглянувши тепер замість xk число xk+p-q+1, знову серед кількох наступних членів послідовності можемо знайти число, яке не є простим. Таких чисел серед членів нашої послідовності нескінченно багато.
Задача № 17.
Розглянемо послідовність 1, 1, 2, 3, 5, 8, 13, 21, 34,… , у якої кожний член дорівнює сумі двох попередніх (послідовність чисел Фібоначчі). Випишемо під кожним з чисел цієї послідовності три останні його цифри :
001, 001, 002, 003, 005, 008, 013, 021, 034, … .
Довести, що ця нова
Розв’язання.
Для кожної пари сусідніх чисел Фібоначчі розглянемо пару чисел, утворених їх трьома останніми цифрами. Всього може бути щонайбільше 106 різних таких пар. Тому, за узагальненим принципом Діріхле, серед 106 + 1 послідовних чисел Фібоначчі обов’язково трапляється дві пари сусідніх членів з відповідно однаковими останніми трьома цифрами. За останніми трьома цифрами пари сусідніх чисел Фібоначчі однозначно відновлюються три останні цифри наступного числа. Звідси й випливає, що послідовність, про яку йдеться в задачі, періодична.
Задача № 18.
На клітчастому папері відзначили 5 точок, розташованих у вузлах сітки. Довести, що хоч би один з відрізків, що сполучає ці точки, проходить через вузол сітки.
Розв’язання.
Введемо на клітчастому папері систему координат з початком координат в одному з вузлів, осями, спрямованими уздовж ліній сітки, і одиничним відрізком, рівним стороні клітини. Тоді усі відмічені точки матимуть цілочисельні координати. Покажемо, що знайдуться дві точки з п'яти, у яких одна і та ж парність координат x і координат y. "Кроликами" у нас будуть точки, а " клітками" – пари (П,П)(П, Н)(Н, П)(Н, Н). Якщо, наприклад, у точки(x, y) координата x парна, а координата y непарна, то ми її помістимо в клітку (П,Н). Отже, маємо 5 " кроликів" і 4 " клітки". За принципом Діріхле, деякі дві точки мають однакову парність координат. Нехай, (х1, у1) і (х2, у2) - дві точки, що потрапили в одну " клітку". Середина відрізка, що сполучає ці дві точки, має координати( , ), які є цілими числами в силу однакової парності x1 і x2, y1 і y2. Таким чином, середина цього відрізку лежить у вузлі сітки, тобто цей відрізок є шуканим.
Задача № 19.
Усередині рівностороннього трикутника зі стороною 1 розташовані 5 точок.
Довести, що відстань між
деякими двома з них менше 0,5.
Розв’язання.
Середні лінії правильного трикутника із стороною 1 розбивають його на чотири правильні трикутнички із стороною 0,5. Назвемо їх " клітками", а точки вважатимемо "кроликами". За принципом Діріхле з п'яти точок хоча би дві опиняться в одному з чотирьох трикутничків (див. малюнок). Відстань між цими точками
менше 0,5, оскільки точки не лежать у вершинах трикутничків. (Тут використана відома лема про те, що довжина відрізку, розташованого усередині трикутника, менше довжини його найбільшої сторони).
Задача № 20.
У кожній клітинці дошки 5x5 сидить жук. В деякий момент часу всі жуки переповзають у сусідні по горизонталі чи по вертикалі клітинки. Довести, що при цьому принаймні одна клітинка залишиться порожньою.
Розв’язання.
Розмалюємо дошку 5×5 в шаховому порядку.
Нехай в результаті цього одержали 13 клітинок чорного та 12 білого кольору. Зрозуміло, що переповзаючи в сусідню клітинку, жук опиняється в клітинці протилежного кольору. Тому 12 жуків, які знаходилися спочатку у клітинках білого кольору, не зможуть зайняти всі 13 кліток чорного кольору. Принаймні одна з таких кліток залишиться вільною.
Розділ 2.
Узагальнений принцип Діріхле.
Умова збігу.
- Узагальнений принцип Діріхле
Якщо у n клітках розміщено не менше ніж nk + 1зайців, то знайдеться клітка, яка містить принаймні k + 1зайців.
Доведення.
Пронумеруємо клітки числами 1, 2, …, n. Через xі позначимо кількість кроликів у клітці з номером і, 1 і n. За умовою
x1 + x2 + … + xn
Припустимо, що x1 k, x2 k, … , xn k. Тоді
x1 + x2 + … + xn
Отримали суперечність: кількість зайців, з одного боку, більше ніж nk, а з іншого не перевищує nk. Отже, наше припущення не правильне, тобто знайдеться такий номер і, що xі k + 1. Узагальнений принцип Діріхле доведено.
При k = 1 узагальнений принцип Діріхле переходить у звичайний принцип Діріхле. У задачах на дослідження часто корисним є наступне зауваження до узагальненого принципу Діріхле.
Зауваження. Якщо рівно nk + 1зайців розташовані у n клітках, то не обов’язково знайдеться клітка з k + 2 або більше зайцями . Наприклад, можливе таке розташування зайців у клітках : n – 1 кліток містять рівно по k зайців, а n- на клітка містить k + 1 зайця.
Приклад.
У крамниці є 25 хусток різних розмірів: маленьких, середніх і великих. Доведіть, що серед них є принаймні 9 хусток одного й того самого розміру.
Розв’язання.
Проведемо міркування від супротивного. Припустимо, що маленьких хусток не більше восьми, середніх хусток не більше восьми і великих хусток не більше восьми. Тоді всього хусток не більше 8 · 3 = 24. Суперечність з тим, що за умовою у крамниці 25 хусток. Отже, у крамниці є принаймні 9 хусток одного й того ж самого розміру.
- Умова збігу
Якщо розмістити не більше ніж – 1 кроликів у n клітках, то знайдуться дві клітинки, в яких сидить однакова кількість кроликів (можливо клітки порожні).
Доведення.
Припустимо, що немає двох кліток, шо містять однакове число кроликів. Це означає. Що у всіх клітках знаходиться не менше
0 + 1 + 2 +…+
Отримали суперечність. Отже, знайдуться дві клітки, в яких однакова кількість кроликів.
Задача № 1.
У місті 2 500 000 жителів. Науковці вважають, що в кожної людини менш як 200 000 волосин на голові. Довести, що є тринадцять жителів з однаковою кількістю волосин на голові.
Розв’язання.
Припустимо, що є 200 000 ящиків, пронумерованих числами 0, 1, 2, …, 199 999 (це можливі числа волосин на голові людини).нехай число волосин кожного жителя записано на окремій картці. Таких карток 2 500 000 шт. розкладемо ці картки відповідно в ящики з номерами 0,1, … , 199 999. За узагальненим принципом Діріхле, в одному ящику повинно бути принаймні не менш як 13 карток. Справді, як би в кожному ящику було менш як 13 карток, то загальне число карток не перевищувало б 12 х 200 000 = 2 400 000.
Задача № 2.
У класі навчається 29 учнів. Під час диктанту один учень зробив 13 помилок, а всі інші учні – менше. Довести, що в класі є принаймні три учні, які зробили однакову кількість помилок.
Розв’язання.
Розіб’ємо всіх учнів в класі на 14 груп: до першої віднесемо тих учнів, які написали диктант без помилок, до другої – тих, які зробили одну помилку, до третьої – дві помилки, і т. д., до тринадцятої – тих, які зробили дванадцять помилок, чотирнадцята група складається тільки з одного учня, який зробив 13 помилок. Якби в кожній з перших тринадцяти груп було не більше від двох учнів, то загальне число учнів у класі не перевищувало б 2 х 13 + 1 = 27 учнів. Тому за узагальненим принципом Діріхле, принаймні в одній з груп повинно бути не менш ніж три учні.
Задача № 3.
Довести, що серед будь – яких 100 чисел можна знайти 15 чисел таких, що різниця будь – яких двох з них ділиться на 7 без остачі. Чи можна знайти 16 чисел, які задовольняли б ту саму умову?
Розв’язання.
Різниця двох чисел ділиться на 7 тоді і тільки тоді, коли остачі від ділення цих чисел на 7 однакові. При ділені на 7 є сім різних остач: 0, 1, 2, 3, 4, 5, 6.
Припустимо, що не можна вибрати 15 чисел, які задовольняють умову. Це означає, що чисел, які при діленні на 7 дають остачу 0, не більше як 14; чисел, які при ділені на 7 дають остачу 1, не більше як 14, і т.д., і чисел, які при ділені на 7 дають остачу 6 не більше як 14. У цьому разі маємо не більше як 7 х 14 = 98 чисел.
За узагальненим принципом Діріхле, є 15 чисел, які при діленні на 7 дають однакову остачу.
Для 16 чисел твердження задачі не виконується. Справді, розглянемо числа
1, 2,…, 100. Серед них є 14 чисел 7, 14,…, 98, які діляться на 7 без остачі, дві групи 1, 8, 15,…, 99 і 2, 9, 16,…, 100 по 15 чисел, які при діленні на 7 дають остачі 1 і 2 відповідно; чотири групи, які при діленні на 7 дають остачі 3, 4, 5, 6 відповідно. Отже, серед чисел 1, 2, … , 100 не можна виділити групу з 16 чисел, які при діленні на 7 дають однакову остачу.
Задача № 4.
У квадраті сторона
якого дорівнює 1, узяли 51 точку. Довести,
що деякі при з цих точок
обов’язково містяться
Розв’язання.
Поділимо даний квадрат на 25 однакових квадратів розмірами х . За узагальненим принципом Діріхле, принаймні в одному з них буде не менш, як три дані точки. Опишемо навколо цього квадрата коло. Його радіус буде дорівнювати
. Проте .
Задача № 5.
У шухляді лежать 10 пар чорних і 10 пар червоних рукавичок одного розміру. Яку найменшу кількість рукавичок потрібно витягти навмання із шухляди, щоб серед них було не менше: 1) двох рукавичок одного кольору; 2) однієї пари рукавичок одного кольору; 3) однієї пари рукавичок різних кольорів?