Kezdőlap


Cím:	Dinnyék rendezése
Szerző(k):	Légrádi Imre
Füzet:	2002/január, 28 - 30. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

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: $d_{1} = 16$ cm, $d_{2} = 18$ cm, $d_{3} = 22$ cm, $d_{4} = 26$ cm, $d_{5} = 28$ cm, $d_{6} = 30$ cm, $d_{7} = 34$ cm, $d_{8} = 36$ cm, $d_{9} = 38$ cm, $d_{10} = 40$ cm, $d_{11} = 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 $r_{1} \leq r_{2} \leq r_{3} \leq ... \leq r_{n - 1} \leq r_{n}$ sugarú $n$ darab dinnye esetén akkor a legkisebb, ha a

\begin{matrix} \begin{matrix} D & = {(\sqrt[]{r_{k_{1}}} - \sqrt[]{r_{k_{2}}})}^{2} + {(\sqrt[]{r_{k_{2}}} - \sqrt[]{r_{k_{3}}})}^{2} + {(\sqrt[]{r_{k_{3}}} - \sqrt[]{r_{k_{4}}})}^{2} + \\ + {(\sqrt[]{r_{k_{4}}} - \sqrt[]{r_{k_{5}}})}^{2} + ... + {(\sqrt[]{r_{k_{n - 1}}} - \sqrt[]{r_{k_{n}}})}^{2} \end{matrix} \end{matrix}

összeg a legnagyobb; ahol tehát

r_{k_{1}}, r_{k_{2}}, r_{k_{3}}, ..., r_{k_{n - 1}}, r_{k_{n}}

az egyes, egymással érintkező dinnyék gömbsugarát jelöli, és ezen belül

k_{1}, k_{2}, k_{3}, ..., k_{n - 1}, k_{n}

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

A B = x = 2 \sqrt[]{a b}

, ahol

a

és

b

a két gömb sugara. Ennek alapján a feladatban meghatározott dinnyesor hossza:

\begin{matrix} L = r_{l_{1}} + 2 \sqrt[]{r_{l_{1}} r_{l_{2}}} + 2 \sqrt[]{r_{l_{2}} r_{l_{3}}} + 2 \sqrt[]{r_{l_{3}} r_{l_{4}}} + 2 \sqrt[]{r_{l_{n - 1}} r_{l_{n}}} + r_{l_{n}}, \end{matrix}

ahol

r_{l_{1}}, r_{l_{2}}, r_{l_{3}}, ..., r_{l_{n}}, r_{l_{n}}

a dinnyék

r_{1} \leq r_{2} \leq r_{3} \leq ... \leq r_{n - 1} \leq r_{n}

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

\begin{matrix} H = 2 (r_{1} + r_{2} + r_{3} + r_{4} + ... + r_{n_{1}} + r_{n}) . \end{matrix}

Vonjuk ki a belőle a fentebb kapott

L

összeget:

\begin{matrix} \begin{matrix} 2 (r_{1} + r_{2} + r_{3} + r_{4} + ... + r_{n - 1} + r_{n}) - \\ - (r_{l_{1}} + 2 \sqrt[]{r_{l_{1}} r_{l_{2}}} + 2 \sqrt[]{r_{l_{2}} r_{l_{3}}} + 2 \sqrt[]{r_{l_{3}} r_{l_{4}}} + ... + 2 \sqrt[]{r_{l_{n - 1}} r_{l_{n}}} + r_{l_{n}}) \end{matrix} \end{matrix}

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

\begin{matrix} \begin{matrix} 2 (r_{l_{1}} + r_{l_{2}} + r_{l_{3}} + ... + r_{l_{n_{1}}} + r_{l_{n}}) - \\ - (r_{l_{1}} + 2 \sqrt[]{r_{l_{1}} r_{l_{2}}} + 2 \sqrt[]{r_{l_{2}} r_{l_{3}}} + 2 \sqrt[]{r_{l_{3}} r_{l_{4}}} + ... + 2 \sqrt[]{r_{l_{n - 1}} r_{l_{n}}} + r_{l_{n}}) \end{matrix} \end{matrix}

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

\begin{matrix} \begin{matrix} D & = H - L = r_{l_{1}} - 2 \sqrt[]{r_{l_{1}} r_{l_{2}}} + r_{l_{2}} + r_{l_{2}} - 2 \sqrt[]{r_{l_{2}} r_{l_{3}}} + r_{l_{3}} + r_{l_{3}} - \\ - 2 \sqrt[]{r_{l_{3}} r_{l_{4}}} + r_{l_{4}} + ... + r_{l_{n - 1}} - 2 \sqrt[]{r_{l_{n - 1}} r_{l_{n}}} + r_{l_{n}}, \end{matrix} \end{matrix}

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

\begin{matrix} D = {(\sqrt[]{r_{l_{1}}} - \sqrt[]{r_{l_{2}}})}^{2} + {(\sqrt[]{r_{l_{2}}} - \sqrt[]{r_{l_{3}}})}^{2} + {(\sqrt[]{r_{l_{3}}} - \sqrt[]{r_{l_{4}}})}^{2} + ... + {(\sqrt[]{r_{l_{n - 1}}} - \sqrt[]{r_{l_{n}}})}^{2} . \end{matrix}

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

| r_{i - 1} - r_{i} | + | r_{i} - r_{i + 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

\begin{matrix} \begin{matrix} l_{1} = 6, l_{2} = 7, l_{3} = 4, l_{4} = 9, l_{5} = 2, l_{6} = 11, \\ l_{7} = 1, l_{8} = 10, l_{9} = 3, l_{10} = 8, l_{11} = 5. \end{matrix} \end{matrix}

\begin{matrix} \begin{matrix} L & = r_{6} + 2 (\sqrt[]{r_{6} r_{7}} + \sqrt[]{r_{7} r_{4}} + \sqrt[]{r_{4} r_{9}} + \sqrt[]{r_{9} r_{2}} + \sqrt[]{r_{2} r_{11}} + \sqrt[]{r_{11} r_{1}} + \\ + \sqrt[]{r_{1} r_{10}} + \sqrt[]{r_{10} r_{3}} + \sqrt[]{r_{3} r_{8}} + \sqrt[]{r_{8} r_{5}}) + r_{5} = 316, 528 379 8 cm . \end{matrix} \end{matrix}

Ezzel az elrendezéssel az egész dinnyesorra képezett

\begin{matrix} Δ = | r_{l_{1}} - r_{l_{2}} | + | r_{l_{2}} - r_{l_{3}} | + | r_{l_{3}} - r_{l_{4}} | + ... + | r_{l_{n - 2}} - r_{l_{n - 1}} | + | r_{l_{n - 1}} - r_{l_{n}} | \end{matrix}

összeg értéke 79; a

\begin{matrix} D = {(\sqrt[]{r_{l_{1}}} - \sqrt[]{r_{l_{2}}})}^{2} + {(\sqrt[]{r_{l_{2}}} - \sqrt[]{r_{l_{3}}})}^{2} + {(\sqrt[]{r_{l_{3}}} - \sqrt[]{r_{l_{4}}})}^{2} + ... + {(\sqrt[]{r_{l_{n - 1}}} - \sqrt[]{r_{l_{n}}})}^{2} \end{matrix}

összeg

13, 471 620 2

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

... .