![]() |
Dinnyék rendezése |
A dinnyeárusnak az a mániája, hogy görögdinnyéit, amelyek tökéletesen gömb alakúak, a vízszintes síklapú piaci kőasztalon az asztal hosszában egyenes sorba rakja úgy, hogy a sor belsejében mindegyik dinnye két szomszédjához ér hozzá, és azok a pontok, ahol a dinnyék az asztallaphoz érnek, egy egyenesen helyezkednek el.
Egy reggel, amikor kocsijában tizenegy gömb alakú dinnyével
megérkezik a piacra, és még nem rakta ki azokat a maga módján, odamegy
hozzá a piaci díjbeszedő és sorra megméri a dinnyék átmérőjét,
amelyeket a következőknek talál: d1=16 cm,
d2=18 cm, d3=22 cm,
d4=26 cm, d5=28 cm,
d6=30 cm, d7=34 cm,
d8=36 cm, d9=38 cm,
d10=40 cm,
d11=42 cm. Ezeket összeadja és közli, hogy az
árusnak az átmérők összege, vagyis 330 cm után kell helyfoglalási
díjat fizetnie. A dinnyeárus ezt nem fogadja el, mondván, hogy ő
a dinnyéit az ő mániája szerint ennél rövidebb sorba tudja rendezni az
asztalon. Számítsa ki a díjbeszedő a dinnyék méretének ismeretében,
hogy milyen hosszú lesz a belőlük összeállítható legrövidebb
dinnyesor, s akkor majd annyiért fizet. Erre a díjbeszedő azt mondja,
látom, szereti a matematikát; nos jól van, én kiszámítom a legrövidebb
dinnyesor hosszát, vagyis annak a síkbeli alakzatnak a kombinatorikus
geometriai átmérőjét, amely a megfelelően elrendezett és egymást
érintő dinnyék asztalra vett merőleges vetületeinek mint halmazoknak
az uniója, ha ön viszont igazolja, hogy ez a hosszúság adott
r1ler2ler3...
rn-1lern sugarú n
darab dinnye esetén akkor a legkisebb, ha a
D=(√rk1−√rk2)2+(√rk2−√rk3)2+(√rk3−√rk4)2+
+(√rk4−√rk5)2+⋯+(√rkn−1−√rkn)2
összeg a legnagyobb; ahol tehát rk1,rk2,rk3,...,rkn-1,rkn az egyes, egymással érintkező dinnyék gömbsugarát jelöli, és ezen belül k1,k2,k3,...,kn-1,kn indexek az 1,2,3,...,n-1,n számok egyik, a minimumot előállító, megfelelő permutációját jelentik. Segítsünk nekik!
Megoldás: A dinnyesor két szomszédos dinnyéjére az ábra szerint igaz, hogy az asztalon lévő érintkezési pontjaik távolsága AB=x=2√ab, ahol a és b a két gömb sugara. Ennek alapján a feladatban meghatározott dinnyesor hossza:
L=rl1+2√rl1rl2+2√rl2rl3+2√rl3rl4+2√rln−1rln+rln,
ahol
rl1,rl2,rl3,...,rln,rln
a dinnyék r1ler2r3le...lern-1
rn gömbsugarai valamilyen
sorrendben.
A legrövidebb dinnyesorban a dinnyék úgy következnek egymás után, hogy a fenti összeg a legkisebb legyen.
Tekintsük a dinnyék átmérőinek összegét, amely legyen
H=2(r1+r2+r3+r4+...+rn1+rn).
Vonjuk ki a belőle a fentebb kapott L összeget:
2(r1+r2+r3+r4+...+rn-1+rn)-
−(rl1+2√rl1rl2+2√rl2rl3+2√rl3rl4+⋯+2√rln−1rln+rln)
A kisebbítendő tagjait át lehet rendezni abba a sorrendbe, amilyen sorrendben a kivonandóban szerepelnek:
2(rl1+rl2+rl3+...+rln1+rln)-
−(rl1+2√rl1rl2+2√rl2rl3+2√rl3rl4+⋯+2√rln−1rln+rln)
A kivonás elvégzése utána a maradék:
D=H−L=rl1−2√rl1rl2+rl2+rl2−2√rl2rl3+rl3+rl3−
−2√rl3rl4+rl4+⋯+rln−1−2√rln−1rln+rln,
amely viszont a következőképpen írható:
D=(√rl1−√rl2)2+(√rl2−√rl3)2+(√rl3−√rl4)2+⋯+(√rln−1−√rln)2.
A legrövidebb dinnyesor tehát akkor adódik, ha ez utoljára kapott négyzetösszeg maximális. Ezzel megoldottuk a dinnyeárusra a díjbeszedő által kirótt feladatot.
A díjbeszedő feladatát, vagyis a legrövidebb dinnyesor hosszának megállapítását elvileg úgy oldhatjuk meg, hogy a 11 dinnye minden lehetséges sorrendjét előállítjuk, és megkeressük a legrövidebb sor hosszát. Ennek gyakorlati kivitele hosszadalmas, hiszen 11!=39 916 800 lehetséges sorrendje van a dinnyéknek. A feladatnak ezt a részét is az imént kapott négyzetösszeg útmutatása alapján oldhatjuk meg. Ebben a sugarak négyzetgyökei különbségének négyzetösszege szerepel. Ebből következik, hogy nagy sugarú dinnyék szomszédságában kis sugarúakat kell elhelyezni, amelyre nézve az |ri-1-ri|+|ri-ri+1| tájékoztató összeg nagyobb számot ad.
Ennek megfelelően tegyük középre a legnagyobb sugarú dinnyét, és
tegyük két oldalára a két legkisebb sugarút. Ezek mellé -- kifelé
folytatva a sort -- tegyük a következő két legnagyobbat, majd melléjük
a következő két legkisebbet, aztán megint a két maradék legnagyobbat,
majd a két közepes méretűt a sor két végére; végig figyelve az kritérium
érvényesülésére. Ezzel az eljárással az alábbi sorozathoz jutunk:
Azaz
l1=6, l2=7, l3=4, l4=9, l5=2, l6=11,
l7=1, l8=10, l9=3, l10=8, l11=5.
L=r6+2(√r6r7+√r7r4+√r4r9+√r9r2+√r2r11+√r11r1+
+√r1r10+√r10r3+√r3r8+√r8r5)+r5=316,5283798 cm.
Ezzel az elrendezéssel az egész dinnyesorra képezett
Delta=|rl1-rl2|+|rl2-rl3|+|rl3-rl4|+...+|rln-2-rln-1|+|rln-1-rln|
összeg értéke 79; a
D=(√rl1−√rl2)2+(√rl2−√rl3)2+(√rl3−√rl4)2+⋯+(√rln−1−√rln)2
összeg 13,4716202 cm. Természetesen L+D=H.
Az, hogy a fenti elrendezés a lehetséges legrövidebb sor, az eddigiekből még nem következik. Olvasóinktól várunk egy bizonyítást, vagy egy még rövidebb dinnyesort ....
Légrádi Imre, Sopron