Optimale indeling tafels bij kaartspel

Helena109 · Bericht door **Helena109** » 18 apr 2011, 21:25

Dag wiskundeforumleden,

Mijn vader en ik hebben een vraag waar we niet uitkomen. Ik heb vroeger behoorlijk uitvoerig statistiek gehad, maar ben de sociale richting opgegaan en ben het he-le-maal kwijt

De vraag is als volgt:

Je hebt 16 bridgespelers (geen idee waarom, maar er zijn mensen die dat leuk vinden. Zélfs 16

Zij spelen aan 4 tafels, dus met 4 personen steeds aan een tafeltje.

Hoeveel speelrondes moet je minimaal spelen zodat íedereen tenminste 1x met íeder ander aan een (willekeurige) tafel heeft gezeten? Met zo min mogelijk 'dubbelingen' (dat je 2x of vaker dezelfde speler aan je tafeltje hebt)? (Het lijkt mij überhaupt onmogelijk dat je iedereen slechts 1x tegenkomt, in zo'n grote groep, en met 4 'subgroepjes').

Mochten jullie kunnen helpen - bridgeclub Westfriesland-Noord is jullie heel dankbaar

Hartelijke groet,
Ellen

Bericht door **arie** » 19 apr 2011, 11:33

Elke speler zit per ronde met 3 andere spelers aan tafel, omdat er 15 andere spelers zijn, zijn er dus minimaal 15/3=5 speelrondes nodig voordat je met alle andere spelers aan tafel gezeten hebt.
En deze minimum-oplossing is haalbaar.
Nummer de spelers 1 t/m 16, dan heb je bijvoorbeeld het volgende schema dat voldoet:

ronde 1:
tafel A: 1 2 3 4
tafel B: 5 6 7 8
tafel C: 9 10 11 12
tafel D: 13 14 15 16

ronde 2:
tafel A: 1 5 9 13
tafel B: 2 6 10 14
tafel C: 3 7 11 15
tafel D: 4 8 12 16

ronde 3:
tafel A: 1 6 11 16
tafel B: 2 5 12 15
tafel C: 3 8 9 14
tafel D: 4 7 10 13

ronde 4:
tafel A: 1 7 12 14
tafel B: 2 8 11 13
tafel C: 3 5 10 16
tafel D: 4 6 9 15

ronde 5:
tafel A: 1 8 10 15
tafel B: 2 7 9 16
tafel C: 3 6 12 13
tafel D: 4 5 11 14

Is dit wat je bedoelt?

Helena109 · Bericht door **Helena109** » 20 apr 2011, 12:07

Dag Arie,

Heel hartelijk dank voor je antwoord!

Dat was ook waar ik aan dacht. Echter, ik kreeg het vervolgens met geen mogelijkheid 'uitgetekend'. We liepen steeds vast.

Vervolgens vertelde een collega dat het niet mogelijk was om in vijf rondes iedereen iedereen te laten tegenkomen, omdat je gegarandeerd 'dubbelingen zou krijgen. Zie zijn argumentatie hieronder:

'We beginnen met 1,2,3,4 bij elkaar, en 5,6,7,8 enzovoorts.
Dan mogen die daarna dus niet meer bij elkaar. Dus 1, 2, 3 en 4 zitten telkens apart. Laten we zeggen respectievelijk aan tafel A, B, C, D.
5,6,7,8 moeten bij al deze tafels een keer ...langs. Dat is nog geen probleem, maar wel voor persoon 9.
Die moet namelijk zorgen dat hij bij geen van deze tafels iemand een 2de keer tegenkomt.
Stel 9 zit in ronde 2 bij tafel A, net als 1 en 5. Dan gaan 6 en 7 op dat moment bij twee van de andere tafels langs. Bij die twee tafels komt 9 deze spelers dus niet meer tegen.
Dus er is nog één tafel over waar speler 9 spelers 6 en 7 tegen kan komen. Maar daar kan hij geen twee keer zitten en 6 en 7 kunnen daar ook niet tegelijk zitten, want die zijn al samen geweest.'

Echter, jouw oplossing klopt als een bus! Daarom: wat is je systeem geweest?

Nogmaals erg bedankt!
Ellen

Bericht door **arie** » 20 apr 2011, 20:57

ronde 1 is triviaal:
tafel A: 1 2 3 4
tafel B: 5 6 7 8
tafel C: 9 10 11 12
tafel D: 13 14 15 16

in ronde 2 verdelen we elk tafelviertal van ronde 1 over de 4 tafels:
tafel A: 1 5 9 13
tafel B: 2 6 10 14
tafel C: 3 7 11 15
tafel D: 4 8 12 16

In ronde 3 t/m 5 blijven speler 1 t/m 4 verdeeld over tafel A t/m D, ze mogen immers niet nog eens onderling aan dezelfde tafel gaan zitten.

Kijk nu naar de overige 3 kolommen.
Dit moeten steeds de tafelviertallen van ronde 1 blijven.
In de volgende ronde kunnen ze alleen van plaats binnen hun kolom wisselen, ze mogen nooit meer aan dezelfde tafel plaatsnemen.
Splits elk viertal nu in tweetallen van hoge en lage nummers binnen elke kolom.
In ronde 2 spelen de lage nummers aan tafel A en B, hier met rood aangegeven (5,6), (9,10) en (13,14):

ronde 2:
tafel A: 1 5 9 13
tafel B: 2 6 10 14
tafel C: 3 7 11 15
tafel D: 4 8 12 16

In ronde 3 t/m 5 mag slechts 1 van deze tweetallen aan tafel A en B plaatsnemen, de andere 2 tweetallen moeten naar tafel C en D (ga zo nodig zelf na wat er gebeurt als je 2 rode tweetallen boven (=aan tafel A en B) zou houden):

ronde 3:
tafel A: 1 6 11 16
tafel B: 2 5 12 15
tafel C: 3 8 9 14
tafel D: 4 7 10 13

Natuurlijk moet het tweetal dat boven blijft wisselen van tafel, want 1 en 2 blijven zitten.
De twee tweetallen die naar C en D gaan moeten onderling wisselen van tafel: 9 heeft al bij 13 gezeten, en 10 bij 14.
Een zelfde redenatie geldt voor de zwarte nummers.
Omdat we na ronde 2 steeds 1 van de 3 tweetallen boven houden, zijn er na ronde 2 nog 3 ronden te gaan, en komen we precies goed uit:

ronde 4:
tafel A: 1 7 12 14
tafel B: 2 8 11 13
tafel C: 3 5 10 16
tafel D: 4 6 9 15

ronde 5:
tafel A: 1 8 10 15
tafel B: 2 7 9 16
tafel C: 3 6 12 13
tafel D: 4 5 11 14

PS:
Inderdaad, er zijn mensen die bridge leuk vinden, maar volgens mij gaat er toch echt niets boven wiskunde.

Helena109 · Bericht door **Helena109** » 22 apr 2011, 11:47

Dag Arie,

Dankjewel voor je uitvoerige antwoord! Het is helemaal duidelijk!

(Ja, mensen kunnen heel rare hobby's hebben. Maar goed, ze doen verder weinig waad en het houdt ze van de straat

Groetjes!

Bericht door **David** » 24 apr 2011, 23:53

Ik heb me een paar dagen af en aan geamuseerd en misschien heb ik een andere methode om geschikte indelingen te maken voor de bridgeclub (en andere activeiteiten met een ander aantal spelers, tafels en tafelplaatsen als zo'n indeling mogelijk is). Om dit te vinden had ik wel de oplossing van Arie, jou nodig.
Ik hernummer de tafelnummers even. Dat doe ik voor verderop. De 4 stoelen krijgen een nummer.
stoel s1, s2, s3, s4

We hebben: