Дирицхлетов принцип: проблеми са решењима

Постоји много принципа у математици. Неки од њих су прилично једноставни и разумљиви чак и за почетнике, а неки захтијевају одређена објашњења и доказе. Међутим, сви су они веома ефикасни и могу се лако применити у пракси. Један од њих је Дирицхлетов принцип (познат и као принцип голуб / зец). Ово је прилично једноставна тврдња која може помоћи у рјешавању многих математичких проблема.

Хистори оф

Овај принцип формулисао је почасни немачки математичар Јоханн Дирицхлет 1834. године. Данас се користи у комбинаторици, као иу математичкој физици. Преведено са оригиналног немачког, звучи као "принцип кутија". Научник је спровео истраживање са зечевима и контејнерима. Он је показао да ако ставимо, рецимо, 5 зечева у 7 контејнера, онда би барем у једном контејнеру било 5/7 од једне животиње. Међутим, зец се не може поделити на делове, тако да ће најмање једна ћелија бити празна (5/7 је 0 целих бројева). На исти начин, у супротном смеру, ако има 7 зечева и 5 кутија, онда барем један од њих има 2 зеца (7/5 је 2 нетакнута). Полазећи од те тврдње, математика је успјела формулирати принцип који већ годинама осигурава успјешно рјешавање проблема из математике.

Модерна формулација и доказ

Данас постоји неколико различитих формулација овог принципа. Најразумљивије и најједноставније значи да је немогуће засадити 8 кунића у 3 кавеза тако да сваки има више од 2. Знанственија и сложенија формулација која објашњава Дирицхлетов принцип каже: ако има к + 1 зечева у к станицама, онда најмање Најмање једна ћелија ће садржати више од једног зеца. И ако има к-1 зечева у к ћелијама, онда ће најмање 1 ћелија садржати мање од једног зеца. Доказ ове тврдње је прилично једноставан, да тако кажем, контрадикторним. Ако претпоставимо да је у свакој ћелији мање зечева од к-1 / к, онда је к ћелија зечева мање од к * к-1 / к = к-1, што је у супротности са почетним условима.

У ствари, такав једноставан и разумљив принцип увелико олакшава решавање проблема у математици и доказ многих тешких теорема. Потребно је само узети у обзир да се зечеви и ћелије могу лако заменити математичким објектима и објектима (бројеви, тачке, сегменти, фигуре, итд.).

Још једна формулација

Понекад задаци по Дирицхлетовом принципу нису тако једноставни и очигледни као код животиња у кутијама. Потребно је пренијети овај принцип на математичке скупове како би се пронашла било каква рјешења. У овом случају, можете се ослонити на другачију, сложенију формулацију.

Ако мапирамо скуп С који садржи д + 1 елементе у скуп Р са скупом елемената д, онда ће два елемента из скупа С имати исту слику.

Иако модерни ГЕФ у математици намеће креативне захтјеве студентима и нуди нестандардне опције, рјешење кроз Дирицхлетову тврдњу није увијек тако једноставно и једноставно. Понекад је веома тешко одредити коју вредност треба узети у обзир као животињу, а која као кавез, и како чињеница да имају двије животиње у једном кавезу помаже у рјешавању проблема. И ако успемо да то схватимо, још увек је немогуће одредити у којој ће целини бити објекат. То јест, можете једноставно доказати постојање такве ћелије, али не можете је конкретизовати.

Пример број 1. Геометрија

Савремени примери решавања проблема показују да савршени различити математички објекти могу деловати као животиње и ћелије.

Задатак

Линија к пролази кроз раван троугла АБЦ, али не сијече нити један од његових врхова. Неопходно је доказати да не може прећи три стране.

Решење

Замислите како линија к дели троугао на две равни, назовимо их с1 и с2. Претпостављамо да су с1 и с2 отворени, односно да не садрже л. Сада је вријеме да примијенимо Дирицхлетов принцип. Задаци са решењима могу показати да у савременим условима зечеви и ћелије подразумевају различите објекте. Дакле, уместо зечева, замењујемо вертикале троугла, а уместо ћелија - полу-равни. Будући да нацртана линија к не сијече нити један од врхова, сваки од њих је у једној или другој равнини. Али будући да у троуглу постоје три врха и имамо само две равни (с1 и с2), једна од њих ће садржати два врха. Претпоставимо да су то врхови А и Б, и они су у полу равнини с2 (то јест, леже на истој страни к). У овом случају сегмент АБ не сијече правац к. То јест, постоји страна у троуглу која се не укршта.

