ПРИНЦИПЪТ НА ДИРИХЛЕ

Принципът на Дирихле, който понякога се нарича „принципът на чекмеджетата”, е „очевидно” твърдение с интересни, неочаквани и значими приложения в най-различни области на математиката. С негова помощ в някои случаи лесно се доказва съществуването на обекти с определено свойство. В най - простата си форма той може да се формулира така: ако m предмета са поставени в n чекмеджета и m > n, поне в едно чекмедже има най-малко два предмета.

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

Ще разгледаме няколко задачи, при решаването на, който се използва принципът на Дирихле.

1 зад. В един хубав град има хубава традиция: всяка година на 24 май се прави тържество за всички ученици, които през същата година навършват 18г. На 24 май 2007г. се събрали 400 ученика. Да се докаже , че поне двама от тях са от тях са родени в един и същи ден.

Р е ш е н и е: Присъстващите на тържеството са родени през 2007г., която има 365 дни. Да разгледаме 365 чекмеджета, номерирани с числата от 1 до 365. Да „поставим” в първото от тях учениците, родени на 1 януари 2007 година, във второто – тези, които са родени на 2 януари 2007г. и т. н.; в 365 чекмедже да „поставим” родените на 31 декември 2007г. Тъй като броят на учениците (400) е по- голям от броя на чекмеджетата (365), според принципа на Дирихле поне двама ученици ще бъдат „поставени в едно и също чекмедже, а това означава, че те са родени в един и същи ден.

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

3 зад. От биологията е известно, че космите по главата на всеки човек са по- малко от 200000. Да се докаже, че сред жителите на София, които са повече от 1000000, има поне 6 души с еднакъв брой косми на главата.

Р е ш е н и е: Да разгледаме 200000 чекмеджета, номерирани с числата от 0 до 199999. Да „поставим” всеки жител на София в чекмедже, чийто номер е равен на броя на космите по главата му. Ако допуснем, че няма шест души с еднакъв брой косми по главата, във всяко чекмедже ще има най – много по пет души. Тогава всички жители на София са най – много 5.200 000 = 1 000 000, което е противоречие.

4 зад. Тридесет ученици правили диктовка. Един от тях направил 14 грешки, а другите по-малко. Да се докаже, че има поне трима, които са направили еднакъв брой грешки.

5 зад. Да се докаже, че във всяка компания от 5 човека има поне двама с еднакъв брой познати сред присъствуващите (ще считаме, че Иван познава Гошо, когато Гошо познава Иван).

6 зад. Числата от 1 до 10 са написани в редица в произволен ред. Всяко от тях е събрано с номера на мястото на, на което стои. Да се докаже, че поне две от получените цифри завършват на една и съща цифра.

Р е ш е н и е: Да допуснем, че получените десет суми завършват с различни цифри. Тогава тези цифри са 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Следователно сумата на десетте получени суми завършва на цифрата 5, защото 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9= 45. Но сумата на всички на всички получени суми е равна на 2. ( 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 +10) = 110 и завършва на 0, а не на 5. Противоречие.

7 зад. В квадрат със страна 1 са избрани по произволен начин 51 точки. Да се докаже, че поне три от тях се съдържат в квадрат със страна 0,2.

Р е ш е н и е: Да разделим дадения квадрат на 25 еднакви квадрата със страна 0,2 с прави, успоредни на страните му. Ако допуснем, че във всеки от получените квадрати има (вътре или по страните му) не повече от две точки, то всичките точки в големия квадрат ще са най-много 2.25=50 – противоречие.

8 зад. а) Възможно ли е девет монети да се поставят в четири джоба по такъв начин, че във всеки джоб да има монета и във всеки два джоба да различен брой монети?

б) На двадесет и едно деца разделили 200 ореха. Да се докаже, че поне две деца имат еднакъв брой орехи ( може и по 0 ореха).

9 зад. Пет съпружески двойки се събрали на тържество. Разменили се много ръкостискания, но никой не се е ръкувал сам себе си или със съпруга (съпругата) си. Също така никой не се ръкувал повече от един път с един и същ човек. След като свършили поздравленията, един от мъжете, на име Асен, попитал, всички присъстващи, включително и жена си, колко ръце са стиснали. Оказало се, че деветима записани казали различни числа. Колко ръце е стиснала жената на Асен?