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

Андрєєв А.A., Савін О.Н., Саушкін М.Н.

Введення

При вирішенні багатьох завдань використовується логічний метод міркування - "від протилежного ". У даній брошурі розглянута одна з його форм - принцип Діріхле. Цей принцип стверджує, що якщо безліч з N елементів розбито на пнепересекающіхся частин, що не мають спільних елементів, де N> n то, по крайней мірі, в одній частині буде більше одного елемента. Принцип названий на честь німецького математика Діріхле (1805-1859), який успішно застосовував його до доказу арифметичних тверджень.

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

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

Формулювання принципу Діріхле

Самая популярна формулювання принципу Діріхле звучить так:

ФОРМУЛЮВАННЯ 1. "Якщо в n клітках сидить n +1 або більше зайців, то знайдеться клітка, в якій сидять принаймні два зайці ".

Зауважимо, що в ролі зайців можуть виступати різні предмети і математичні об'єкти - числа, відрізки, місця в таблиці і т. д.

Принцип Діріхле можна сформулювати на мові множин і відображень.

ФОРМУЛЮВАННЯ 2. "При будь-якому відображенні безлічі P, що містить n +1 елементів, в безліч Q, що містить n елементів, знайдуться два елементи безлічі P, що мають один і той же образ ".

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

Наведені нижче теореми і задачі показують, що природа "зайців" і "Клітин" в різних завданнях може сильно відрізнятися один від одного.

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

Рішення

півплощини, на які пряма l розбиває площину трикутника ABC, позначимо через q 1 і q 2 ; ці півплощини будемо вважати відкритими (тобто не містять точок прямої l). Вершини розглянутого трикутника (точки A, B, C) будуть "зайцями", а півплощини q 1 і q 2 - "Клітинами". Кожен "заєць" потрапляє в яку-небудь "Клітку" (адже пряма l не проходить ні через одну з точок A, B, C). Так як "зайців" три, а "клітин" тільки дві, то знайдуться два "зайця", попавшіев одну "клітку"; інакше кажучи, знайдуться такі дві вершини трикутника ABC, які належать одній півплощині. Див малюнок.

Нехай, скажімо, точки A і B знаходяться в одній півплощині, тобто лежать по одну сторону від прямої l. Тоді відрізок AB не перетинається з l. Отже, у трикутнику ABC знайшлася сторона, яка не перетинається з прямою l.

Приклад 2. Усередині рівностороннього трикутника зі стороною 1 розташовано 5 точок. Довести, що відстань між деякими двома з них менше 0,5.

Рішення

Середні лінії правильного трикутника зі стороною 1 розбивають його на чотири правильні трикутничка зі стороною 0,5. Назвемо їх "клітинами", а точки будемо вважати "зайцями". За принципом Діріхле з п'яти точок хоча б дві опиняться в одному з чотирьох трикутничків (Див. малюнок). Відстань між цими точками менше 0,5, оскільки точки не лежать в вершинах трикутничків. (Тут використана відома лема про те, що довжина відрізка, розташованого всередині трикутника, менше довжини його найбільшої сторони.)

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

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

Приклад 4. Довести, що для будь-якого дійсного числа a> 0 і будь-якого натурального N знайдуться такі цілі m і 0 і k> 0, що | ka-m | Р€ 1 / N .

Рішення Розіб'ємо відрізок [0, 1] точками 1 / N , 2 / N , . . . , [(N-1)/(N)] на N відрізків (Див. малюнок). Отримані відрізки будемо вважати "клітинами", а числа 1, 2,. . . , N +1 приймемо як "Зайців".

Якщо k - один з "зайців", то число ka можна записати у вигляді ka = m + x, де m - ціле, 0Р€ x <1 (тобто у вигляді суми цілої і дробової частини). Число x потрапляє в одну з "клітин"; в цю "клітку" ми і посадимо "зайця" k.

Так як "зайців" більше, ніж "клітин", то знайдуться два "Зайця", що сидять в одній "клітці". Інакше кажучи, серед чисел 1, 2,. . . , N +1 знайдуться такі два числа k 1 2 , що

k 1 a = m 1 + x 1 , 0 Р€ x 1 <1,

k 2 a = m 2 + x 2 , 0 Р€ x 2 <1,

причому x 1 і x 2 знаходяться в одній "клітці", і тому | X 2 -x 1 | Р€ 1 / N .

Таким чином,

| (k 2 -k 1 ) a-(m 2 -m 1 ) | = | (k 2 am 2 ) - (k 1 -m 1 ) | = | x 2 -x 1 |

1

N

,

