Loading [MathJax]/jax/output/HTML-CSS/jax.js
Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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 r1ler2ler3le...lern-1lern sugarú n darab dinnye esetén akkor a legkisebb, ha a

D=(rk1rk2)2+(rk2rk3)2+(rk3rk4)2+

+(rk4rk5)2++(rkn1rkn)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=2ab, ahol a és b a két gömb sugara. Ennek alapján a feladatban meghatározott dinnyesor hossza:

L=rl1+2rl1rl2+2rl2rl3+2rl3rl4+2rln1rln+rln,

ahol rl1,rl2,rl3,...,rln,rln a dinnyék r1ler2ler3le...lern-1lern 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+2rl1rl2+2rl2rl3+2rl3rl4++2rln1rln+rln)

A kisebbítendő tagjait át lehet rendezni abba a sorrendbe, amilyen sorrendben a kivonandóban szerepelnek:

2(rl1+rl2+rl3+...+rln1+rln)-

(rl1+2rl1rl2+2rl2rl3+2rl3rl4++2rln1rln+rln)

A kivonás elvégzése utána a maradék:

D=HL=rl12rl1rl2+rl2+rl22rl2rl3+rl3+rl3

2rl3rl4+rl4++rln12rln1rln+rln,

amely viszont a következőképpen írható:

D=(rl1rl2)2+(rl2rl3)2+(rl3rl4)2++(rln1rln)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 |r_{i-1}-r_i|+|r_i-r_{i+1}|=\max 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=(rl1rl2)2+(rl2rl3)2+(rl3rl4)2++(rln1rln)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