i i “1151-Drnovsek-Eulerjev” — 2010/7/19 — 9:46 — page 1 — #1 i i i i i i List za mlade matematike, fizike, astronome in računalnikarje ISSN 0351-6652 Letnik 20 (1992/1993) Številka 6 Strani 346–350 Roman Drnovšek: EULERJEV PROBLEM DELITVE KONVEKSNEGA VEČ- KOTNIKA NA TRIKOTNIKE Ključne besede: matematika, geometrija, konveksni večkotniki, Euler- jev problem. Elektronska verzija: http://www.presek.si/20/1151-Drnovsek.pdf c© 1993 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. EULERJEV PROBLEM DELITVE KONVEKSNEGA VEČKOTNIKA NA TRIKOTNIKE V tem prispevku bomo odgovorili na naslednji vprašanji : 1. Na koliko različnih načinov lahko dani konveksni o-kotnik s pomoejo njegovih diagonal razdelimo na same trikotnike tako, da se začrtane diagonale v notranjosti večkotnika ne sekajo? 2. Na koliko načinov lahko izračunamo produkt n različnih faktorjev tako, da zmnožimo vedno po dva faktorja in je tako dobljeni produkt eden od faktorjev v nadaljnjem množenju? Prvo vprašanje je leta 1751 postavil švicarski matematik Leonhard Euler (1707 - 1783) , z drugim pa se j e leta 1838 prvi ukvarjal fra ncoski matematik Cata lan. Čeprav se problema na prvi pogled precej raz likujeta, pa je njuno reševa nje tesno povezano. Eulerjev problem bralcem , ki skrbno shranjujejo vse številke Preseka, ni neznan . V članku Marka Razpeta : Rezanje večkotnika na trikotnike (P 18 (1990 /91) , št. 1 , str . 12 - 16) avtor (med drugim) bralca seznani z rešitvijo in le to t udi de lno dokaže. Hkrati je v isti številki Preseka Vilko Domajnko na str . 35 zast avil Eulerjevo nalogo za nara vna števila n :::: 8 . V Eulerjevo ča st z en označimo število možnih delitev konveksnega n-kot- nika na trikotnike . Za prvih nekaj naravnih števi l lahko preprosto preštejemo vse možnosti . Tako ugotovimo, da je e3=l , e4= 2, es=5 ln e6=14 , ter slej kot prej obupamo nad to metodo določanja števil en. Leta 1758 j e Segner , s katerim se je Euler dop isoval , našel naslednjo rekurzivno zvezo za zaporedje števil { en } : n 2:3 , (1) kjer smo def inirali e2 = 1. Dokažimo to zvezo ! V ta namen si oglejmo sliko 1. 347 ; h - I Slika 1 All .11/1_1 Ogli šča konveksnega n-kotnika označimo zaporedoma s črkami Al, A2' A3, . . ., An. Pri poljubni delitvi je stranica AnAl stranica nekega trikotnika, denimo AnAlAk, kjer je k naravno število med 2 in (n - 1). Na eni strani tega trikot- nika imamo k-kotnik A lA2 .·· Ak, na drugi stani pa (n +1- k )-kotnik AkAk+ l .. . An. Prvi večkotnik la- hko razdelimo z diagonalami na tri- kotni ke na ek , drugega pa na en+l-k načinov. Ker pa poljubno delitev prvega večkotnika lahko kombiniramo s poljubno delitvijo drugega, imamo pri izbranem k natanko ek . en+l-k delitev. število k lahko zavzame poljubno naravno vrednost med 2 in (n - 1) . Ker na ta način dobimo vse možne delitve prvotnega večkotnika , od tod dobimo (1). (Bralec naj sam premisli , zakaj je ugodno definirati e2 = 1.) Zvezo (1) imenujemo Segnerjeva rekurzivna formula. Lahko se prepriča­ mo, da se sklada s prej določenimi vrednostmi e3, ea , es in e6. Dobimo pa še nekaj naslednjih členov zaporedja : e8 = e2 e7 + e3 e6 + e4 eS + eS e4 + e6 e3 + e7 e2 = 132 itd . Pri velikih n tudi s pomočjo formule (1) težko določimo število en . Da bi dobili končno formulo za en, najprej rešimo drugi problem. Začnimo z nekaj primeri : Produkt števil 2 ·3·4·5 lahko izračunamo na primer na naslednji način: 2·3 = 6, 4·5 = 20 in končno 6 ·20 = 120 . Splošno lahko produkt štirih faktorjev ab c d izračunamo na naslednjih pet načinov: [(a· b)· c] . d , [a · (b · c)] · d , (a· b). (c · d) , a·[(b·c) ·d] ln a·[b·(c ·d)] . Tu smo upoštevali vrstni red faktorjev . Kaj pa, če le ta ni predpisan? Tedaj lahko na primer množimo tudi takole a .[c ·(b ·d)] ali d .[(c .b).a] . 348 Ugotovili smo, da Catalanov problem pravzaprav vsebuje dve vprašanji : 1. Na koliko na činov lahko izračunamo produkt n različnih faktorjev , če je vrstni red faktorjev predpisan? 2. Na koliko načinov lahko izračunamo produkt n razli čnih faktorjev, če vrstni red faktorjev ni predpisan? Števili, po katerih sprašujeta vprašanji, zaporedoma zaznamujmo s Cn in z Fn - Obe števili sta v preprosti zvezi rn = Cn . n! (2) kjer je n! produkt prvih n naravnih števil. To bo brez težav, ob upošteva- nju, da je število vseh možnih razvrstitev (permutacij) n elementov enako n! , pokazal bralec sam. Kot za zaporedje števil {en} bomo tudi za zaporedji {cn} in {rn} poiskali rekurzivni zvezi, s pomočjo katerih bomo dobili formule za vsa tri zaporedja . Najprej začnimo z zaporedjem {rn} . Predstavljajmo si, da imamo za- pisanih vseh rn načinov množenja faktorjev fI , f2, .. ., fn . Tem poskusimo dodati še faktor fn+l (ki ga označimo krajše s f), tako da dobimo vseh rn+l načinov množenja faktorjev fI , f2, . .. , fn , fn+l . Naj bo P poljubno množenje produkta n faktorjev (eno izmed rn mo- žnih) . Očitno vsebuje (n - 1) produktov oblike A o B , kjer sta A in B podprodukta. Le je na primer n = 4 in P = c o[Ca ob) · d], imamo za A in B naslednje možnosti : A = a, B = b ; A = a ob, B = dinA = c, B = (a . b) od . Le uporabimo faktor f najprej enkrat kot faktor pred A, potem za A, nada lje enkrat kot faktor pred B in nato za B , dobimo iz produkta A oB naslednje štir i produkte (f oA)·B, (A·f) oB, k(f·B) ln A o(B of) . Ker to lahko storimo za vseh (n -1) podproduktov A· B v P, iz produkta P tako dobimo 4 (n - 1) produktov (n + 1) faktorjev . Poleg tega iz P dobimo tudi naslednj i dve mogoči množenj i f . P in P . f . Torej iz enega množenja produ kta n faktorjev dobimo (4n - 2) različnih množenj produkta (n + 1) faktorjev. Iz vseh t n različn ih množenj produkta n faktorjev potemtakem dobimo (4n - 2) rn različnih množenj produkta (n + 1) faktorjev. Ugotov ili 349 smo torej , da je rn+l = (4n -2)rn. (3) To je rekurzivna zveza med rn in rn+l. Da dobimo končno formulo za rn , izračunajmo prvih nekaj členov zaporedja . Očitno je r2 = 2, saj faktorje a in b lahko množimo na dva možna načina : a· bali b · a. Iz (3) potem dobimo zaporedoma r3 = 6 r2 = 2 ·6, r4 = 10 r3 = 2 ·6 ·10 in tako naprej. Končno dobimo rn = 2 ·6 · 10 . . ... (4 n - 6) . Poiščimo še rekurzivno zvezo za zaporedje {cn } . Sedaj je vrstni red faktorjev predpisan, denimo, da je to že zaporedje fI, f2, . . . , fn (n 2: 2). Vsako od Cn množenj teh faktorjev je oblike ( ). ( ), kjer prvi oklepaj vsebuje množenje prvih recimo k faktorjev fI, f2, . . . , f k, drugi pa naslednjih (n - k) faktorjev fk +! , f k +2, . . . , fn. Tukaj je k poljubno naravno število, manjše od n . V prvem oklepaju je možnih q množenj , v drugem pa Cn-k . Ker lahko množenja v prvem oklepaju poljubno kombiniramo z množenji v drugem oklepaju, je pri danem k vseh množenj Ck cn-k' Ker je k poljubno naravno število od 1 do (n - 1), končno dobimo Cn = CI Cn-l + C2 Cn- 2 + C3 Cn- 3 + ...+ Cn-l CI Z uporabo te rekurzivne zveze iz Cl =1 in C2 =1 izpeljemo C3 = CI C2 + c2 Cl = 2 , c4 = CI C3 + C2 C2 + C3 Cl = 5 itd. S pomočjo enakosti (2) dobimo tudi končno formulo za Cn I n 2 ·6 ·10 · ... · (4 n - 6) Cn = 1= I . n . n . (4) Tako je Catalanov problem v celoti rešen. Končno rešitev Eulerjevega prob- lema pa tudi že slutimo. Prvih nekaj členov zaporedij {en} in {cn} se z zamikom enega člena namreč ujema , zaporedji pa zadoščata podobnima rekurzivnima enačbama. Zato postavimo hipotezo en = Cn-l , ki jo bralec s pomočjo indukcije ter zvez (1) in (4) brez težav tudi dokaže . KonEno torej lahko zapiSemo To formulo Sc nekoliko preoblikujrno 2n-2-1.3.5.....(2n-5) en = - ( n - l)! 2"-2 - (2 n - 3)! (n - I)! .2+2 . ( n - 2)! - (2n - 3) Od tod dobimo kjar j e t = n - 2 Ztevilo trikotnikov, ki nastanejo po delitvi konveksnega n- kotnika z dirgonalami, k = 2n-3 pa j e tedaj Stevila weh stranic in diagonal. Roman Drnou3ek