| |

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

 

    Принципът на Дирихле (или т. нар. принцип на чекмеджетата) се използва за решаване на едни много интересни задачи. За съжаление, той не се изучава в часовете за задължителна подготовка по математика, но пък се използва на състезания и олимпиади и затова тук ще разясним неговата същност.
    Ако в училищния двор има 5 пейки и седнат 6 ученици, то логиката показва, че поне двама са седнали на една пейка. С други думи: Ако m предмета се поставят в n чекмеджета и m>n, то има чекмедже, в което са поставени поне два предмета (оттук идва и името на този принцип). А ако на тези 5 пейки седнат 12 ученици, то поне 3 ученици са седнали на една от тях. Или: Ако m предмета се поставят в n чекмеджета и m>k.n, то има чекмедже, в което са поставени поне k+1 предмета.
    Всъщност, всичко това изглежда напълно логично и очевидно. Трудността при използване в задачи е да определим кои ще са предметите, кои – чекмеджетата, което понякога не е съвсем очевидно. Даже понякога на пръв поглед не може да се прецени необходимостта от използването на принципа.
    Математическата формулировка в двата случая се изразява със следната теорема (с n(A) означаваме броя елементи на множеството А):
    І) Нека А и В са непразни крайни множества, като n(A)>n(B) и на всеки елемент от А е съпоставен по дадено правило елемент от В. Тогава съществуват два различни елемента на А, на които е съпоставен един и същ елемент на В.
    ІІ) Нека А и В са непразни крайни множества, като n(A)>k.n(B) и на всеки елемент от А е съпоставен по дадено правило елемент от В. Тогава съществуват k+1 различни елемента на А, на които е съпоставен един и същ елемент на В.
    Наистина, ако допуснем, че има най-много k различни елемента на А, на които е съпоставен един и същ елемент на В, то броят n(А) може да бъде най-много k.n(B). Но n(A)>k.n(B). Получава се противоречие.
    Този принцип носи името на немския математик Петер Густав Льожон Дирихле (1805 – 1859 г), който в своите разработки по теория на числата пръв използва подобни разсъждения.

    Да порешаваме малко задачки:
    1 зад. В нашето училище учат 750 ученици. Да се докаже, че поне трима ученици имат една и съща рождена дата.
    Реш. Датите в календара са 366 – колкото са дните във високосна година. Ако на всеки ученик (от множеството А със 750 елемента - предметите) съпоставим една дата от годината (от множеството В с 366 дни - чекмеджетата), то 750>2.366. Следователно според принципа на Дирихле има поне трима (k за нас е 2) ученици с една и съща рождена дата.
    Оставям на вас да отговорите на въпросите: колко най-малко ученици от нашето училище имат рожден ден в един и същ месец и колко ученици най-малко са родени в един и същи ден от седмицата. 
    2 зад. В квадрат със страна 1 са избрани по произволен начин 51 точки. Да се докаже, че поне три от тях се съдържат в квадрат със страна 0,2.
    Реш. Нека да разделим квадрата на 25 еднакви квадрата със стана 0,2 с прави, успоредни на страните му. Нека на множеството А на точките съпоставим множеството В на квадратите. Но 51>2.25. Следователно има поне един квадрат, който съдържа 3 точки.
    3 зад. Нека a1, a2, ..., an е пермутация на числата 1, 2, ..., n. Да се докаже, че ако n е нечетно, произведението (a1 - 1)(a2 - 2)...(an - n) е четно.
    Реш. Нека n=2k+1. Сред числата от 1 до n четните са k на брой, а нечетните k+1. Множителите, при които умаляемото е нечетно число са k+1 на брой. Да разгледаме умалителите в тези произведения – също k+1 на брой. Но тъй като четните числа са k, то поне един умалител е нечетно число. Т. е. поне един множител е четно число (като разлика на нечетни) и произведението е четно.
    4 зад. Нека k е естествено число, а А е множество от k+1 на брой естествени числа. Да се докаже, че разликата на поне два елемента на А се дели на k.
    Реш. Нека a1, a2, ...,ak+1 са елементите на А, а b1, b2, ..., bk+1 са остатъците от делението с k и 0b1k-1, 0b2k-1, ..., 0bk+1k-1 и са елементи на множеството В. Тогава можем да представим числата от А така: a1=k.c1+b1, a2=k.c2+b2, ..., ak+1=k.ck+1+bk+1. Нека на всеки елемент от А съпоставим неговия остатък при деление с k. Но елементите на А са k+1 на брой, а на В – k на брой. Тогава поне две числа от А имат еднакви остатъци. Ако това са am и an, то аm-an=k.cm+bm-k.cn+bn=k.(cm-cn), т. е. разликата се дели на k.
    Други варианти на принципа на Дирихле
    Можем да срещнем различни варианти и обобщения на този принцип. Напр. за геометрични обекти:
    Ако върху отсечка с дължина L са разположени отсечки, сумата от дължините на които е по-голяма от L (k.L), то най-малко две (k+1) от тях имат обща точка.
    Подобни твърдения могат да се изкажат за дължини на дъги от окръжност, лица на фигури, обеми на тела, мерки на ъгли и т. н.
    Принципът може да се използва напр. в следния вариант:
    Ако сумата от дължините на няколко отсечки е по-малка от L, то с тях не може да се покрие отсечка с дължина L. (подобно за лица на фигури и др.)
    Ще илюстрираме последното със следната задача:
    5 зад. В квадрат с лице S са разположени 100 фигури, сумата от лицата на които е по-голяма от 99S. Да се докаже, че всички фигури имат обща точка.
    Реш. Нека S1, S2, ... , S100 са лицата на дадените фигури, а   Q1, Q2, ... , Q100 – лицата на фигурите, които ги допълват до квадрата. Ясно е, че Sk + Qk = S. По условиe S1 + S2 + ... + S100 > 99S, тогава Q1 + Q2 + ... + Q100 = (S - S1)+ (S - S2) + ... + (S - S100) = 100S-(S1 + S2 + ... + S100) < 100S-99S = S.
    Сумата от лицата на допълващите фигури е по-малка от лицето на квадрата и следователно те не могат да покрият целия квадрат (според последния вариант на принципа на Дирихле). Т. е. ще се намери точка, която не принадлежи на нито една от тях. Тогава тази точка принадлежи ва всяка от изходните фигури и е търсената.
    Сега и малко задачи за самостоятелна работа:
    1 зад. На диктовка по английски език в един клас от 30 ученици най-много грешки направил Петър – 9 на брой. Колко най-малко ученици от класа имат еднакъв брой грешки?
    2 зад. В правоъгълна овощна градина с размери 20 м дължина 10 м ширина са засадени 201 дръвчета. Да се докаже, че има правоъгълник с размери 2 м и 1 м, в които са засадени поне 3 дръвчета.
    3 зад. Дадени са 500 кутии, във всяка от които са сложени не повече от 240 бонбона. Да се докаже, че има поне три кутии, които съдържат еднакъв брой бонбони.
    4 зад. Числата от 1 до 10 са написани в редица в произволен ред. Всяко от тях е събрано с номера на мястото, на което стои. Да се докаже, че поне две от получените суми завършват на една и съща цифра.
    5 зад. В кръг с радиус 3 по произволен начин са разположени няколко кръга, сумата от радиусите на коите е равна на 25. Да се докаже, че съществува права, която пресича не по-малко от девет кръга.
    6 зад. На квадратна маса със страна 70 см лежат 100 квадратни салфетки със страна 10 см. Да се докаже, че в масата може да се забие гвоздей, който преминава през не по-малко от три салфетки



    Използвани материали:
1. Ив. Проданов, Принцип на Дирихле
2. А. Андреев, Принцип на Дирихле /реферат/
3. Р. Русев, К. Банков, Св. Савчев, Задачи за извънкласна работа
4. http://math.ournet.md

 

 
, .
 
Curtissoi: ???? ????????? ???????? http://agrarnaja-politika.ru/ - ???