matematikk.net

I en ludoturnering er det 100 deltagere. Alle møter alle nøyaktig 1 gang og ingen kamper ender uavgjort. Er det nødvendigvis mulig å liste spillerne i en rekkefølge sånn at #1 på lista har slått #2, #2 har slått #3,..., #99 har slått #100?

La [tex]G[/tex] være en rettet graf med [tex]n[/tex] noder (spillerne) og [tex]{ n \choose 2 }[/tex] kanter (omgangene), hvor inngraden representerer antall seiere. Hver node har en grad på [tex]n-1[/tex].

Problemet blir altså å finne en hamiltonsk vei hvor man kun kan benytte seg av kanter som går fra en node (eventuelt kanter som går mot, men det blir det samme).

Dette går klart for [tex]n=2[/tex].

Anta at denne veien eksisterer for [tex]k<n[/tex] noder.

Nå ser vi på en graf med [tex]k+1[/tex] noder. Vi separerer én node fra grafen. I den resterende grafen med [tex]k[/tex] noder finnes det en hamiltonsk vei av induksjonshypotesen.

Det betyr at vi kan navngi nodene som [tex]v_r[/tex] og slik at den hamiltonske veien blir [tex]v_1 \to v_2 \to ... \to v_k[/tex].

Nå fester vi noden [tex]v_{k+1}[/tex] på grafen igjen. Vi ser at hvis [tex]v_{k+1} \to v_1[/tex] finnes, er vi ferdige.

Så anta at [tex]v_1 \to v_{k+1}[/tex] finnes i stedet.

Tegn en tegning om du vil, for dette er vanskelig å forklare med ord:

Trikset blir å prøve å finne [tex]v_i[/tex], slik at veien [tex]v_{i} \to v_{k+1} \to v_{i+1}[/tex] finnes.
Da kan vi "hoppe av" veien til [tex]v_{k+1}[/tex] og så tilbake for så å følge den opprinnelige veien igjen.
Dette skjer første gang (når vi teller nodene gjennom rangeringen) retningen til kantene fra [tex]v_{k+1}[/tex] blir rettet mot grafen (for kanten er rettet fra [tex]v_1[/tex]).
Hvis dette aldri skjer, har vi at en kant er rettet fra [tex]v_k[/tex] til [tex]v_{k+1}[/tex], som fullfører veien [tex]v_1 \to v_2 \to ... \to v_k \to v_{k+1}[/tex].

Av induksjonsprinsippet vil enhver rettet graf med n noder, hver med grad [tex]n-1[/tex], ha en hamiltonsk vei. Dermed finnes rangeringen vi ønsker for [tex]n=100[/tex].

Rangeringen er forresten ikke nødvendigvis unik. Faktisk så er den ikke det for [tex]n>3[/tex].

Uten å ha finlest, trur jeg dette stemmer. Induksjon er nøkkelen, og det koker bare ned til å vise at hvis man legger til en spiller kan denne alltid presses inn i ei gammal liste som vi veit eksisterer.