то є числа k = k 2 - k 1 і m = m 2 - m 1 є шуканими. Тут k> 0, так як k 2 > k 1 , і m і 0, так як k 2 ...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. Будь многочлен з цілими коефіцієнтами (відмінний від константи) при деякому натуральному значе...нні аргументу приймає значення, що представляє собою складене число.

Доказ Нехай f (x) = a 0 x n + a 1 x n - 1 +. . . + A n , де всі a i - цілі числа. Припустимо, що при деякому k значення многочлена f (x) - просте число, тобто f (k) = p, де p - просте. Багаточлен ступеня n приймає одне і те ж значення не більше ніж в n точках. (Дійсно, якщо f (x) = y 0 більше ніж в n точках x 1 , x 2 ,. . ., X n + 1 , то многочлен g (x) = f (x)-y 0 має коріння x 1 , x 2 ,. . ., X n + 1 , а, як відомо, будь многочлен не може мати більше n дійсних коренів.) Покажемо, що знайдеться таке ціле t, що f (k + pt) відмінно від 0 і p. Нам допоможе принцип Дирихле. Будемо вважати значення багаточлена (в натуральних точках) "Клітинами", а натуральні числа виду k + pt "зайцями". Натуральне число N = k + pt будемо розміщати в "клітку", відповідну значенню многочлена f (N). Згідно висловлену вище твердженням, в "Клітці" не може поместітьс більше n "зайців". Так як "Зайців" багато, то це означає, що f (k + pt) не може приймати тільки значення 0 і p при різних цілих t, тобто знайдеться "заєць" k + pt, який не потрапить ні в "клітку" 0, ні в "клітку" p. Отже, при деякому t маємо: f (k + pt) № 0 і f (k + pt) № p. Розкладаючи f (k + pt) за ступенями pt (використовуючи біном Ньютона), отримаємо

f (k + pt) = f (k) + c 1 pt + c 2 (pt) 2 +. . . + C n (pt) n ,

де всі c i - деякі цілі числа. Оскільки f (k) = p, з попереднього рівності отримуємо, що f (k + pt) ділиться на p, причому f (k + pt) № 0 і f (k + pt) № p, так що f (k + pt) - складене число. Теорема доведена.

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

Наступна теорема, сформульована П. Ферма, є одним з найбільш фундаментальних фактів в теорії подільності цілих чисел і знаходить широке застосування як в теоретичних дослідженнях, так і в арифметичних додатках.

МАЛА ТЕОРЕМА ФЕРМА. Якщо p - просте число, a - ціле число, не ділиться, на p, то a p - 1 при діленні на p дає залишок 1, тобто

a p - 1 є 1 (mod p).

Доказ Кожне з p - 1 чисел a, 2a,. . ., (P-1) a ("зайців") дає при діленні на p ненульовий залишок (адже a не ділиться на p):

a = k 1 p + r 1 ,

2a = k 2 p + r 2 ,

. . . . . . . . . . . . . . .

(p - 1) a = k p - 1 p + r p - 1 .

Якщо число різних зустрічаються тут залишків ("клітин") менше p - 1, то серед них знайдуться принаймні два однакових ("в клітці по крайней мірі два зайці "). Але це неможливо, так як при r n = r m число (nm) a = (k n -k m ) p ділиться на p, що суперечливо, бо | nm |

1 ,. . . , R p - 1 між собою різні і утворюють перестановку чисел 1, 2, . . . , P - 1. Перемножая всі попередні рівності, отримуємо

(p-1)! a p - 1 = N В· p + r 1 r 2 В·. . . В· R p - 1 = Np + (p-1)!,

де N - деяке ціле число. Отже, (p-1)! В· (A p-1 -1) ділиться на p, а тоді і a p - 1 - 1 ділиться на p. Теорема доведена.

Слідство. Якщо p - просте число, то при будь-якому цілому a різниця a p - a ділиться на p.

Крім малої теореми Ферма застосування принципу Діріхле до залишків при діленні зустрічається в багатьох інших завданнях елементарної теорії чисел. Можлива наступна переформулировка принципу Діріхле:

"Серед p + 1 цілих чисел знайдуться два числа, що дають при діленні на p один і той же залишок ".

При розподіл із залишком на p може зустрітися кінцеве число різних залишків: 0, 1, 2,. . . , P-1. Вони то і грають тут роль "клітин", а самі цілі числа є "зайцями". Так як чисел ("зайців") більше, ніж залишків ("клітин"), то хоча б два числа "сидять в одному клітці ", тобто мають однакові залишки при діленні на p. Розглянемо класичні приклади.

Приклад 10.

Рішення

Приклад 11. . .

