Een spel spelen

Er zijn 10 spellen en 20 spelers. Elk spel is een 2-persoons spel. Iedereen moet elk spel 1 keer spelen, telkens tegen een unieke tegenstander.

Dus 10 ronden, in elke ronden speelt iemand een uniek spel tegen een unieke tegenstander.

Als je het spel speelt met een oneven getal, dus bijvoorbeeld 9, dan lukt het wel, maar bij 10 niet.. Tenminste niet als ik het handmatig probeer.

Mijn vraag, is het mogelijk om het spel met 10 spellen te spelen, zo ja -> bewijs, zo nee -> bewijs

Roderi
Leerling bovenbouw havo-vwo - maandag 14 oktober 2002

Antwoord

Hoi,

De zekere regels van het tornooi:
We hebben n spellen en 2n spelers.
Iedereen speelt elk spel precies één keer, dit noemen we een partij.
Niemand speelt meer dan één keer tegen dezelfde tegenspeler.
Het tornooi wordt in een aantal ronden gespeeld.
In elke ronde spelen een aantal spelers precies één spel. Er kunnen tijdens een ronde één of meer spellen parallel gespeeld worden. Eenzelfde spel kan tijdens een ronde maar door één koppel spelers gespeeld worden.

Uit je opgave is niet duidelijk of iedereen per se tegen iedereen moet spelen tijdens het tornooi. In dat geval zou de eerste speler bijvoorbeeld tegen 2n-1 verschillende tegenstanders moeten uitkomen. Er zouden dus 2n-1 verschillende spellen moeten zijn en dat is niet het geval. Het is dus NIET nodig dat iedereen tegen iedereen speelt.

In je opgave besluit je dat je n ronden moet spelen. Als iedereen elke spel moet spelen is dit inderdaad het minimum aantal ronden. Laten we deze beperking voorlopig weglaten en zoeken naar een oplossing voor het probleem met het minimale aantal rondes. Als dit minimum inderdaad n is, dan hebben we je oorspronkelijke puzzel opgelost. Als deze minimumwaarde niet bereikt kan worden, dan hebben we bewezen dat er geen oplossing is voor je puzzel.

Er zijn hoogstens n(2n-1) partijen, er wordt minstens 1 partij per ronde gespeeld. Er zijn dus hoogstens n(2n-1) rondes nodig om alles af te werken.

Voor n=2 met spelen G1 en G2 en rondes R1,R2,... hebben we bijvoorbeeld:
G1 G2
R1 12 -
R2 - 13
R3 - 24
R4 34 -
Het kleinste aantal rondes is dus 4 en we kunnen geen rondes combineren.

In opeenvolgende rondes laten we eerst speler 1 alle spellen doorlopen, telkens tegen één van de spelers waartegen hij nog niet speelde. Daarna is het de beurt aan twee voor alle spelen die hij nog niet deed, enz. In elke rond spelen we dus één spel.

Voor n=3 hebben we:
G1 G2 G3
R1 12 - -
R2 - 13 -
R3 - - 14
R4 - 24 -
R5 - - 25
R6 34 - -
R7 - - 36
R8 56 - -
R9 - ???

Of voor n=3 hebben we:
G1 G2 G3
R1 12 - -
R2 - 13 -
R3 - - 14
R4 - 25 -
R5 - - 26
R6 34 - -
R7 - - 35
R8 56 - -
R9 - 46 -

We kunnen verschillende rondes combineren tot:
G1 G2 G3
R1 12 46 35
R2 56 13 26
R3 34 25 14
En inderdaad: een minimum van n ronden kan volstaan...

Voor n=4 vinden we bijvoorbeeld:
G1 G2 G3 G4
R1 12 65 73 84
R2 64 13 58 72
R3 75 28 14 63
R4 83 74 62 15

De vraag is dus of we voor elke n een vierkant van nxn kunnen vullen met
de getallen 1,2,..., 2n zodat:
- elk vakje bevat precies 2 getallen
- elke rij en elke kolom bevat alle getallen
- geen twee vakjes bevatten dezelfde twee getallen

Hier moet ik nog even op zoeken...
Alle feedback is welkom...

Groetjes,
Johan

andros
woensdag 23 oktober 2002

©2001-2024 WisFaq