Feladat:	2013. évi Kürschák matematikaverseny 3. feladata	Korcsoport: -	Nehézségi fok: -
Megoldó(k):	Fleiner Tamás
Füzet:	2014/február, 70. oldal		PDF  |  MathML
Témakör(ök):	Matematika, Kürschák József (korábban Eötvös Loránd), Számhalmazok, Gráfelmélet
Hivatkozás(ok):	Feladatok: 2014/február: 2013. évi Kürschák matematikaverseny 3. feladata

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.   Megoldás. Megmutatjuk, hogy a válasz igenlő. Legyen $l_{ji}=l_{ij}$ minden $1\le i<j\le n$ párra. Határozzuk meg egyenként a továbbiakban potenciálnak nevezett $a_1\mathrm{,}{a}_2\mathrm{,}\text{...}\mathrm{,}{a}_n$ mennyiségeket (nem feltétlenül ebben a sorrendben) a következő szabály szerint. Minden lépésben válasszunk egy olyan $i$ indexet, amelyre az $a_i$ potenciált korábban még nem határoztuk meg, és amelyre azon $l_{ki}$ értékek $s$ összege, amelyekre $a_k$-t már korábban meghatároztuk, a lehető legkisebb. Az így megválasztott $i$ indexre legyen az $a_i$ potenciál ez a minimális $s$ összeg. Tegyük fel, hogy az $a_i$ potenciált az $a_j$ potenciál előtt határoztuk meg, továbbá, hogy $K$ az $a_i$ előtt, $M$ pedig az $a_i$ után, de $a_j$ előtt meghatározott $a_t$ potenciálokhoz tartozó $t$ indexek halmaza. Az eljárásból következtében ekkor ${\displaystyle \begin{array}{cc}\hfill {\displaystyle a_j}& {\displaystyle ={\sum }_{k\in K}{l}_{kj}+l_{ij}+{\sum }_{m\in M}{l}_{mj}\ge {\sum }_{k\in K}{l}_{ki}+l_{ij}+{\sum }_{m\in M}{l}_{mj}=}\hfill \\ \hfill {\displaystyle }& {\displaystyle =a_i+l_{ij}+{\sum }_{m\in M}{l}_{mj}\ge a_i+l_{ij}\mathrm{,}}\hfill \end{array}}$ tehát $|a_i-a_j|\ge l_{ij}$ valóban teljesül minden $i\ne j$ párra. Az indoklás befejezéséhez pedig mindössze annyit kell megfigyelnünk, hogy $\begin{array}{c}{\displaystyle S:=a_1+a_2+\text{...}+a_n}\end{array}$ éppen az $l_{ij}$ ($1\le i<j\le n$) értékek összege, hiszen minden egyes $l_{ij}$ pontosan egyszer szerepel $S$-ben, mégpedig az $a_i$-t és $a_j$-t definiáló összegek közül abban, amelyik a később meghatározott potenciálhoz tartozik.  $\square$   Megjegyzés. A feladat és a megoldása is sokkal világosabb, ha átfogalmazzuk gráfokra. Ilyen szóhasználattal élve azt kell igazolnunk, hogy bárhogyan is rendelünk egy $n$ pontú teljes gráf éleihez nemnegatív élhosszakat, a gráfnak létezik egy aciklikus (azaz irányított kört nem tartalmazó) irányítása, és az $n$ csúcs mindegyikéhez hozzárendelhető egy-egy nemnegatív potenciál úgy, hogy a csúcsok potenciálösszege ne haladja meg az élek összhosszát, továbbá bármely $uv$ irányított él esetén az $u$ és $v$ csúcsok potenciálkülönbsége legalább az $uv$ él hossza legyen. A megoldás kulcsa, hogy a potenciálok megválasztásának sorrendje az $l_{ij}$ élhosszakhoz tartozó úgynevezett minvissza sorrend. Ez úgy kapható, hogy tetszőleges csúcsból kiindulva, ha már kiválasztottuk a sorrend első néhány elemét, akkor a soron következő csúcs az lesz, amelynek össztávolsága az eddig választott csúcsoktól minimális. Ha ezek után a gráf minden élét a minvissza sorrendben korábban felbukkanó csúcsból a sorrendben később szereplő csúcsba irányítjuk, akkor a potenciálokat természetes módon definiálva éppen a kérdéses $a_i$ számokat kapjuk meg. Érdekes, hogy míg a hasonló módon definiált maxvissza sorrendet sokat vizsgálták (a segítségével például hatékony algoritmus adható arra, hogy egy összefüggő gráfban megtaláljuk a lehető legkevesebb élt, amelyek elhagyásától a gráf már nem marad összefüggő), addig a minvissza sorrendnek a bizottság tudomása szerint nem ismert hasonló alkalmazása.