Citat

уторак, 20. март 2012.

Дирихлеов принцип - 2. део


У наставку ћемо се позабавити примерима где ћемо „препознати“ могућност примене Дирихлеовог принципа.
Решимо следеће задатке:
1.       Ако у одељењу има 32 ученика, доказати да бар два ученика имају презиме које почиње истим словом.
Решење: У овом примеру ученици имају улогу „зечева“ а слова азбуке улогу „кавеза“. Како слова има 30 то по Дирихлеовом принципу, ако првих 30 ученика и има сваки различито почетно слово презимена, већ онај 31. ученик мора имати почетно слово презимена исто као неко од његових другова.
2.       Доказати да у школи која има 1100 ученика постоје бар 4 ученика који славе рођендан истог дана.
Решење: овде су ученици „кликери“ а дани у години су „кутије“. Како ученика – кликера има 1100 , а дана – кутија 366 (нека је и година преступна), и како се траже 4 ученика – кликера, добијамо:
1100=366х3+2
Тако да, кад би сваког дана било највише 3 ученика који славе рођендан, било би их 1098, па од преостале двојице један би морао славити рођендан са још тројицом другова.
3.       У једној основној школи у сваком разреду има по три одељења. Ако је укупан број ученика у тој школи 613, доказати да постоји одељење у којем има више од 25 ученика.
Решење:  Одељења има 24, питање је да ли постоји одељење са 26 или више ученика. Како је 613 : 25 = 24 уз остатак 13, то значи да ако би усваком одељењу било највише 25 ученика, преостаје нам још 13 ученика, те сваки од њих мора бити у неком од одељења где већ има 25 ученика, чиме смо доказали постојање одељења са више од 25 ученика.
Заједничко за ове задатке је да смо на неки начин увек посматрали најгори могући сценарио по нас. Оваква логика се може илустровати и у разним примерима са извлачењем предмета.
4.  Нека у кутији имамо 10 црвених, 8 плавих, 8 зелених и 4 жуте куглице. Колико најмање куглица треба да извучемо из кутије да би били сигурни да међу извученим куглицама имамо све четири боје? А колико да би били сигурни да међу њима има 6 плавих?
Решење: Како је најгора ситуација по нас (захтеваће највише извлачења) да извучемо прво све куглице у једној боји и како црвених има највише, најнеповољније би било да извучемо прво 10 црвених, па 8 плавих, па 8 зелених, што је укупно 26 извучених куглица. Али онда 27. Куглица мора бити жута што нам даје сигурност да имамо међу извученим куглицама заступљене све четири боје.
Што се тиче другог питања везаног за плаве куглице оставићемо читаоцу да се увери да је најмањи број извлачења 28.