Рішення

. . . . . . . . . . . . . . . . . . .

.

Якщо Припустимо, . . ділиться на 100. .

.

Приклад 12.

Рішення

Розглянемо . . . . .

. . . . . ., N.

Доказ Нехай теорема . . . . . . . Суперечність.

Таким . . . Теорема доведена.

Стосовно

"Якщо

Для

"Якщо

"Якщо

В

"Якщо

"Якщо

В

Приклад 13.

Рішення . . . . . тому

. .

Таким

Приклад 14.чином поміщені кілька кіл, сума радіусів яких дорівнює 25. Довести, що знайдеться пряма, що перетинає НЕ менше дев'яти з цих кіл.

Рішення Спроектуємо всі кола на довільний діаметр AB великого кола (AB = 6). Сума довжин проекцій, очевидно, дорівнює сумі діаметрів кіл, тобто 50. Оскільки 50> 8AB, то на відрізку AB є точка, що належить проекціям по крайней мірою дев'яти кіл. Пряма, що проходить через цю точку і перпендикулярна діаметру AB, - шукана.

Приклад 15. Дана фігура площі більше N. Довести, що в ній знайдуться N +1 точок, різниці відповідних координат яких - цілі числа.

Рішення Розіб'ємо вихідну фігуру паралельним...и прямими, розташованими на відстані 1, на клітини. (В якості таких прямих можна взяти, наприклад, лінії цілочисельний сітки.) Деякі клітини будуть покриватися фігурою повністю, інші - лише частково. Виділимо яку-небудь одну клітину і з допомогою паралельних переносів перенесемо на цю клітину всі шматочки фігури, які вийшли в результаті її перетину з усіма клітинами. {Наочно це можна описати так. Уявіть, що фігура намальована на картатій папері. Розріжте папір по клітинам і складіть їх в стопку, переносячи їх паралельно і не перевертаючи, а потім спроектуйте стопку на виділену клітинку.}

Площі проекцій частин фігури в сумі дадуть площа самої фігури, тобто більше N. Тому на виділеній клітці (площі 1) згідно з принципом Діріхле знайдеться точка X, покрита не менше N +1 шматочками фігури. Повернемося тепер до вихідної фігурі і відзначимо на ній N +1 точок, що проектуються у точку X при перенесенні клітин. Ці точки будуть шуканими, тому після перенесення шматочка фігури в виділену клітинку координати кожної точки цього шматочка змінюються на ціле число.

Приклад 16. У кубі з ребром a лежить ламана, яку кожна площина, паралельна однією з граней, перетинає не більше k разів. Довести, що довжина ламаної менше 3ka.

Рішення Введемо в просторі прямокутну систему координат, осі якої направимо уздовж ребер куба. Нехай ламана складається з декількох відрізків, довжини яких ми позначимо через L k .

Нехай x k , y k , z k - проекції відрізка L k на осі координат. Тоді L k = [Ц (x 2 k + y 2 k + z 2 k )]. Задачу будемо розв'язувати методом від протилежного. Припустимо, що довжина ламаного не менше 3ka. Тоді спробуємо знайти площину, паралельну одній з граней, яка перетне ламану не менш ніж у k +1 точках. Спроектуємо ламану на три грані куба, розташовані в площинах XOY, YOZ і XOZ, і розглянемо одну з таких проекцій, наприклад, XOY (Див. малюнок).

Кожен k-ий відрізок спроектованої ламаної утворює також 4 проекції на сторонах квадрата, сума довжин яких дорівнює 2 (x k + y k ). Якщо скласти довжини всіх таких проекцій для кожного відрізка, то отримаємо S2 (x k + Y k ). Якби ця величина була більшою 4ka (тобто більш ніж в k разів перевершувала периметр квадрата), то за принципом Діріхле на одній зі сторін квадрата знайшлася б точка, покрита не менше ніж k +1 проекціями. Тоді пряма, проведена через цю точку і паралельна стороні квадрата, перетне проекцію вихідної ламаної не менш ніж у k + 1 точках. Значить, якщо через цю пряму провести площину, паралельну грані, то вона перетне вихідну ламану по крайней мірою в k + 1 точках.

Залишилося показати, що для однієї з трьох граней, на які проектувалася ламана, сума довжин проекцій, що лежать на сторонах квадрата, буде більше 4ka, тобто одна з величин S2 (x k + y k ), S2 (z k + y k ), S2 (x k + z k ) більше 4ka. Довжина ламаної дорівнює SL k = S [Ц (x 2 k + y 2 k + z 2 k )] і по припущенню не менше 3ka. Тому отримуємо

