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

О Дирихлеовом принципу

Често смо у математици суочени са задацима које је тешко сврстати у неку одређену категорију задатака, већ смо принуђени да се ослонимо на логичко размишљање и закључивање. Ово је нарочито изражено код ученика у основној школи. Који још нису „наоружани“ комплекснијим математичким оружјем.

Рецимо, чест је пример да треба доказати да неки објекти имају неко својство. Искуство показује да и код прилично очигледних примера ученици наиђу на препреку типа: „чини ми се да то јесте тако, али како то да баш докажем?“. У оваквим ситуацијама се заправо веома успешно може применити тзв Дирихлеов принцип, назван тако у част познатог немачког математичара чије пуно име је Јохан Петер Густав Лежен Дирихле (1805-1859).

Пре преласка на сам Дирихлеов принцип, рећи ћемо нешто о једном од најмоћнијих оружја математичког доказивања – доказивање свођењем на апсурд, полазећи од супротне претпоставке од оне коју доказујемо. Ово, иако звучи компликовано, у ствари функционише врло једноставно. Можда ће неко поставити питање: „а откуд уопште идеја да нешто доказујем тако што ћу да претпоставим супротно?“. Наиме, да би доказали да неко својство НЕ важи за све објекте, довољно је да нађемо један контрапример, тј један објекат за  који то својство важи. Другим речима, много је лакше доказати да нешто не важи него доказати да нешто важи за све објекте.

 Примера ради, желимо да докажемо једноставно тврђење:

„ Међу свим једноцифреним бројевима постоји број дељив са 3“

 Да би доказали ово тврђење, претпоставићемо супротно:  „ међу свим једноцифреним бројевима не постоји ни један број дељив са 3“ . Да би доказали да оно не важи довољно је констатовати да је, рецимо број 6 дељив са 3 чиме смо „оборили“ поменуто тврђење. Нас не интересује да испитамо све наведене бројеве, већ самим тим што смо нашли један који се „не уклапа“ у тврђење, ми смо показали да тврђење не важи, а ако не важи да „не постоји број дељив са 3“, онда мора важити да „постоји број дељив са 3“.

Дакле, када користимо супротну претпоставку, ми је намерно и „с предумишљајем“ постављамо да би је „оборили“ и тиме доказали да она не може бити истинита, па мора бити истинита она наша почетна претпоставка супротна од ње.

Пређимо сада на сам Дирихлеов принцип.Иако он има и сложенију математичку формулацију ми ћемо покушати да га приближимо читаоцу помоћу два честа и популарна случаја који се могу применити касније у разним другим примерима. То су „принцип зечева и кавеза“ и „принцип кликера и кутија“.

Принцип зечева и кавеза:

Замислимо да имамо 9 кавеза и 10 зечева. Докажимо да ако све зечеве ставимо у кавезе, мора постојати бар један кавез у коме се налазе бар два зеца.

Доказ је, наравно прост ако се крене од супротне претпоставке. Ако би претпоставили да не постоји кавез са два зеца, онда би у сваком од кавеза било по највише један зец, па би било највише 9х1=9 зечева укупно, што је у супротности (контрадикцији) са условима задатка, па је наша претпоставка неодржива (немогућа) што значи да је истина супротна од те претпоставке тј мора постојати кавез са два зеца.

Ако овај пример мало уопштимо па посматрамо n кавеза и n+1 зечева долазимо до најосновнијег Дирихлеовог принципа зечева и кавеза:

Ако n+1 зечева треба сместити у n кавеза, онда мора постојати бар један кавез у којем су бар два зеца.

Међутим, још је очигледније да можемо уместо n+1 узети било колико зечева (само да их је више него кавеза) па да твђење опет важи.

Рецимо да треба 13 зечева сместити у 10 кавеза. Ако у сваки кавез сместимо по једног зеца, „потрошили“ смо 10 зечева, што нам оставља још 3 нераспоређена зеца, који морају у неки од кавеза, па како у сваком од кавеза већ имамо по једног то сваки од њих мора отићи у кавез у којем већ постоји зец, па ће бар у једном кавезу морати да се нађу бар два зеца.

Дакле, ако у n кавеза треба сместити m (m > n) зечева, онда постоји кавез у коме ће се наћи бар два зеца.

Принцип кликера и кутија:

Замислимо да имамо 21 кликер и 4 кутије. Докажимо да, ако све кликере спакујемо у кутије, онда међу кутијама мора постојати бар једна у којој се налази бар 6 кликера.

Ако у свакој кутији има највише 5 кликера, како кутија има 4, то даје 4х5=20 кликера а ми их имамо 21, па тај последњи кликер мора отићи у неку кутију у којој их већ има 5, што даје укупно 6 кликера у тој кутији.

Уопштено, ако kxn+1 (или више) кликера треба распоредити у k кутија, онда у барем једној кутији има n+1 кликер.

Урадимо још примера са кликерима:

1.       Доказати да ако 1045 кликера треба сместити у 261 кутију, онда постоји кутија у којој има 5 кликера.

Решење: Ако би билу у свакој кутији по 4 кликера то би дало 261х4=1044 кликера, па остаје 1 кликер који мора у неку од кутија од 4, што даје једну кутију са 5 кликера.

2.       Доказати да распоређивањем 810 кликера у 115 кутија добијамо бар једну кутију са бар 8 кликера.

Решење: како је 115х7=805 то после распоређивања од највише 7 кликера по кутијама остаје 5 нераспоређених кликера, па ће рецимо тај 806. морати у кутију од 7 кликера, па ће их у тој кутији бити 8.

Приметили смо, надам се „тактику“, ако треба да покажемо за 9 кликера ми прво израчунамо број кутија пута 8 па видимо „шта претекне“, за 15 кликера би рачунали број кутија пута 14 итд.

 Оставимо за вежбу случајеве са:

Број кутија	Укупан број кликера	Постоји кутија са најмање...кликера
8	41	6
13	92	8
15	93	7