Алтернативе солутион

У овом задатку смо претпоставили да су тачке А и Б у истој равни, али Дирицхлетов принцип не указује на специфичну ћелију, тако да можемо указати и на то да су тачке Ц и Б, или А и Ц лоциране у истој равни. није битно која страна троугла има праву л крижану линију. Стога је овај принцип идеалан за његово рјешавање.

Пример бр. 2. Геометрија

Задатак

У средини једнакостраничног троугла АБЦ (у коме је АБ = БЦ = АЦ = 1) лоцирано је 5 тачака. Неопходно је доказати да се два налазе на удаљености мањој од 0,5.

Решење

Ако нацртате средње линије у десном АБЦ троуглу, они га деле на 4 мала правоугаоника са странама ½ = 0.5. Претпоставимо да су ови троуглови ћелије, а тачке унутар њих су зечеви. Испоставило се да имамо 5 зечева и 4 ћелије, тако да ће у једном од њих бити најмање два зеца. С обзиром да тачке нису врхови (будући да се налазе унутар троугла АБЦ, а не на једној од његових страна), они ће бити смјештени унутар малих фигура. Према томе, удаљеност између њих ће бити мања од 0,5 (пошто величина сегмента унутар троугла никада не прелази величину његове највеће стране).

Пример број 3. Комбинаторика

У другим областима, Дирицхлетов принцип се такође може успешно применити: комбинаторика и математичка физика већ дуго се заснивају на томе у решавању проблема.

Задатак

На пример, око заобљеног стола, м заставе различитих земаља стоје на једнаким међусобним удаљеностима, а за столом сједе представници из сваке земље, сваки од њих се налази поред туђе заставе. Неопходно је доказати да ће се уз одређену ротацију стола бар два представника налазити близу својих застава.

Решење

Испоставља се да постоје м-1 начини да се табела прошири тако да се мијења међусобни распоред представника и застава (ако искључимо почетни положај табеле), али остаје м заступника.

Ми примењујемо Дирицхлетову тврдњу на решење и означавамо да су представници зечеви, а одређене позиције табела током ротације су ћелије. У овом случају, потребно је направити аналогију између локације представника поред одговарајуће заставе и испуњених ћелија. То јест, позитиван резултат (један представник је постављен близу његове заставе) је еквивалентан резултату “зец је у кавезу”. Разумемо да имамо једну ћелију мању него што је потребно (м-1), што значи да ће један од њих имати најмање 2 зеца. Истовремено, нису искључене ситуације да ће неки кавез бити празан (ниједан представник не одговара застави), али у неком кавезу ће бити два, три или чак више зечева (два, три или више представника ће се подударати са заставама). Тако ће се, уз једну одређену ротацију, најмање два представника наћи близу својих застава (најмање два зеца ће пасти у једну ћелију).

Започињући рјешавање таквог проблема, важно је разумјети да је почетна позиција и ћелија, али према стању проблема очигледно је празна, тако да укупну вриједност смањујемо за 1 (м-1).

Пример број 4. Теорија бројева

Дирицхлетов принцип у теорији бројева је такође од највеће важности.

Задатак

Претпоставимо, на комаду биљежнице у кавезу, ученик насумце у чворовима ћелија стави 5 бодова. Потребно је доказати да најмање један сегмент са врховима на овим тачкама пролази кроз чвор ћелије.

Решење