3ka Р€ S

___________

Цx 2 k + y 2 k + z 2 k

k + y k + z k ) =

= (1/4) В· (S2 (x k + y k ) + S2 (y k + z k ) + S2 (x k + z k )),

звідки

S2 (x k + y k ) + S2 (y k + z k ) + S2 (x k + z k )> 3.4 ka.

Якщо сума трьох доданків більше 3.4 ka, то принаймні одне з них більше 4ka, що й потрібно.

Безперервний принцип Діріхле

Як правило, цей принцип застосовується для декількох чисел та їх суми. У загальному вигляді для чисел він виглядає наступним чином:

"Якщо сума n чисел більше S, то принаймні одне з цих чисел більше S/n ".

По-іншому його можна сформулювати так:

"Якщо середнє арифметичне кількох чисел більше a, то хоча б одне з цих чисел більше a ";

або в термінах "зайців":

"Якщо n кроликів з'їли m кг трави, то якийсь кролик з'їв не менше m/n кг трави ".

Крім того, існує проста геометрична інтерпретація безперервного принципу Діріхле:

"Нехай з деякої точки на площині проведено N різних променів; тоді кут між деякими двома з них не менше 360 В° /N ".

Зрозуміло, що якщо розглядати тільки кути між сусідніми променями, то все вийде N кутів (Див. малюнок). У сумі вони складають повний кут, рівний 360 В° . Отже,

по безперервному принципом Діріхле градусна міра одного з цих кутів не менше 360 В° /N (Інакше їх сума буде менше 360 В° ).

Розглянутий принцип називається безперервним остільки, оскільки тут числа (або градусні міри кутів) можуть приймати будь-яке значення з деякого проміжку, в той час як принцип Діріхле в звичайному сенсі оперує з дискретним набором об'єктів ("Зайців") - було б абсурдним припускати, що в клітині може виявитися, скажімо, два з половиною зайця.

Приклад 17. На площині дано n попарно непаралельних прямих. Довести, що знайдуться дві з них, кут між якими не менше 180 В° /n.

Вказівка. Досить перенести прямі паралельно самим собі так, щоб всі вони проходили через одну точку. З цієї точки буде виходити 2n променів, і тепер можна застосувати принцип Діріхле.

Приклад 18. На полях шахівниці 8 Г— 8 розставлені дійсні числа, кожні два з яких відрізняються не менш ніж на 1/9. Довести, що є пара сусідніх (Що мають загальну сторону) клітин, різницю чисел в яких не менше 1/2.

Рішення Нехай A - найменше з виписаних на дошці чисел, а B - найбільше. Покажемо, що B-A і7.

Запишемо числа в порядку зростання (зауважимо, що ніякі два числа не рівні):

x 1 2 3 <... 63 64

(тут x 1 = A, x 64 = B).

Тоді

B - A = x 64 - x 1 = (x 64 - x 63 ) +

+ (x 63 - x 62 ) +. . . + (X 3 - x 2 ) + (X 2 - x 1 ) i

и (1/9) + (1/9) + ... + (1/9) = 63 В· (1/9) = 7.

Припустимо тепер, що твердження задачі невірно, тобто в будь-якій парі сусідніх клітин числа відрізняються менше ніж на 1/2. Розглянемо дві клітини, в яких записані числа A і B. Зрозуміло, що, переходячи з клітки в клітку, можна потрапити з клітки A в клітку B, зробивши не більше 14 переходів. Найгірший випадок, коли потрібно зробити рівно 14 переходів, показаний на малюнку (A, B - протилежні клітини). За припущенням прирощення на кожному переході менше 1/2. Тому B - A <14 В· (1/2) = 7. Суперечність.

Список літератури

[1] Андрєєв А.А., Горєлов Г.Н., Люльов А.І., Савін О.І. "Принцип Діріхле", Самара "Піфагор", 1997р

[2] І. Л. Бабинська. Завдання математичних олімпіад. М.: Наука, 1975.

[3] Д. X. Муштарі. Підготовка до математичних олімпіад: завдання, теми, методи. Казанський ун-т, 1990.

[4] В. В. Прасолов. Завдання з планіметрії. Ч. 2. М.: Наука, 1991.

[5] В. Г. Болтянський. Шість зайців в п'яти клітинах. // Ж-л В«КВАНТВ», 1977, No2.

[6] А. А. Леман. Збірник завдань московських математичних олімпіад. Під ред. В.Г. Болтянський. М.: Просвещение, 1965.

[7] Ю. Ф. Фоміних. Принцип Діріхле. // Ж-л В«Математика в школіВ», 1996, No3.