a - k 1 a = (m 2 + x 2 ) - (M 1 + x 1 )> 0, звідки m 2 - m 1 > X 1 - x 2 > -1 (адже 0 Р€ x 1 <1 і 0 Р€ x 2 <1), і оскільки m 1 і m 2 - цілі числа, m 2 - m 1 і 0.
Приклад 5. На картатій папері відзначили 5 точок, розташованих у вузлах клітин. Довести, що хоча б один з відрізків, що з'єднують ці точки, проходить через вузол клітини.
Рішення Введемо на картатій папері систему координат з початком координат в одному з вузлів, осями, спрямованими уздовж ліній сітки, і одиничним відрізком, рівним стороні клітини. Тоді всі відзначені точки будуть мати цілочисельні координати. Покажемо, що знайдуться дві точки з п'яти, у яких одна і та ж парність координат x і координат y. "Зайцями" у нас будуть точки, а "Клітинами" - пари (Ч, Ч), (Ч, Н), (Н, Ч), (Н, Н). Якщо, наприклад, у точки (x, y) координата x парна, а координата y непарна, то ми її помістимо в "клітку" (Ч, Н). Отже, 5 "зайців" і 4 "клітини". Нехай (x 1 , y 1 ) і (x 2 , y 2 ) - дві точки, що потрапили в одну "Клітку". Середина відрізка, що з'єднує ці дві точки, має координати ([(x 1 + x 2 )/2], [(y 1 + y 2 ) /2]), які є цілими числами в силу однакової парності x 1 і x 2 , y 1 і y 2 . Таким чином, середина цього відрізка лежить у вузлі сітки, тобто даний відрізок є шуканим.
Приклад 6. На довгій прямолінійною дорозі з рівними інтервалами вириті невеликі поперечні канавки (Див. малюнок). Відстань між центрами кожних двох сусідніх канавок одно Ц2 метрів. Довести, що якими б вузенькими ці канавки не були зроблені, людина, що крокує по дорозі і має довжину кроку 1 метр, рано чи пізно потрапить в одну з канавок.
Рішення Уявімо, що ми можемо "намотати" дорогу на барабан, довжина окружності якого дорівнює Ц2 метрів. Тоді всі канавки на цьому барабані сполучаться, а кожен крок людини буде зображуватися на окружності дугою довжини 1 метр. Будемо послідовно відзначати на окружності слід людини після першого, другого, третього і так далі кроків. Нам треба довести, що хоча б один з цих слідів потрапить всередину заданої на окружності дуги, що зображає канавку, якою б малою не була довжина h цієї дуги. Неважко зрозуміти, що якщо нам вдасться знайти такі k і m, для яких сліди k-го і (k + m)-го кроків видалені один від одного (на окружності) менше ніж на h, то необхідну твердження доведе легко. Адже ще після m кроків новий слід (тобто (k +2 m)-й) знову зрушиться на відстань меншу h, потім ми розглянемо наступні m кроків і так далі. Ясно тепер, що, зробивши кілька разів по m кроків, ми неминуче виявимо слід, що потрапив в канавку (тому що, переміщаючись на одне і те ж відстань, меншу h, не можна "переступити" канавку ширини h). Отже, потрібно знайти два сліди, що знаходяться на окружності на відстані, меншій h. Ось тут-то і допомагають "зайці". Дійсно, розділимо коло на дуги, кожна з яких має довжину менше h; ці дуги ми і назвемо "Клітинами". Нехай їх мається p штук. Якщо ми візьмемо число слідів більше, ніж p (зауважимо, що ніякі два сліди не співпадуть в силу ірраціональності числа Ц2), то за принципом Діріхле хоча б в одну з кліток потрапить більше одного сліду ("зайця"). Відстань між двома слідами, потрапили в одну "клітку", менше h; цим наше твердження і доведено.
В ряді задач застосовують наступне узагальнення принципу Діріхле.
ФОРМУЛЮВАННЯ 3. "Якщо nk +1 зайців розміщені в n клітках, то знайдуться k +1 зайців, які посаджені в одну клітку (n, k - натуральні числа) ".
Узагальнений принцип Діріхле також досить очевидний: якби в кожній клітині сиділа не більш k зайців, то у всіх клітинах було б не більше nk зайців, що суперечить умові. Узагальнення принципу використовують, коли потрібно виявити декілька (три і більше) об'єктів, що володіють деяким властивістю. Розберемо декілька прикладів.
Приклад 7. У прямокутнику 5 Г— 6 закрашено 19 клітин. Доведіть, що в ньому можна вибрати квадрат 2 Г— 2, в якому закрашено не менше трьох клітин.
Рішення
Розділимо прямокутник на 6 частин по 5 клітин (див. малюнок). Згідно з принципом Діріхле в одній з цих частин буде зафарбовано не менше 4 клітин. Тоді в квадраті 2 Г— 2, що міститься в цій частині, закрашено або 3, або 4 клітки. Це і буде шуканий квадрат.
Приклад 8. У класі 25 чоловік. Відомо, що серед будь-яких трьох з них є двоє друзів. Доведіть, що є учень, у якого не менше 12 друзів.
Рішення Виберемо будь-яких двох учнів класу, які не дружать між собою. (Якщо таких ні, то всі учні класу дружать між собою, значить, у кожного є 24 одного, і задача вирішена.) З решти 23 учнів кожен дружить з одним з цих двох, інакше ми мали б трійку учнів, серед яких не було б друзів. Тоді в одного з обраних двох учнів не менше 12 друзів. (23 "Зайця" розсаджені в двох "клітках".)
Приклад 9. У одиничний квадрат кинули 51 точку. Довести, що якісь три з них можна накрити кругом радіуса 1/7.
Рішення Розіб'ємо даний квадрат на 25 однакових квадратиків ("клітин") зі стороною 1/5. В один з них потрапить не менше трьох точок ("зайців"). Коло, описане навколо квадратика зі стороною 1/5, має радіус 1 / 5 В· [(Ц2)/2] = [1/([Ц50])] <[1/([Ц49])] = 1 / 7 , тому цей квадратик можна накрити кругом радіуса 1/7.
Принцип Діріхле в теорії чисел
Наступну теорему часто використовують у шкільному курсі алгебри, але доказ не розглядають. Його дуже просто отримати за допомогою принципу Діріхле.
ТЕОРЕМА 1. Нехай p, q - натуральні числа, p
Доказ Будемо ділити p на q "куточком" і стежити за залишками. Якщо на якомусь кроці залишок буде нульовим, то вийде кінцева дріб. Якщо ж всі залишки будуть відмінні від нуля, то раціональне число p/q запишеться у вигляді нескінченної десяткового дробу. Доведемо, що вона буде періодичною. Кожен раз при знаходженні черговий цифри приватного виходитиме в залишку одне з чисел 1, 2, ..., q-1. Ці можливі значення залишків ми і будемо вважати "Клітинами", так що все мається q-1 "клітин". "Зайцями" ж будуть залишки, які виходять в дійсності при виконанні ділення (Див. малюнок). Розглянемо перший q "зайців". Так як їх на 1 більше, ніж число "клітин", то якісь два "Зайця" потраплять в одну "клітку". Іншими словами, не пізніше, ніж через q - 1 кроків почнуть повторюватися залишки, а слідом за цим - і цифри в приватному. Дійсно, якщо на деякому кроці повторився залишок, то, приписавши як зазвичай до нього 0, ми одержимо те ж число, що було колись, а, значить, знесемо в приватне ту ж саму цифру, що і раніше; тому наші дії почнуть повторюватися. Таким чином, вийде періодична десятковий дріб із періодом довжиною не більше q - 1.
З Віддавна математиків цікавило питання про існування функцій f (k), значеннями яких при всіх натуральних k були б тільки прості числа. Відомі функції, які беруть підряд багато простих значень. Наприклад, Ейлер вказав цікавий многочлен x 2 - x + 41, який при всіх цілих x від -39 до 40 включно приймає тільки прості значення (тобто при x = 0, В± 1, В± 2,. . . , В± 39, 40). Однак при x = 41 і x = 42 значення цього многочлена будуть вже складовими числами. У загальному випадку многочлен з цілими коефіцієнтами не може при всіх натуральних значеннях аргументу приймати тільки прості значення.
ТЕОРЕМА 2. Будь многочлен з цілими коефіцієнтами (відмінний від константи) при деякому натуральному значе...
