Et matematisk problem, lad os kalde det "Pubcrawl Paradokset"...

Posted on

For lang tid siden, var jeg med til at planlægge en pubcrawl, og vi løb ind i et planlægningsproblem, jeg ikke har kunnet finde en løsning på endnu, og umiddelbart har ingen af dem jeg lige har spurgt, kunne give mig et hint af, i hvilken retning svaret måtte ligge. Så nu smider jeg det op på internettet, og håber at der sidder nogle kloge hoveder derude, der kan hjælpe lidt.

For en god ordens skyld, så skal det siges at jeg er ved at lave en brute-force løser, der tester alle mulige permutationer, men inden den bliver færdig for de rigtigt store tilfælde, kunne det være fedt hvis nogen havde en ordentlig grund til, hvorfor man ikke kan planlægge det. 

Jeg sætter i øvrigt en flaske vin på højkant. Måske 2. Og også et kram! Nå - her begynder vi:

  • Pubcrawlen involverer et antal aktiviteter, svarende til antallet af steder der skal besøges. Dette antal er m.
  • Pubcrawlen har n deltagende hold.
  • På hvert sted, skal to hold kæmpe imod hinanden, så n = 2m. Om man møder alle hold, er ikke vigtigt.
  • Hvert hold må kun prøve hver aktivitet én gang.
  • Holdene må ikke kæmpe mod hinanden mere end én gang.
  • Og slutteligt, grundet fysikkens love, kan man ikke være på 2 pubs på én gang.

Så langt jeg har fundet frem til, så kan problemet ikke løses hvis antallet af aktiviteter (m), er lige. Men for et ulige antal, kan man bare drible ned gennem et skema, og så passer pengene. Er der nogen der kan hjælpe? Gerne, eventuelt med noget litteratur på emnet, samt et navn på det matematiske aspekt af det. Jeg er sådan set ligeglad med om det kan løses eller ej, jeg vil bare gerne vide hvorfor. På billedet nedenfor har jeg vist et eksempel, med 3 steder, og 6 hold. Og den kan godt løses (med mindre jeg har overset noget).

pubcrawlParadox

 

Og skulle det resultere i at vi er nød til at opfinde noget matematik for at få det løst, jamen så gør vi det gerne! Jeg håber at måtte blive medforfatter på en eventuel publikation.

Jeg skal nok give lyd når jeg nærmer mig et resultat... Og ja, jeg løser også mine sudoku med kuglepen, jeg lever et hårdt liv!
/Rasmus