i i “826-Milosevic-Dirichletov” — 2010/5/27 — 10:17 — page 1 — #1 i i i i i i List za mlade matematike, fizike, astronome in računalnikarje ISSN 0351-6652 Letnik 14 (1986/1987) Številka 2 Strani 110–111 Dragoljub M. Miloševíc, prevod Peter Šemrl: DIRICHLETOV PRINCIP Ključne besede: matematika, razvedrilo. Elektronska verzija: http://www.presek.si/14/826-Milosevic-Semrl-Dirichlet.pdf c© 1986 Društvo matematikov, fizikov in astronomov Slovenije c© 2010 DMFA – založništvo Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali posameznih delov brez poprejšnjega dovoljenja založnika ni dovo- ljeno. DIRICHLETOV PRINCIP Pri reševanju raznih problemskih nalog, še posebej pri tistih, ki zahtevajo dokaz obstoja objektov z neko določeno lastnostjo , nam pogosto pomaga Dirichletov princip, imenovan po nemškem matematiku P.G.L. Dirichletu (1805 - 1859). Ta preprosti princip ima več popularnih imen, na primer: "problem zajčkov in kletk", "problem škatel in kroglic" in podobno. Lahko ga formuliramo ta- kole: Če je v n škatlah spravljeno več kot n kroglic, potem mora vsaj ena škatla vse- bovati več kot eno kroglico. Z nekaj primeri bomo sedaj ilustrirali uporabo tega principa. ZGLED 1. Dokažimo, da sta med desetimi slučajno izbranimi naravnimi števili vsaj dve taki števili, da je njuna razlika deljiva z 9. REŠiTEV. Pri deljenju naravnega števila z 9 je lahko ostanek eno izmed števil: O, 1, 2, ..., 7, 8. Ker imamo 10 števil in s tem tudi 10 ostankov, ki pa lahko zavzamejo največ 9 različnih vrednosti, nam Dirichletov princip pove, da imata vsaj dve med desetimi izbranimi števili isti ostanek pri deljenju z 9. Označimo ti dve števili z ni in n2 in s črko r njun skupni ostanek pri deljenju z 9. Tedaj imamo ni = 9k +r in n2 = 9rn + r kjer sta m in k naravni števili. Zato je njuna razlika ni - n2 =9(k - mdeljiva z 9. Dokaz je s tem končan. ZGLED 2. V razredu je 20 učencev. Pri šolski nalogi iz matematike nihče od učencev ni napravil več kot 5 napak. Dokažimo, da so vsaj štirje učenci napra- vili isto število napak. REŠiTEV. Razvrstimo učence v "škatle", tako da v isto "škatlo" spravimo učence, ki so napravili enako število napak. Ker so učenci napravili O, 1,2,3, 4 ali 5 napak , je takih "škatel" šest. V za nas najbolj neugodnem primeru bi bi- li v vsaki "škatli" po trije učenci, torej dva ostaneta (20=6.3+2). Na osnovi Dirichletovega principa obstaja "škatla", v kateri so vsaj štirje učenci, kar je bi- lo potrebno dokazati. ZGLED 3. V pravilnem dvanajstkotniku pobarvamo nekatere izmed diagonal. Dokažimo, da obstajata vsaj dve oglišči, v katerih se končuje enako število po- barvanih diagonoal. 110 RE~ITEV. V vsakem ogl& re konCuje 9 diagonal. Zam imwo v vlakem ogligOu 10 rnofnorti xa h i l o obatvanih diagonal. OglM ('kroglk*') pa je 12. Po Diriehlmvem pdnclpu obrtejata dve oglWi z istim M 1 o m ob8rvanih diagonal. ZGLED 4. V kvadratu s rtaanico 1 je poljubno ramdhnih 51 toEk. Ali je mo2- no mal njimi poiski tri boEke, ki jih mkrii kmg s polmemm 1/77 RESITEV. Dani kvadrat v oblikl Eshovnbce razdelhno na 25 kvsdretov s otrani- oo 1/6. DMchletw princip nam pow, da obstaja kvadrat, ki dcupaj s wojimi strenlcmni vwbuje vrqj 3 toEke. Ker je 2/7 M j e od &/5, Iahko fa M r a t po- krijerno s krogom polmra 1/7. b vsm je Dlrichlstov princip r mojo pmpmmortjo in ~Cinkovitostjo W, se lahko -jno lotlte d a n j a naslednjih problemw. 1. Jugoslavlja ima manj kot 23 rnilkjonar pmbiwkev in ved! kot 7000 nrcelij. Dak&b, da imata vraJ dve wlji enako k#NIlo pmbivelcev. 2. Koliko najmanj naremih MI je pafmbno vzeti, da bi med njimi gotaro obstqjal2 dve hwili, W I h razlika je ddjiva s 57 3. V hadretu c m a n b 1 je izkanih 101 e k , tlko da nobena trojica kmed wh W k M Mi na i s t i pramid. D~kuUm trikotnka z ogtwi v treh bmed tab toCk in s podlno, manjjo od 0,Ol. 4. V omari .ham 4 para rfrvh in 4 pare 6mih M j w . Kolilro najrnenj lkvljev ie potrebno na depo vzed iz omrra, da bi imdi vsaj en par 5evljev lrte barvef D m # & M. MiMwvf0 Prevedel ~ b w r k l