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

Едва ли в математиката може да се посочи твърдение, което да е така очевидно и същевременно да притежава толкова интересни, неочаквани и дълбоки приложения, както принципа на Дирихле.

Да си мислим, че m предмета са поставени в n чекмеджета, като при това m > n. Ясно е, че при тези предположения в поне едно от чекмеджетата ще са поставени най-малко два предмета. Това е принципът на Дирихле в най-простата му форма или принципът на "чекмеджетата", както понякога го наричат шеговито. Разбира се, така формулиран той е очевиден. Това обаче ни най-малко не намалява значението му.

В принципа на Дирихле се твърди съществуването на "чекмедже" с определени свойства. Ето защо той е едно твърдение за съществуване. Изглежда, че най-близки до ума са конструктивните доказателства за съществуване, про които обектът, чието съществуване искаме да докажем, се построява по един или друг начин. Принципът на Дирихле не дава правило за намиране на "чекмедже" с желаните свойства, поради което доказателствата, в които той се използва, не са конструктивни. Вероятно това е главната причина за неочакванотстта на приложенията му.

Ето един прост пример: От биологията се знае, че броят на космите на главата на всеки човек е по-малък от 200000. Да си мислим за 200000 чекмеджета, номерирани с числата от 0 до 199999 включително. Да "поставим" всеки софиянец в чекмежето, чийто номер е равен на броя на космите на главата му. Тъй като жителите на София са повече от 200000, то поне двама от тях, съгласно принципа на Дирихле, ще "попаднат" в едно чекмедже. Ето защо можем да твърдим, че в София има поне двама души с еднакъв брой косми на главата си.

И така, като се тръгна от един биологичен факт, с помощта на принципа на "чекмеджетата" се обосновава твърдение, чието конструктивно доказателство би създало отчайващи трудности (такова конструктивно доказателство е, например, непосредствената проверка, която води до преброяване на космите по главите на софиянци).

Аналогично може да се установи, че във всяка достатъчно голяма гора (в която броят на дърветата е по-голям от броя на листата на дървото в нея с най-много листа) има поне две дървета с еднакъв брой листа.

При посочените два примера се раглеждат крайни множества с различни по характер елементи и се изисква да се докае, че едно от тези множества притежава поне два елемента с определени свойства. Тъй като математиката изучава общото, което се среща в често нямащи на пръв поглед никаква прилика явления, то от математическо гледище разгледаните два примеране са съществено различни.

При разглеждане на проблеми, свързани с крайни множества, едно от най-простите и най-често срещани оръдия е множеството на естествените числа. Принципът на Дирихле е в същност една теорема за естествените числа, или казано малко по-общо, една теорема за крайните множества.

Колкото и да е привлекателна дадената по-горе формулировка на принципа на Дирихле, тя притежава един съществен недостатък. Известно е, че при конструирането на математически предложения имаме право да използваме само математически понятия, а понятието "чекмедже" едва ли можем да причислим към тази категория. Ето защо ще дадем една по-точна формулировка на този принцип.

Нека А и В са две непразни крайни множества, като броят на елементите на А е по-голям от броя на елементите на Б. Нека освен това е зададена някаква релация от А към В, при която на всеки елемент на А е съпоставен елемент на В. Тогава съществуват поне два различни елемента на А, които имат за образ при разглежданата релаця един и същ елемент на В.

В дадената формулировка на принципа на Дирихле се говори за произволни крайни множества. Тази общност позволява той да се прилага при решаване на различни по съдържание задачи. Най-същественият момент в нея обаче е условието за броя на елементите на А и В и връзката межру тях.

А сега да разгледаме някои примери за приложението на принципа на Дирихле.

Пример 1: В една паралелка има 40 ученика. Да се докаже, че поне двама от тях са родени в един и същи месец.

Нека множеството, съставено от учениците в паралелката, е А. Броята на неговите елементи е m = 40. Да означим с В множеството на месеците от годината. Броят на елементите на В е n = 12. Да разгледаме релацията от множеството А към множеството В, дефинирана с предиката "ученикът х е роден през месец у", където х А и у Б. тази релация е изображение, защото всеки ученик има точно един рожден месец. При това m > n т.е. броят на елементите на А е по-голям от броя на елементите на В. Тогава, съгласно принципа на дирихле, съществуват поне два различни елемента на А, които имат образ при споменатат релация (изображение) един и същ елемент на В. А това означава, че поне двама ученика от паралелката ще са родени в един и същи месец. С това задачата е решена.