Прво треба да прикажете на листу бележнице координатни систем, чија се основа налази у једном од чворова. Оси координатног система ће се подударати са линијама мреже, а страна ћелије се узима као један сегмент. Испоставља се да ће свих 5 означених тачака бити у систему, а њихове координате ће бити само цијели број (парне или непарне). Тако добијамо 4 опције координата: (парне, парне), (непарне, парне), (парне, непарне) и (непарне, непарне). Дакле, 2 од 5 бодова ће одговарати једној варијанти. Ако погледате ситуацију из Дирицхлетове позиције, онда морате да одредите тачке као зечеве, а опције координата - као ћелије. Добијамо 5 птица са једним каменом и 4 кавеза, у једном од њих ће бити најмање 2 животиње. Претпоставимо да су то тачке П и А, са координатама (к ₄ , и ₃ ) и (к ₅ , и ₆ ). Средина сегмента који повезује ова два врха ће имати координате ((к ₄ + к ₅ ) / 2), ((и ₃ + и ₆ ) / 2)), које ће бити цели бројеви под условима одговарајућег паритета к ₄ и к _5, и ₃ и и ₆ . Испоставља се да је средина сегмента лоцирана у чвору ћелије.

Пример број 5

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

Задатак

На равном путу копају мале попречне бразде. Размак између свих жљебова је исти и једнак је О2 м. Неопходно је доказати да, без обзира на ширину жљебова, особа која хода цестом у размацима од 1 м једном ће пасти у једну од њих.

Решење

Да би се олакшало рјешење, потребно је замислити да се пут може "намотати" на круг дужине О2 метра. Испоставља се да ће се сви жљебови спојити у 2 супротна, а кораци особе ће бити приказани у облику лука једнаке 1 м. Морамо сукцесивно означити све кораке све док један од њих не буде у луку који означава жлеб, без обзира на дужину к лук (ширина утора). Наравно, очигледно је да ако је мушкарац прошао удаљеност једнаку мање од к, онда би прије или касније ушао у јарак. На крају крајева, особа не може да пређе удаљеност к ако је дужина корака мања од к. Дакле, треба да нађемо две траке, раздаљина између којих неће прећи вредност к. Да би се то постигло, било би прикладно користити принцип Дирицхлетовог. Ми ментално поделимо цео круг на лукове величине мање од к и сматрамо их ћелијама. Претпоставимо да их нема. Претпоставимо да је број корака већи од броја лукова (н + м), иако се не могу подударати два корака због ирационалности броја О2, па ће према принципу Дирицхлета барем једна од ћелија садржати више од једног корака. Пошто је дужина лука мања од к, онда ће удаљеност између корака бити мања. Стога смо пронашли кораке потребне за доказ.

Генерализација принципа

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

Пример бр. 6. Генерализација

Задатак

Правоугаоник са површином од 5 к 6 ћелија (30 ћелија), осенчан само 19. Да ли је могуће пронаћи квадрат са површином од 2 к 2 ћелије у којој ће најмање три бити обојена?

Решење

Наша фигура мора бити подељена у 6 блокова од 5 ћелија. На основу изјаве Дирицхлета, најмање 4 ћелије ће бити осликане у једној од њих (19/6 = 4). Затим у једном од квадрата са површином од 4 ћелије, смештене у једном од блокова, биће обојене најмање 3 ћелије.

Пример број 7

Класа у којој је 25 људи. Од 3 случајно одабрана ученика, два ће бити пријатељи. Неопходно је доказати да у разреду постоји школарац који има више од 11 пријатеља.

Два решења

За почетак, узимамо два школарца која нису пријатељска једни с другима (јер ако су сви били пријатељи једни са другима, у свакој тројки би било три пријатеља, а сваки ученик би био пријатељ са још 24 особе). Преосталих 23 колеге ће се дружити с једним од нас двојице, јер би иначе постојала тројка без пријатеља (а то је у супротности са првобитним стањем проблема). Испоставило се да ће један од два студента бити пријатељ са најмање 12 ученика. У овом случају, ученици су зечеви, а термини "пријатељи или не" су ћелије. Имамо 23 животиње и само 2 кавеза. Према томе, у једном од њих најмање 23/2 = 11,5, односно 12 зечева. Односно, један од 2 студента које смо изабрали биће пријатељи са најмање 12 својих колега из разреда (или чак више). Наравно, постоје и други начини за решавање проблема, али ово је један од најразумнијих и практичнијих.