Hvem kan blive mestre, og hvem rykker ned?

Folk, der går op i fodbold, ved, at når turneringer nærmer sig deres afslutning - når der f.eks. er tre spillerunder tilbage af superligaen - så er der virkelig mange spekulationer omkring hvilke hold, der stadig er i fare for at rykke ned, hvilke hold, der stadig kan få sølvmedaljer, osv.

Faktisk er det forbavsende svært at regne sig frem til præcist, hvad der kan lade sig gøre, og hvad der helt sikkert ikke kan lade sig gøre. Sportsjournalister forsøger sig med dette, og man hører udtalelser, der refererer til en "matematisk" chance for, at noget kan ske. En af grundene til, at det er vanskeligt at finde ud af, er, at når hver kamp kan ende med sejr, uafgjort eller tab for hjemmeholdet, så er der f.eks. i superligaen med bare tre spillerunder tilbage 150.094.635.296.999.121 (ca. 150 billiarder) muligheder for, hvordan resultaterne kan fordele sig - og det er endda før, man tager målscore i betragtning.

Når man som person kigger på dette, kan man heldigvis se bort fra en masse muligheder, man kan se er irrelevante, men med flere end tre spillerunder tilbage, bliver det ret svært manuelt at afgøre spørgsmål med sikkerhed.

De to datalogistuderende Jan Christensen og Anders Knudsen har set på denne problemstilling i deres speciale under vejledning af professor Kim Skak Larsen fra Institut for Matematik og Datalogi på Syddansk Universitet. Sammen har de dels bevist, at problemet virkeligt er meget svært; formelt siger man, at problemet er NP-hårdt. Men derefter har de vist, at man faktisk godt kan løse det vha. en computer alligevel - og også indenfor rimelig tid for f.eks. superligaen.

Det betyder, at man i aviser og på betting-sider kan give ekstra information til sine læsere, hvis man har lyst. I tabellen, der viser den aktuelle stilling, kan man tilføje en søjle med et interval, som f.eks. 3-8. Det betyder så, at holdet helt sikkert bliver placeret på en af de pladser. Mere præcist kan holdet f.eks. blive nummer 3, hvis andre resultater flasker sig, men der er ingen måde, de kan blive nummer 2 på. Tilsvarende kan de risikere at blive nummer 8, men der er ingen risiko for, at de kan blive nummer 9 - ligegyldigt hvor dårlige andre resultater er for dem.

Denne ekstra information kan nu leveres for alle hold - ligegyldigt hvor mange spillerunder, der er tilbage. Men det er selvfølgeligt mest interessant, når vi nærmer os afslutningen.

Anders og Jan har lige holdt deres mundtlige forsvar, hvor de scorede 12-taller!