——————————————————————– XVII.k¨ ot., 2.sz., 2009. okt.
Ezeregy ´ ka ´ny B´ Csa ela
1001 l´ epten-nyomon. A c´ım sz´ amn´ev, amelyr˝ol el˝osz¨ or a klasszikus irodalmi m˝ u, az Ezeregy´ej juthat esz¨ unkbe, teljesebb nev´en az Ezeregy ´ejszaka mes´ei. Mi´ert ´eppen ezeregy ´ejszaka? Ezekb˝ ol a mes´ekb˝ ol val´o j´aban nem pontosan ezeregy van (egyes kiad´asokban t¨ obb vagy kevesebb), az ezeregy” itt csak tem´erdeket jelent. ” Amikor az angol sok, a n´emet sz´ep, az orosz nagy k¨osz¨ onetet mond, az arab ezeregy k¨osz¨ onettel fejezi ki h´ al´ a j´ at. E trivi´ alis nyelv´eszeti megjegyz´es mellett cikk¨ unk v´eg´en matematikailag is megindokoljuk” Seherez´ad´e mes´einek sz´am´ at egy tov´abbi ” mes´ebe sz˝ott kombinatorikai (¨ osszesz´ aml´al´asi) feladattal. Magyar olvas´ o gondolhat els˝o kir´ alyunk koron´az´as´anak ´ev´ere is, b´ ar e k´erd´esben a t¨ ort´en´eszek v´elem´enye megoszlik: egyesek szerint a nagy t¨ ort´enelmi esem´enyre nem 1001. janu´ ar elsej´en, hanem az ezredik ´ev kar´acsony´an ker¨ ult sor. Matematikus sz´ am´ ara az 1001 term´eszetes sz´am legismertebb ´erdekess´ege, hogy 1001 = 7 · 11 · 13, aminek sz´ amos k¨ovetkezm´enye van. Egy p´elda: ha egy p´ asztor csak 13-ig tud sz´ amolni (s˝ ot: csak sz´ aml´alni!), akkor ak´ ar ezer j´osz´ agb´ol ´all´o csord´ a j´ar´ol is meg tudja ´ allap´ıtani, nem hi´anyzik-e bel˝ ole. Az elj´ar´as kiss´e hosszadalmas, de korrekt: reggel, a kar´ amb´ ol kihajtva az ´allatokat, megsz´aml´alja ˝oket hetes´evel, majd tizenegyes´evel (c´elszer˝ uen visszahajtva ˝oket a kar´amba, amin az intelligensebb j´ osz´ ag ugyancsak elcsod´ alkozik), v´eg¨ ul tizenh´ armas´aval, ´es megjegyzi a h´ arom marad´ekot. Esti behajt´ askor ugyanezt csin´alja, s ha a marad´ekok rendre megegyeznek, akkor nyugodt lehet: a csorda hi´anytalan. Ez a k´ınai marad´ekt´etelb˝ ol (annak is az egy´ertelm˝ us´egi ´ all´ıt´ as´ ab´ol) k¨ovetkezik, l´asd pl. [4], 38. o. A 11-gyel val´o oszthat´os´ ag eld¨ ont´es´enek j´ ol ismert m´odszer´et term´eszetes m´odon ´atalak´ıtva az 1001-gyel val´ o oszthat´os´ agot is meg tudjuk a´llap´ıtani (hogyan?). Ez´altal lehet˝ov´e v´alik a 7-tel ´es a 13-mal val´ o oszthat´os´ag eld¨ ont´ese is az oszt´as elv´egz´ese n´elk¨ ul. Kev´esb´e ismert t´eny, hogy 1001 o ¨tsz¨ ogsz´ am. ´Igy nevezz¨ uk az n sz´amot, ha l´etezik olyan k, hogy n pontot a t´ uloldali ´abr´ an l´athat´o m´odon el lehet helyezni
2
Cs´ ak´ any B´ela
k sz´am´ u egym´ asba skatuly´ azott szab´alyos ¨ otsz¨ogben. Az ´abra azt is mutatja, hogy ez a defin´ıci´o a n´egyzetsz´am ´es a h´ aromsz¨ ogsz´am defin´ıci´o j´at ut´anozza. Hasonl´oan az ut´obbiak sorozataihoz, az ¨ otsz¨ogsz´amok is m´asodrend˝ u sz´amtani sorozatot alkotnak (vagyis a szomsz´edos ¨ otsz¨ogsz´amok k¨ ul¨onbs´egeinek sorozata sz´amtani sorozat): 1, 5, 12, 22, . . .. Van teh´ at olyan ax2 + bx + c m´asodfok´ u f¨ uggv´eny, amelynek az i helyen felvett ´ert´eke ´eppen az i-edik ¨otsz¨ogsz´am. Innen a, b ´es c h´ arom egyenletb˝ ol ´ all´o line´aris egyenletrendszer megold´asak´ent kisz´ am´ıthat´o: a = 3/2, b = −1/2, c = 0. Eszerint az ¨otsz¨ogsz´amok az f (x) = 32 x2 − 12 x f¨ uggv´eny ´ert´ekei a pozit´ıv eg´esz sz´ amokon. Speci´ alisan, 1001 = f (26) ¨otsz¨ogsz´am. Ugyancsak szerepelteti 1001-et P´eter R´ ozsa J´ at´ek a v´egtelennel c´ım˝ u sokszor kiadott k¨onyv´eben [5]. Az e sz´ amr´ol ´ırva elmagyar´azza, hogy 1001/1000 ezredik hatv´anya mi´ert alkalmas logaritmus alapsz´am´ anak (130-132. oldal), m´asutt pedig arra vezet r´a, hogy ugyanennek a t¨ ortnek a kis kitev˝os hatv´anyait tizedest¨ ortk´ent egym´ as al´a ´ırva a Pascal-h´ aromsz¨ og els˝o sorai t˝ unnek el˝o (gondoljuk meg, h´ any sor!). Ezekben a p´eld´ akban azonban nem l´enyeges, hogy ´eppen 1001-r˝ol van sz´o; helyette 101 vagy 10001 is megtenn´e. 1001 a Pascal-h´ aromsz¨ ogben. A sz´ oban forg´ o sz´ammal egy alkalommal v´aratlanul tal´ alkoztam. Amikor a binomi´alis egy¨ utthat´ok szok´ asos t´ abl´ azat´at megismerj¨ uk, vagy bemutatjuk, rendszerint csak n´eh´any sort ´ırunk fel bel˝ole. Szeml´eltetni akarv´an, hogy a Fibonacci-sz´ amok, meg a Catalan-sz´amok hogyan olvashat´ok le a Pascal-h´ aromsz¨ ogr˝ ol* , fel´ırtam a Pascal-h´ aromsz¨ og els˝o 16 sor´at, kezdve 00 -val (ez a nulladik sor), ´es befejezve 15 ıgy kezd˝odik: 15 -tel. A 15. sor ´ 1
14 91 364 1001 2002 3001
...
* A teljess´eg kedv´e´ert: az Fn Fibonacci-sz´amokat az F1 = 1, F2 = 1, Fk+2 = Fk + Fk+1 (k ≥ 1) szab´alyok defini´alj´ak, m´ıg a valamivel kev´esb´e ismert, de ugyancsak gyakran el˝ ofordul´ o Cn Catalan-sz´amokat a C0 = 1, Ck = C0 Ck−1 + C1 Ck−2 + · · · + Ck−1 C0 (k ≥ 1) szab´alyok. A Fibonacci-sz´amok mindegyik´et egy-egy ferde egyenes vonal ment´en elhelyezked˝o ¨osszes binomi´alis egy¨ utthat´ok ¨osszege adja, m´ıg a Catalan-sz´amokat k´et alkalmas f¨ ugg˝oleges egyenes vonalon l´ev˝ o binomi´alis egy¨ utthat´ ok k¨ ul¨onbs´egei.
3 Felbukkant 1001. R´ aad´ asul, ha egy pillanatra az 1001 = 14 = A, 4 14 2002 = 14 = B, 3003 = = C jel¨ o l´ e seket haszn´ a ljuk, akkor az A, B, C 5 6 sz´amokra a k¨ovetkez˝ok is szem¨ unkbe t˝ unnek: (I) B = 2A, C = 3A. (II) B − A = C − B, azaz A, B, C sz´ amtani sorozat. (III) A + B = C. Megvizsg´aljuk, vannak-e a Pascal-h´ aromsz¨ og m´as soraiban is olyan egym´ as ut´an k¨ovetkez˝o A, B, C sz´ amok, amelyekre az (I), (II), (III) ¨osszef¨ ugg´esek valamelyike ´erv´enyes. Ez nem h´ arom f¨ uggetlen feladat, hiszen tetsz˝ oleges A, B, C sz´amokra (I) pontosan akkor teljes¨ ul, ha (II) ´es (III) teljes¨ ul. Ez´ert elegend˝o lenne a (II) ´es (III) ¨osszef¨ ugg´esekkel foglalkozni. Mivel azonban (I) vizsg´alata sokkal egyszer˝ ubb, vele fogunk kezdeni. Bemeleg´ıt´esk´ent pedig megn´ezz¨ uk, h´ anyszor fordul el˝o 1001 a Pascal-h´ aromsz¨ ogben. Amint l´attuk, 14 = 14 = 1001, tov´abb´a 1001 = 1001 = 1001. 4 10 1 1000 Megmutatjuk, hogy m´ a s binomi´ a lis egy¨ u tthat´ o k ´ e rt´ e ke nem lehet 1001. Ha n ≥ 4, akkor n4 < n+1 . Ez´ e rt, ha egy, a l´ a tottakt´ o l k¨ u l¨ o nb¨ o z˝ o (n, k) p´ a rra 4 n = 1001, akkor k ≤ 3. Ha k = 2, a binomi´alis egy¨ utthat´ot kifejtve az k n2 − n − 2002 = 0 egyenletet kapjuk, s ennek nincs eg´esz megold´asa, mert a megold´ok´eplet alkalmaz´asakor a n´egyzetgy¨okjel alatt nem n´egyzetsz´am ´all. Ha pedig k = 3, hasonl´ oan az n(n − 1)(n − 2) = 6006 egyenlethez jutunk. Ezt kiel´eg´ıt˝o eg´esz n sem l´etezik; a bizony´ıt´ ashoz csak a term´eszetes sz´amok pr´ımekre bont´ as´anak egy´ertelm˝ us´eg´et kell haszn´alnunk. A tov´abbiakhoz is csak elemi matematikai ismeretekre lesz sz¨ uks´eg¨ unk: a pithagoraszi sz´ amh´ armasok el˝ oa´ll´ıt´ as´ ara*, valamint a Fibonacci- ´es a Lucassz´amokra vonatkoz´o n´eh´any egyszer˝ u¨ osszef¨ ugg´esre. Az ut´obbiak igazol´as´at majd r¨oviden v´azoljuk. I. 1001 = 14 am a Pascal-h´ aromsz¨ ogben, amelyt˝ ol egy hellyel 4 az egyetlen sz´ jobbra a k´etszerese, k´et hellyel jobbra a h´ aromszorosa a ´ll. n n n Az ´all´ıt´ast ´ıgy is kimondhatjuk: Ha nk = 2 k−1 ´es k+1 = 3 k−1 , akkor n n = 14, k = 5 ´es k−1 = 1001. n Az nk = 2 k−1 egyenletb˝ ol azonnal ad´odik a vele ekvivalens n = 3k − 1, teh´at v´egtelen sok olyan binomi´alis egy¨ utthat´ovan, amely k´etszerese a sor´aban ˝ot k¨ozvetlen¨ ul megel˝oz˝onek, s ezek ´eppen a 3k−1 sz´amok minden k pozit´ıv eg´eszre. k n n Tegy¨ uk fel, hogy k+1 = 3 k−1 is teljes¨ ul. Ez az n2 − (2k − 1)n − (2k 2 + 4k) = 0 egyenlett´e ´ırhat´ o´ at, ahonnan a megold´ok´eplettel * Ha a, b, c relat´ıv pr´ım sz´ amok, amelyekre a2 + b2 = c2 , ahol a ´es b k¨oz¨ ul a a p´ aratlan, akkor l´eteznek olyan u ´es v relat´ıv pr´ım p´ aratlan sz´amok, hogy a = uv, b = (u2 − v 2 )/2, c = (u2 + v 2 )/2.
4
Cs´ ak´ any B´ela
n=
2k − 1 +
√ 12k 2 + 12k + 1 = 3k − 1 2
ad´odik (a gy¨ okmennyis´eget csak pozit´ıv el˝o jellel vett¨ uk figyelembe, mert csak pozit´ıv megold´ast keres¨ unk). A k-ra ilyen m´odon nyert egyenlet egyetlen pozit´ıv megold´asa k = 5, innen pedig n = 14. Az I. ¨osszef¨ ugg´es teh´at a Pascalh´ aromsz¨ ognek csak egyetlen hely´en, az 1001, 2002, 3003 sz´amokra teljes¨ ul. II. A Pascal-h´ aromsz¨ og v´egtelen sok sor´ aban van egy-egy olyan szomsz´edos sz´ amh´ armas, amely pozit´ ul¨ onbs´eg˝ u sz´ amtani sorozatot alkot. ıv k¨ n n Legyenek k−1 , nk , k+1 ilyen sz´ amok. Akkor (1)
n n n n − = − , k k−1 k+1 k
ami az n2 −(4k+1)n+(4k 2 −2) = 0 egyenlett´e ´ırhat´ o ´at. Ennek az eg´esz megold´asai: n = 4k + 1 ± 2,
√ 8k + 9
ahol 8k + 9 n´egyzetsz´am. Gondoljuk meg, hogy 8k + 9 = (2t + 1)2 akkor ´es csak akkor, ha k = t(t + 1)/2 − 1. Ez´ert t minden egyn´el nagyobb ´ert´ek´ere kapunk egy olyan pozit´ıv k-t, amelyre 8k + 9 n´egyzetsz´am, a megold´ok´epletb˝ ol pedig az n = (t + 1)2 − 2 ´es n = t2 − 2 ´ert´ekeket. A k + 1 ≤ n hallgat´olagos feltev´es miatt, ami csup´ an azt fejezi ki, hogy keresett sz´amtani sorozatainknak benne kell lenni¨ uk a Pascal-h´ aromsz¨ ogben , n = t2 − 2 csak 2-n´el nagyobb t-re adja feladatunk megold´as´at. Nyert¨ uk, hogy (t + 1)2 − 2 (t = 2, 3, . . .), t(t + 1)/2 − 1
tov´abb´a
t2 − 2 (t = 3, 4, . . .) t(t + 1)/2 − 1 az (1) egyenletet kiel´eg´ıt˝ o nk binomi´alis egy¨ utthat´ok. Az el˝obbiek a Pascalh´ aromsz¨ og k¨oz´epvonal´at´ol balra vannak, ´es ez´ert pozit´ıv k¨ ul¨onbs´eg˝ u sz´amtani (t+1)2 −2 sorozatok k¨oz´eps˝ o elemei. Az ut´obbiakat pedig (t+1)(t+2)/2−1 (t = 2, 3, . . .) alakban is ´ırhatjuk, amib˝ ol l´athat´o, hogy ezek az el˝obbiek t¨ uk¨ork´epei a Pascalh´ aromsz¨ og k¨oz´epvonal´ara vonatkoz´oan. A t param´eter 2,3,4,5 ´ert´ekeire a k¨ovetkez˝o
5 pozit´ıv k¨ ul¨onbs´eg˝ u sz´ amtani sorozatokat kapjuk, amelyek k¨ozep´en rendre a 72 , 14 23 34 alis egy¨ utthat´ ok ´ allnak: 5 , 9 , 14 binomi´ 7, 21, 35 1001, 2002, 3003 490314, 817190, 1144066 927983760, 1391975640, 1855967520
Az alkalmas
n k
sz´ amok t n¨ ovel´es´evel igen gyorsan n˝ onek, pl. ha t = 10,
n 119 = = 29279545134853594455373617608122941. k 54 Gondolatmenet¨ unkb˝ ol l´atszik, hogy r¨ogz´ıtett n-hez legfeljebb egy olyan k tartozik, amelyre (n, k) kiel´eg´ıti (1)-et. Ebb˝ol k¨ovetkezik, hogy a Pascalh´ aromsz¨ og egy sor´anak n´egy egym´ as melletti eleme nem alkothat sz´amtani soroza tot. Ezt szeml´eletes meggondol´as is mutatja: A (0, n0 ), (1, n1 ), . . . , (k, nk ), . . . . . . , (n, nn ) pontok harangg¨orb´en helyezkednek el*, m´asr´eszt, ha a0 , a1 , a2 , a3 sz´amtani sorozat, akkor az(i, a0 ), (i + 1, a1 ), (i + 2, a2 ), (i + 3, a3 ) pontok egy egyenesen vannak. Harangg¨orb´et egyenes azonban nem metszhet n´egy helyen. III. A Pascal-h´ aromsz¨ og v´egtelen sok sor´ aban van k´et olyan szomsz´edos sz´ am, amelyek o ¨sszege a t˝ o l¨ u k k¨ o zvetlen¨ u l jobbra a ´ ll´ o sz´ a m. n Az ilyen k−1 ´es nk sz´ amokra (2)
n n n + = , k−1 k k+1
ami ekvivalens az n2 − 3kn + (k 2 − 2k − 1) = 0 egyenlettel. Azt kell bel´atnunk, hogy v´egtelen sok (n, k) sz´ amp´ arra
(3)
n=
3k ±
p k 2 + (2k + 2)2 . 2
Ha (n, k) ilyen sz´ amp´ ar, akkor a gy¨ okjel alatti sz´am n´egyzetsz´am; jel¨olje p2 . L´ atjuk, hogy (k, 2k + 2, p) pithagoraszi sz´ amh´ armas. Tegy¨ uk fel, hogy k p´ aratlan. Akkor k, 2k +2 ´es p relat´ıv pr´ımek, l´eteznek teh´ at olyan relat´ıv pr´ım p´ aratlan u, v sz´amok, hogy * nk a v´arhat´ o ´ert´eke az n magass´ ag´ u Galton-deszk´an legur´ıtott 2n sz´am´ u goly´ o k¨oz¨ ul a k-adik rekeszbe ker¨ ul˝o goly´ ok sz´am´ anak; l´asd pl. [1], 182-183. o.
6
Cs´ ak´ any B´ela
(4)
k = uv,
2k + 2 =
u2 − v 2 , 2
p=
u2 + v 2 . 2
Innen u2 − v 2 = 4uv + 4.
(5)
√ A m´asodfok´ u egyenlet megold´ok´eplete szerint v = −2u + 5u2 − 4 (v pozit´ıv, ´ıgy a m´asodik tagot csak + el˝ o jellel vessz¨ uk figyelembe). A gy¨ okjel alatt itt is egy q 2 n´egyzetsz´am ´ all, amelyre teh´ at teljes¨ ul q 2 − 5x2 = −4.
(6)
Most kis kit´er˝ ot tesz¨ unk. Lucas-sz´ amoknak nevezz¨ uk az 1, 3, 4, 7, 11, . . . sz´amokat. Jel¨ol´es¨ uk: L1 , L2 , . . .; form´alis defin´ıci´o juk csak abban k¨ ul¨onb¨ ozik a Fibonacci-sz´amok´et´ol, hogy a m´asodik Lucas-sz´am nem 1, hanem 3. Ismerked´es c´elj´ab´ol egym´ as al´ a ´ırjuk az els˝o t´ız Fibonacci-sz´amot ´es Lucas-sz´amot: i Fi Li
1 2 3 4 5 6 7 8 9 10 1 1 2 3 5 8 13 21 34 55 1 3 4 7 11 18 29 47 76 123
Megfigyelj¨ uk ´es teljes indukci´ oval be is l´athatjuk, hogy i > 1-re Li = Fi−1 + Fi+1 . (Ha nulladik Fibonacci-sz´ amnak a 0-t tekintj¨ uk, akkor ez i = 1-re is igaz.) M´ asik alapvet˝o ¨osszef¨ ugg´es a Fibonacci-sz´ amok ´es a Lucas-sz´amok k¨oz¨ott: minden pozit´ıv eg´esz i-re
(7)
L2i − 5Fi2 = (−1)i · 4.
Az el˝oz˝o azonoss´ agot ´es a Fibonacci-sz´ amok defin´ıci´o j´at haszn´alva (7) az ugyancsak nevezetes (8)
Fi−1 Fi+1 − Fi2 = (−1)n
o¨sszef¨ ugg´ess´e alak´ıthat´ o´ at*, az ut´obbit pedig (csup´an a Fibonacci-sz´amok defin´ıci´o j´anak t¨ obbsz¨ori alkalmaz´as´ aval) teljes indukci´oval igazolhatjuk. * A (8) azonoss´ ag a 17. sz´ azadi nagy csillag´asz Cassini nev´ehez f˝ uz˝odik.
7 A (6) ´es (7) egyenleteket ¨ osszehasonl´ıtva l´atjuk, hogy q = Li ,
u = Fi
megold´asai (6)-nak, valah´anyszor i ´es Fi egyidej˝ uleg p´ aratlan sz´am. Ekkor a megold´ok´epletb˝ ol v = −2Fi + Ln = Fi−3 . A (8) azonoss´agot alkalmazva ad´odik, hogy az ´ıgy nyert u, v kiel´eg´ıti (5)-¨ot. Bel˝ol¨ uk (4) szerint k´epezhet˝o k = Fi Fi−3 ´es 2 2 p = (Fi + Fi−3 )/2. Most (3) alapj´ an meghat´arozhatjuk a k-val egy¨ utt alkalmas p´ art alkot´o n-et. Nem neh´ez gyakorlat a kapott n ´es k sz´amokat a bar´ ats´ agos n = Fi−1 Fi − 1, k = Fi−2 Fi−1 − 1 alakra hozni; ehhez is csak a Fibonacci-sz´amok defin´ıci´o j´at ´es a (8) azonoss´ agot kell haszn´alnunk. Mivel v´egtelen sok olyan p´ aratlan i van, amelyre Fi is p´ aratlan, tov´abb´a k¨ ul¨onb¨ oz˝o i-kre k¨ ul¨onb¨ oz˝o (n, k) p´ arokat kapunk, a III. ´ all´ıt´ ast bel´ attuk. R´ aad´ ask´ent az is kider¨ ult, hogy a (2)-t kiel´eg´ıt˝o (n, k) p´ arok k¨oz¨ott v´egtelen sok olyan is van, amelyben k p´ aratlan. Hasonl´oan vizsg´alhat´ o a p´ aros k esete; ezt nem r´eszletezz¨ uk. Az eredm´eny is hasonl´ o: minden olyan egyn´el nagyobb p´ aratlan i-re, melyre Fi ´es Fi+1 is p´ aratlan, n = Fi+1 Fi+2 − 1, k = Fi Fi+1 − 1. Figyelembe v´eve, hogy Fibonacci-sz´am pontosan akkor p´ aros, ha sorsz´ama oszthat´o 3-mal, a k´et esetre kapott megold´asainkat t¨ om¨ oren ´ıgy ´ırhatjuk le: n Fi Fi+1 − 1 = (i = 4, 6, 8, . . .). k Fi−1 Fi − 1 Ez a sorozat m´eg gyorsabban n˝ o, mint az, amellyel II.-t igazoltuk. Ha i = 4, . . . , 12, rendre a k¨ovetkez˝o binomi´alis egy¨ utthat´ okat kapjuk:
14 , 5
103 , 39
713 , 272
4894 , 1869
33551 . 12815
K¨oz¨ ul¨ uk az utols´ o t´ızes sz´ amrendszerben 9688 sz´amjeggyel ´ırhat´ o fel. (2)-vel ekvivalens egyenletet oldott meg D. A. Lind [2] ´es David Singmaster* [6], tov´abbi sz´ amelm´eleti ismeretek felhaszn´al´as´aval. Singmasternek az t˝ unt fel, hogy 3003 legal´ abb hat k¨ ul¨onb¨ oz˝o m´odon ´ırhat´ fel binomi´alis egy¨ utt on+1 n hat´ok´ent (mivel a (2) egyenlet azt is jelenti, hogy k+1 = k ), ´es cikke f˝oeredm´eny´enek tekintette, hogy v´egtelen sok term´eszetes sz´amnak van meg ez a tulajdons´ aga. Azt is meg´allap´ıtotta, hogy 3003 pontosan nyolc helyen szerepel a Pascal-h´ aromsz¨ ogben. Ezt mi is bel´ athatjuk, ahhoz hasonl´ oan, ahogyan 1001 el˝ofordul´asainak sz´ am´ at meghat´aroztuk. * A Rubik-kocka jeles szak´ert˝ o je ´es n´epszer˝ us´ıt˝o je.
8
Cs´ ak´ any B´ela
1001 a szerves k´ emi´ aban. T´erj¨ unk vissza az Ezeregy ´ejszaka mes´eihez. Amikor a sz´eps´eges Seherez´ad´e els˝o csod´ alatos mes´ej´et befejezte, a kegyetlen szult´ an Sahri´ar – a t¨ ort´enet k¨ozismert v´altozat´ at´ol elt´er˝oen – azonnal meg´erezte, hogy leg´ ujabb hitves´et sohasem tudn´ a elveszejteni. Sz´ol´ıtotta h´ at az u ¨ gyeletes eunuchot, s el˝ohozatott egy nemkev´esb´e csod´ alatos nyakl´ancot, amelyre 14 pomp´ as dr´agak˝o, m´egpedig kilenc rubin ´es ¨ ot zaf´ır volt felf˝ uzve. T˝ole szokatlan gy¨ ong´eds´eggel kapcsolta fel Seherez´ad´e nyak´ ara, ´es ´ıgy sz´ olt: Valah´anyszor u ´ jabb gy¨ ony¨or˝ us´eges ” mes´evel andal´ıtasz el, mindannyiszor ugyanennyi rubin- ´es zaf´ırk˝ob˝ol k´esz´ıtett nyakl´anccal jutalmazlak majd meg, ´es k¨ ul¨onb¨ oz˝o mes´ek´ert k¨ ul¨onb¨ oz˝ok´eppen ¨osszerakott nyakl´anc j´ ar!” Ennyi volt a cikk elej´en ´ıg´ert mese. A kombinatorikai feladat: h´ any ´ejszak´an ´at tudta teljes´ıteni ´ıg´eret´et a m´erhetetlen kincsek f¨ol¨ott rendelkez˝ o an? szult´ 14 Elsiethetj¨ uk a v´alaszt: a k´ek zaf´ırk¨ ovek hely´et a 14 dr´agak˝o k¨oz¨ott 5 k¨ ul¨onb¨ oz˝o m´odon jel¨olhetj¨ uk ki, ´es ez a sz´ am 2002, ami j´o ismer˝os¨ unk ugyan, m´egis gyan´ us, hiszen kerekebb lenne a t¨ ort´enet, ha az der¨ ulne ki, hogy a megold´as 1001. Seg´ıts¨ unk magunkon: n´ezz¨ uk meg az al´ abbi k´et nyakl´ancot:
Ezek nem k¨ ul¨onb¨ oz˝ok! Az als´ot megford´ıtva (azaz k´et v´eg´et megcser´elve) ´eppen a fels˝ot kapjuk. Eszerint a zaf´ırk¨ ovek ¨ ot hely´enek kiv´ alaszt´asakor k´etf´elek´eppen is megkapunk minden lehets´eges nyakl´ancot. (Tekints¨ uk a k¨ovetkez˝o ´all´ıt´ast: a ” nyakl´anc megford´ıt´ asa az ¨ osszes nyakl´ancok halmaz´anak olyan transzform´ aci´ o ja, amelynek nincs fixpontja”, ´es gondoljuk meg, hogy ez akkor ´es csak akkor igaz, ha az ¨osszes dr´agak¨ ovek sz´ ama p´ aros, a rubin- ´es zaf´ırk¨ovek sz´ama pedig p´ aratlan.) A helyes v´alasz teh´ at 1001. Megoldottunk egy sz´ınezett l´anc-gr´afok ¨osszesz´ aml´al´as´ara vonatkoz´o apr´ o feladatot. Ezt ´ altal´ anosabban, 14 ´es 5 helyett tetsz˝ oleges n-re ´es k-ra (k ≤ n) megoldotta Szima Lozanics szerb k´emiatud´os* 1897-ben [!] megjelent dolgozat´ aban [3], amely a paraffinok izomerjeinek ¨ osszesz´ aml´al´as´ar´ol sz´ol. A paraffinok (vagy alk´anok) Cn H2n+2 ¨ osszegk´eplet˝ u (m´ as sz´ oval tapasztalati k´eplet˝ u) sz´enhidrog´enek. Szerkezeti k´eplet¨ ukre p´eld´ ak:
* Nev´et angol ´es n´emet sz¨ ovegekben Lozani´c ill. Losanitsch alakban ´ırj´ ak.
9 Mindkett˝ o k´eplete C8 H18 , m´ıg azonban az els˝oben a nyolc sz´enatom egyetlen l´ancot (´ un. egyenes sz´enl´ ancot) alkot, a m´asodikban csak hat atomos egyenes sz´enl´ancot tal´ alunk, amelyhez k´et helyen hidrog´enatom helyett egy-egy CH3 k´eplet˝ u metilcsoport kapcsol´ odik. Itt a sz´enatomok (mint pontok) a k¨ozt¨ uk l´ev˝ o egyszeres k´emiai k¨ot´esekkel (mint ´elekkel) szaknyelven el´agaz´o sz´enl´ ancot, matematikai nyelven f´at k´epeznek, amelyben minden elem foksz´ ama legfeljebb 4. Az els˝o vegy¨ uletet norm´ alis okt´annak, a m´asodikat izo-okt´annak (vagy az okt´an egyik izomerj´enek) nevezz¨ uk, mivel azonban az okt´annak sok m´ as izomerje is van (ti. nyolc sz´enatom a k¨ozt¨ uk l´ev˝ o egyszeres k´emiai k¨ot´esekkel nem csak a fenti k´et m´odon alkothat f´ at), a bemutatott izo-okt´annak olyan nevet is adnak a vegy´eszek, amelyb˝ ol kider¨ ul a szerkezeti k´eplete: 2, 4-dimetilhex´an. Itt 2 ´es 4 azt adja meg, h´ anyadik sz´enatomhoz kapcsol´ od´ o hidrog´enatomot helyettes´ıti metilcsoport, a hex´ an n´ev pedig azt mutatja, hogy megnevezett izo-okt´an-molekul´ank a hat atomos egyenes sz´enl´ anc´ u norm´ alis paraffinmolekula m´o dos´ıt´as´aval keletkezett. M´ asik p´elda a 2, 2-dimetilprop´ an; mivel a norm´alis prop´ an egyenes sz´enl´ anca h´ arom sz´enatomb´ ol ´ all, a n´evb˝ ol kivil´ aglik, hogy ennek a paraffinnak a sz´enf´a j´aban” van ” 4 foksz´ am´ u atom. T¨obbek k¨oz¨ott besz´elhetn´enk pl. 3, 5-dimetilhex´anr´ ol is, de nem besz´el¨ unk, mert ennek a sz´enf´a ja izomorf a 2, 4-dimetilhex´an´eval (ti. abba ´atford´ıthat´o”), ” ´es ez´ert a k´et anyag k´emiailag egyform´ an viselkedik. Nem besz´el¨ unk tov´abb´a 1, 3dimetilhex´anr´ ol sem, mert ez m´ar 4-metilhept´an lenne; m´as sz´oval, metilcsoportot egyenes sz´enl´ anc sz´els˝o atomjaihoz nem kapcsolunk. Ha teh´at ¨ossze akarjuk sz´aml´alni a lehets´eges dimetilhex´ anokat, egyr´eszt meg kell ´allap´ıtnunk, h´ any k¨ ul¨onb¨ oz˝o m´odon v´alaszthatunk ki kett˝ ot a hat atomb´ ol ´all´o norm´alis sz´enl´ anc n´egy bels˝o atomja k¨oz¨ ul, nem tekintve k¨ ul¨onb¨ oz˝onek az olyan kiv´ alaszt´asokat, amelyek egym´ as t¨ uk¨ork´epei a l´anc k¨oz´eppontj´ ara vonatkoz´oan, ´es h´ any helyen lehet 4 foksz´ am´ u sz´enatom a dimetilhex´ an sz´enf´a j´ aban. L´ atjuk, hogy a keresett sz´am 4 + 2 = 6. Lozanics – a k¨ ul¨onb¨ oz˝o paraffinok sz´am´ ara vonatkoz´o sz´amos eredm´enye k¨oz¨ott – meghat´arozta az n + 2 atomos egyenes sz´enl´ ancb´ ol k sz´am´ u k¨ ul¨onb¨ oz˝o bels˝o sz´enatomhoz kapcsol´ od´ o hidrog´enatom metilcsoporttal val´o helyettes´ıt´ese ´altal keletkez˝o paraffinok sz´ am´ at tetsz˝ oleges n(≥ 0)-ra ´es k = 0, 1, . . . , n-re. Ezeket a sz´amokat a Pascal-h´ aromsz¨ ogh¨ oz hasonl´ o t´ abl´ azatba foglalta, amelyet az ut´okor Lozanics-h´ aromsz¨ ognek nevez. N´eh´any sor´at itt l´atjuk, kiemelve a p´ aros sorsz´am´ u sorok p´ aratlan sorsz´am´ u elemeit:
10
Cs´ ak´ any B´ela
A sorokat ´es elemeiket a Lozanics-h´ aromsz¨ ogben is 0-val kezdve sz´amozzuk. Az n-edik sor k-adik elem´et itt L(n, k) fogja jel¨olni; ez a sz´am azt mondja meg, h´ any k¨ ul¨onb¨ oz˝o m´odon sz´ armaztathatunk n + 2 atomos egyenes sz´enl´ anc´ u paraffinb´ ol u ´ j paraffint a sz´enl´ anc k¨ ul¨onb¨ oz˝o bels˝o atomjaihoz kapcsol´od´ o k sz´am´ u hidrog´enatom metilcsoporttal val´ o helyettes´ıt´ese u ´tj´an. Kicsit absztraktabban: L(n, k) a sz´ama egy n elem˝ u l´anc p´ aronk´ent nemekvivalens k elem˝ u r´eszhalmazainak, ha ekvivalensnek azokat a r´eszhalmazokat tekintj¨ uk, amelyek egym´ as t¨ uk¨ork´epei a l´anc k¨oz´eppontj´ ara vonatkoz´oan. Speci´ alisan, L(14, 5) = 1001, hiszen a mesebeli nyakl´ancok ¨ osszesz´ aml´al´ asa ugyanaz, mint a 16 – (´es ´ıgy 14 bels˝o) – sz´enatomot tartalmaz´ o egyenes sz´enl´ anc´ u olyan paraffinok´e, melyekben ¨ot hidrog´enatomot helyettes´ıt metilcsoport. A szerkezeti k´epletet is jelz˝ o terminol´ogi´ at haszn´alva: 1001 a k¨ ul¨onb¨ oz˝o olyan pentametilhexadek´anok sz´ama, amelyek sz´enf´a j´anak pontjai legfeljebb harmadfok´ uak (vagy, a szerves k´emikusok nyelv´en, amelyekben nincs kvaterner sz´enatom). A Lozanics-h´ aromsz¨ og sz´ amait k¨onny˝ u fel´ırni. M´ ar kider¨ ult, hogy ha n p´ aros ´es k p´ aratlan, akkor 2L(n, k) = nk . Ha k = 0 vagy k = n, akkor nyilv´anval´oan L(n, k) = 1. A h´ atramaradt esetben pedig a Pascal-h´ aromsz¨ og k´epz´esi szab´aly´ahoz hasonl´ oan L(n, k) = L(n− 1, k − 1)+ L(n− 1, k). A bizony´ıt´as is hasonl´ o: kijel¨ olj¨ uk az n elem˝ u l´anc k¨oz´eps˝ o (p´aros n eset´en egyik k¨oz´eps˝ o) elem´et, s L(n − 1, k − 1) lesz a kijel¨ olt elemet tartalmaz´ o p´ aronk´ent nemekvivalens k elem˝ u r´eszhalmazok sz´ama, m´ıg L(n − 1, k) a kijel¨ olt elemet nem tartalmaz´ ok´e. Befejez´es¨ ul k´et feladat: 1. H´ any k¨ ul¨onb¨ oz˝o pentametilhexadek´an l´etezik? 2. H´ any k¨ ul¨onb¨ oz˝o olyan nyakl´anc l´etezik, amelynek 18 ´ekk¨ove k¨oz¨ ul ¨ot rubin, a t¨ obbi zaf´ır, ´es mik¨ ozben Sahri´ ar felemeli, nincsenek rajta szomsz´edos rubink¨ovek? Irodalom [1] Cs´ak´ any B´ela, Kis matematikai szint´ √ ezis, Polygon, 2003. [2] D. A. Lind, The quadratic field Q( 5) and a certain Diophantine equation, The Fibonacci Quarterly, 6. k¨otet (1968), 86-93. [3] S. M. Losanitsch, Die Isomerie-Arten bei den Homologen der ParaffinReihe, Chemische Berichte, 30. k¨otet (1897), 1917-1926. [4] Megyesi L´ aszl´ o, Bevezet´es a sz´ amelm´eletbe, Polygon, 1997. [5] P´eter R´ ozsa, J´ at´ek a v´egtelennel, 7. kiad´as, Typotex, 1999. [6] D. Singmaster, Repeated binomial coefficients and Fibonacci numbers, The Fibonacci Quarterly, 13. k¨otet (1975), 295-298.
