Kroegentocht met k kroegen en k*2 teams

[wacco]

Ten eerste weet ik niet of dit probleem al eerder is langsgekomen, kan er iig niets over vinden. Keywords zijn welkom.

Het probleem: Er is een kroegentocht, waar k kroegen zijn en k*2 teams. Het doel is om elke kroeg met je team te bezoeken en daar een wedstrijd te doen tegen een ander team. Je mag dus niet:
- twee keer in dezelfde kroeg puzzelen
- twee keer tegen hetzelfde team spelen
Is dit mogelijk voor elke k, en is er een formule om te bepalen welke route elk team moet nemen?

Dit zit ons dus op stage al twee uur flink bezig te houden, en we komen er niet uit

Een paar conclusies waar we al wel 'uit' zijn:

Met k = 3 kan het zonder problemen, dit stond in een paar minuten op papier en is één van de oplossingen (horizontaal de kroegen, verticaal de 'rondes'):

12	34	56
36	15	24
45	26	13

Met minder kan het niet, met meer hebben we geen oplossing kunnen vinden.
We 'denken' dat oneven k wel kan, even niet. Maar onderbouwen is nog niet echt gelukt.

Verder is het aantal mogelijke combinaties van teams (n * n-1) / 2, of uitgedrukt in k: 2k²-k. En verder zijn hier meerdere pagina's aan theorieën volgekrabbelt maar niets wat echt zal helpen ben ik bang.

Iemand een idee?

[3V3RT]

51	74	53	72
62	61	64	63
73	52	71	54
84	83	82	81

dit kan voor k=4. formule kan ik even niet geven hiervoor, daar ben ik nu te gaar voor

[ Voor 181% gewijzigd door 3V3RT op 30-10-2008 16:38 ]

[StefSybo]

@hierboven: Je laat teams meerdere wedstrijden in dezelfde ronde spelen, dat is volgens de probleemstelling niet expliciet verboden, maar ik denk dat een team niet tegelijkertijd in meerdere kroegen aanwezig kan zijn.

Met k oneven is het vrij makkelijk, de eerste k teams beginnen allemaal bij één café en bezoeken de cafés in oplopende volgorde (aangenomen dat ze genummerd zijn en na café k komt café 1). De andere k teams beginnen ook allemaal in één café en bezoeken de cafés in aflopende volgorde. Teams komen elkaar dan pas weer tegen in het café waar ze begonnen zijn in ronde k+1, dus dan is het spel al afgelopen.
Dit kan je zien doordat de 'afstand' tussen twee teams die in ronde i tegen elkaar gespeeld hebben elke volgende ronde met 2 toeneemt (één team schuift een kroeg naar voren, het andere een kroeg naar achteren). Ze zijn pas weer tegelijk in hetzelfde café als deze afstand een veelvoud van k is, de eerste keer is dus in ronde i+k, als de afstand 2k is. Dat is dus op zijn vroegst in ronde k+1, als het spel al afgelopen is.

Met een even k kan ik ook niet zo snel een oplossing vinden en ik vraag me af of dat wel kan. Met bovenstaand algoritme is het probleem dat teams elkaar alweer tegenkomen in ronde i+(k/2) en dat is voordat het spel is afgelopen.
Om dit te voorkomen zou je zeggen dat de 'oplopende' teams halverwege het spel een kroeg overslaan om nieuwe tegenstanders tegen te komen. Dan speelt niemand twee keer tegen dezelfde tegenstander, maar dan komen deze 'oplopende' teams in de laatste ronde al terug in hun 'startkroeg'. De kroeg die zo'n team nog niet bezocht heeft is dan de kroeg die het na ronde k/2 heeft overgeslagen. In die kroeg is op dat moment een 'aflopend' team aanwezig, maar tegen dat team heeft het 'oplopende' team al gespeeld, want het enige 'aflopende' team waar ze nog tegen moeten is op dat moment in de 'startkroeg' van het 'oplopende' team.
Dat gaat dus niet werken. Misschien is er een ander algoritme dat wel werkt, maar ik kan er geen verzinnen

[wacco]

Het 'diagonale' van t_n doet k_i+1 = n/2? k + 1: k - 1; waar t team is, n welk team, k welke kroeg, i welke iteratie waren we hier inderdaad ook al achter, en ook dat ze elkaar halverwege tegen komen bij een even aantal kroegen. Ik wist het alleen even niet te verwoorden (bovenstaande is meer programmeren) dus had het maar achterwege gelaten

Verder heeft gistermiddag Paul hier op stage nog een oplossing weten te vinden voor k=4:

1,2	4,6	5,7	3,8
5,6	1,3	2,8	4,7
3,7	5,8	1,4	2,6
4,8	2,7	3,6	1,5

De theorie erachter is dat je team 1 telkens in een andere kroeg laat spelen, tegen een ander team. Daarna wil je niet meer de rest van de combinaties niet meer dat de teams 1 t/m 5 tegen een ander team uit die groep speelt. Met een dot trial & error & excel kwam er vervolgens bovenstaande uitrollen.

Er zijn zat patronen in te zien maar de achterliggende theorie zijn we nog niet helemaal uit. Koekje voor degene die 'em door heeft

[wacco]

We zijn er uit qua 'algoritme' voor een even k. Het kan, het zijn twee sudokus naast elkaar.
De wiskunde erachter zal dan wel hetzelfde zijn als wat er voor sudokus geld, maar weet niet of die ooit echt gedefinieerd zijn.

Ten eerste moeten we even de notatie aanpassen. Wat we doen is horizontaal over welk team we het hebben, verticaal in welke bar ze moeten gaan zitten in welke iteratie. Verder willen we dat bijvoorbeeld team 1 maar 1 keer in elke kroeg zit, en de tweede requirement is dat er telkens tegen een ander team gespeeld wordt uit de andere groep (sudoku). Dan krijg je voor 4 kroegen:

 1  2  3  4   5  6  7  8
------------------------
 1          | 1
 2          |    2
 3          |       3
 4          |          4

Ik weet even niet of dit voor een ervaren sudoku'er genoeg is om beide sudokus (met de waardes 1 tot 4, twee sudokus naast elkaar) op te kunnen lossen, maar met wat trial & error kwam ik iig tot 'een' oplossing:

 1  2  3  4   5  6  7  8
------------------------
 1  3  4  2 | 1  3  4  2
 2  4  3  1 | 4  2  1  3
 3  1  2  4 | 2  4  3  1
 4  2  1  3 | 3  1  2  4

Zie ook hoe dus subsets sudoku-correct zijn.
Wat nog even naar de oude notatie vertaalt kan worden:

1,5  4,8  2,6  3,7
4,7  1,6  3,8  2,5
2,8  3,5  1,7  4,6
3,6  2,7  4,5  1,8

Wat een andere oplossing is als eerder.

Nu blijft de vraag nog of dit toe te passen is op een oneven aantal kroegen somehow, en hoeveel oplossingen er zijn voor elke k.

Edit: Een oneven aantal kroegen zou natuurlijk een echte sudoku zijn, maar er zal iets van een regel zijn dat k deelbaar moet zijn. Geen oplossing voor 5, 7, maar wel voor 9.

[ Voor 5% gewijzigd door wacco op 31-10-2008 10:36 ]