Андрєєв А.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 ...