При условието на решения пример 1 може да се докаже, че поне 4 ученика от паралелката са родени в един и същи месец. За тази цел би могъл да се използва методът на опровергаване на отрицанието. Да съставим отрицанието на съждението "поне четири ученика от паралелката са родени в един и същи месе" (в един и същи месец са родени 4, 5, 6 или дори всичките ученици от паралелката). То би могло да се формулира така: "не е вярно че поне четири ученика са родени в един и същи месец" или, което е все същото, че "най-много трима ученика от паралелката са родени в един и същи месец". ако приемем за вярно така формулираното отрицание, излиза, че броят на учениците в паралелката е най-много равен на 3.12 = 36, т.е. m = 40 ≤ 36 (равенството би могло да има, когато всеки месец са родени 3 ученика). Но съждението 40 ≤ 36 e невярно. Следователно нашето допускане е също невярно. Тогава остава, че твърдението "поне 4 ученика от паралелката са родени в един и същи месец" е вярно.

Естествено е да възникне въпросът не би ли могло доказаното чрез косвения метод твърдение да се докаже с помощта на принципа на Дирихле. Отговорът е положителен, но с уговорката този принцип да се усили. Това може да стане по следния начин:

Ако А и В са непразни крайни множества, с брой на елементите съответно m и n, при това m > k.n, където k е естествено число и е дефинирана релация от А към В, при която на всеки елемент на А е съпоставен елемент на В, то съществуват поне k+1 елемента на А, които имат за образ при тази релация един и същ елемент на В.

Наистина, ако допуснем, че не повече от k елемента на А имат общ образ, ще получим, че m ≤ k.n. Но съждението m ≤ k.n противоречи на условието m > k.n. Остава вярна другата възможност - съществуват поне k+1 елемента на А, които имат за образ един и същ елемент на В.

А сега да приложим усиления принцип на Дирихле за решаване на разгледания по-горе пример чрез косвения метод.

Тъй като m = 40 > 3.12 = 3.n, т.е. m > 3.n (k = 3), то, съгласно усиления принцип, поне 3 + 1 = 4 елемента на А ще имат за образ един и същи елемент на В. Това означава, че поне 4 ученикаот паралелката са родени в един и същи месец.

Пример 2. В едно училище има 30 паралелки и 1000 ученика. Да се докаже, че в това училище има паралелка с не по-малко от 34 ученика.
    Въвеждаме означенията:
    A - множеството, съставено от всички ученици в училището;
    B - множеството, съставено от всички паралелки на училището.

Броят а елементите на А е m = 1000; броят на елементи на В е n = 30. Разглеждаме релацията от А към В, дефинирана с предиката (изречението с променливи) "ученикът х е в паралелка у", където х А и у В. Тази релация е изображение, защото всеки ученик е в точно една паралелка. Освен това 1000 > 33.30 = 990,
т.е. m > k.n (k = 33). Тогава съгласно усиления принцип на Дирихле, поне 33 + 1 = 34 елемента на А ще имат за образ при разглежданата релация един и същи образ на В. Това означава, че поне 34 ученика са в една и съща паралелка или, което е все същото, в училището има паралелка с поне 34 ученика.

Задачи

1. В една борова гора има 800000 дървета, като на всяко дърво има не повече от 500000 игли (листа). Докажете, че в тази гора има поне 2 бора с еднакъв брой игли.

2. На земята живеят повече от 3.6 милиарда човека. Известно е, че не повече от 1% от тях са над 100 години. Докажете, че има поне двама човека, които са се родили в една и съща секунда.

3. В група от р човека са станали ръкувания по произволен начин. Да се докаже, че в групата има поне двама души, които са направили еднакъв брой ръкувания.

4. По произволен начин е избрана група от 5 човека. Докажете, че между тях има поне двама души, които имат еднакъв брой познати между избраните (считаме, че релацията "познанство" е симетрична).

5. В магазин за плодове и зеленчуци са докарали 25 щайги ябълки от три сорта, като във всяка щайга имало ябълки само от един сорт. Докажете, че има поне 9 щайги ябълки от един и същи сорт.

6. Да се докаже, че между произволно избрани 14 естествени числа, винаги може да се намерят две, разликата на които се дели на 13.

7. Докажете, че между произволно избрани р+1 естествени числа, винаги може да се намерят две, разликата на които се дели на р.

8. Докажете, че между произволно избрани 12 различни естествени двуцифрени числа има поне две, разликата на които е двуцифрено число, което се записва с две еднакви цифри.

9. Произволни р естествени числа са наредени в редица. Да се докаже, че поне едно от тях или сумата на няколко от тях, последователно стоящи в редицата, се дели на р.

10. От естествените числа не по-големи от 100по произволен начин са избрани 51. Докажете, че поне едно от избраните числа се дели на друго от тях.

11. Докажете, че съществува число кратно на 1983, в десетичния запис на което участват само цифрите 0 и 1.

12. Нека М е множество, съставено от 10 естествени числа ненадминаващи 100. Да се докаже, че съществуват две непресичащи се подмножества на М с еднакви суми на елементите си. (Давана на XIV международна олимпиада.)