Gruppspel där alla ska möta alla, tre personer i varje grupp

Hur möts 8 spelare på 3 kontroller?

8: (7,6), (5,4), (3,2), (1,?)

Det går alltid att göra ett schema där alla möter alla lika många gånger var, det var ju det jag visade först. Men för vissa N räcker det med mycket färre matcher än
(N över 3).
Iaf för N=7 klarar man sig alltså med 7 matcher ist f 35.

Den kanske matematiskt intressantare frågan är om för vilka kombinationer av
N = antal spelare
och
m = antal kontroller,
som är just sådana att det räcker med mindre än
(N över m)
matcher. Och så gärna även en allmän algoritm för att konstruera spelscheman. Kan ju vara bra att ha om TS har ett annat antal kompisar nästa gång och med ett annat antal spelkontroller.

Noterar iaf att det alltid måste finnas en symmetri mellan problemen med m kontroller och med N-m kontroller, för ett givet N. Dvs med t ex N=7 spelare och m=4 kontroller krävs det också 7 spelomgångar. Varför? Därför att varje kombination med 3 spelare, samtidigt är en kombination med 4 som INTE spelar. Med 4 kontroller skulle man alltså kunna använda samma schema som med 3, om man bara vänder på vilka som spelar och vilka som tittar på.

Ok, så med 7 spelare och 4 kontroller är det alltså det komplementära schemat till 7 spelare med 3 kontroller. Dvs vi använder samma schema, men de som spelade resp tittade på i (7,3)-schemat, byter nu plats. Resultatet blir (i parentes de som tittar på)
4567 (123)
2367 (145)
2345 (167)
1357 (246)
1346 (257)
1256 (347)
1247 (356)
Noterar att alla nu får möta alla andra 2 gånger. T ex möter 1 och 3 varandra två gånger.

Det mer allmäna problemet har jag ingen lösning på just nu, men undrar om inte en greedy algoritm är rätt ok?

Omgång ett är enkel, omgång två så väljer man som första spelare någon som har spelat lägst antal matcher f.n. Som spelare två väljer man någon ur "lägst antal matcher gruppen" som inte mött spelare 1. osv osv. Man undviker worst case som borde vara att man har en spelare kvar som inte spelat ngn match på slutet.

Borde funka rätt bra om man bara skall dra ihop ett schema super-snabbt.

Tänker man till lite, borde det inte vara sååå svårt att skriva ihop något liknande på sitt favoritprogrammeringsspråk, som itererar fram match efter match, ändå tills alla har spelat mot alla lika många gånger. Vi vet ju redan att det krävs max
(N över m)
matcher, vilket alltså lämpligen sätts som övre gräns (för att undvika ev evighetsloop om något går fel). I programmet behöver man då vid varje ny match hålla reda på hur många gånger varje spelare redan har mött varje annan spelare, vilket bör kunna göras med en lämplig N×N matris.

Ett (7,4)-schema borde bli {1, 2, 3, 4}, {1, 5, 6, 7}?

(8,3)-schema innehåller ej #8: {1, 2, 3}, {1, 4, 5}, {1, 6, 7}, {2, 4, 6}, {2, 5, 7}, {3, 4, 7}, {3, 5, 6}.

Jag är fortsatt fascinerad både av det allmänna problemet med N spelare och m kontroller, och av din lösning för (N,m)=(7,3). Hur bar du dig åt?

Man kan skriva din lösning som en matris, där varje rad är matchnummer, och varje kolumn är spelare:
Denna matris är symmetrisk, dvs lika med sitt transponat. Inte alls självklart kan tyckas. Varje par av rader har precis EN spelare gemensam, vilket om man vill även kan tolkas som att det är samma vinkel mellan alla radvektorer (=acos(1/3)= ca 70.53°). Matrisens determinant är -24, dvs inte 0, vilket betyder att radvektorerna är en 7D vektorbas. Och så inte minst att det för varje par av spelare finns exakt EN match där de möts.

Liknande gäller om (N,m)=(7,4), där matrisen blir samma som ovan, fast med alla nollor och ettor utbytta mot varandra. Vinkeln mellan radvektor blir nu 60°. Och i detta fall möts varje par av spelare i TVÅ matcher.

I båda fallen är antalet kombinationer
(7 över 3) = (7 över 4) = 35
men bara 7 matcher räcker alltså för att lösa TS problem. Man kan misstänka att det det finns 5 olika lösningar, eftersom 5•7=35. Sant??

Och hur gör man nu i det allmänna fallet??

Frågan är(?) vad ett korrekt spel är. Det finns ingen entydig uppställning.

(7,3). Några möjligheter:
{1, 2, 3}, {1, 4, 5}, {1, 6, 7}, {2, 4, 6}, {2, 5, 7}, {3, 4, 7}, {3, 5, 6}
eller
{1, 2, 7}, {1, 3, 6}, {1, 4, 5}, {2, 3, 5}, {2, 4, 6}, {3, 4, 7}, {5, 6, 7}

(7,4):
{1, 2, 3, 4}, {1, 5, 6, 7}
eller
{1, 5, 6, 7}, {2, 3, 4, 7}
(och många andra)

Lite mera info som jag fann på nätet. Fanns två metoder att skapa dessa spelplaner, t.ex. för (9,3):

{1, 2, 3}, {1, 4, 5}, {1, 6, 7}, {1, 8, 9}, {2, 4, 6}, {2, 5, 7}, {3, 4, 7}, {3, 5, 6}
och
{1, 2, 9}, {1, 3, 8}, {1, 4, 7}, {1, 5, 6}, {2, 3, 7}, {2, 4, 6}, {2, 5, 8}, {3, 4, 5}, {3, 6, 9}, {4, 8, 9}, {5, 7, 9}, {6, 7, 8}

Längden är olika för (9,3) men lika för (7,3) även om spelen skiljer sig åt;
{1, 2, 3}, {1, 4, 5}, {1, 6, 7}, {2, 4, 6}, {2, 5, 7}, {3, 4, 7}, {3, 5, 6}
och
{1, 2, 7}, {1, 3, 6}, {1, 4, 5}, {2, 3, 5}, {2, 4, 6}, {3, 4, 7}, {5, 6, 7}

En \(10\times10\)-matris där rader är \(n\) och kolumner \(k\) för den första spelalgoritmen ges av, \(1<k \le n/2\),
\[
M_1=
\left(
\begin{array}{cccccccccc}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 6 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 10 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 15 & 4 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 21 & 7 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 28 & 7 & 2 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 36 & 8 & 3 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 45 & 10 & 3 & 2 & 0 & 0 & 0 & 0 & 0 \\
\end{array}
\right)
\]

Tror fortfarande att det slutar med ngn form av greedy-algoritm, men ett försök att ställa upp det:
Om man utgår från en matris som du skriver så om y är antal spelade matcher så borde:

Y = (1/(2*m))*(( summa över alla i,j ( x(ij)) -n)
Man summerar helt enkelt matriselementen, drar bort ettorna för "möta sig själv" och delar med antal deltagare i en match och sedan delar man det med 2 då x(ij)=1 ger att x(ji) också sätts till ett.

Sedan min Y med bivillkor:
x(ij) större än eller lika med 1
x(ij)-x(ji) = 0

Egentligen tycker jag det är mer intressant att se på det geometriskt. När man lägger ut en match verkar det vettigt att lämna ma xarea kvar i matrisen. Ett sätt att göra det är att lägga in kvadrater (exempel (2,1),(3,1),(2,3) osv). Ett annat sätt är att fylla längs diagonalerna((2,1),(2,3) osv). Om det blir ojämnt (eg när man når(n-1,n),(n,n-1) så har man fortfarande behov av att placera in fler spelare i en match så kan man fylla (1,n) (och (n,1)) osv då det inte tar så mycket "diagonalplats".

Litet tillägg, när man väljer diagonaler så bör man nog välja de som är multipler av m i längd eller kombinera diagonaler som tillsammans blir m eller multipler av m första hand...

Givet EN lösning kan man man förstås få en massa andra genom (1) radbyten (dvs byta matchordning) eller genom (2) kolumnbyten (dvs byta plats mellan spelare i schemat). Som regel bevarar inte detta symmetrin, men likafullt verkar det ju rimligt att kalla alla dessa varianter för SAMMA lösning. Och då tror jag att det faktiskt bara finns en för varje (N,m).

Ditt förslag till lösning för (7,4) duger INTE, eftersom spelare 1 då spelar 2 matcher medan alla andra bara spelar 1. Dessutom möts inte t ex spelare 2 och 5 i ditt schema.

Kravet på en lösning är:
* alla spelare får möta varje annan spelare
* varje par möter varandra lika många gånger
* alla spelare får spela lika många matcher var
(Dessa krav är förstås beroende av varandra).
Symmetrin i matrisen är ren bonus, men inte ett krav.

En giltig (7,4)-lösning ges t ex av
(framtagen från komplementet till Iqni-ferroques
(7,3)-lösning, följt av några rad och kolumnbyten för att fixa till symmetrin). Alla spelar 4 matcher var, och alla möter alla andra 2 gånger var.

Efter lite meck har jag även hittat en lösning till (13,4):
där alla spelar 4 matcher var, och möter varje annan spelare 1 gång var.
(13,9) kan tas fram som komplement till detta (dvs byt ut alla ettor mot nollor och vice versa).

Jag tror att man kan hitta liknande lösningar för alla (N,m) som uppfyller
N = 1 + m•(m-1)
dvs även för t ex (21,5) och (31,6)...
I alla dessa möter varje spelare varje annan spelare EN gång. Det finns nog också någon regel för lösningar där alla möter varje annan 2 gånger, eller 3 gånger, etc.

----

Btw, vad var det du fann på nätet? Länk kan vara intressant. Kanske inte om exakt samma problem?

Och så finns som sagt alltid en lösning där man helt enkelt tar med alla kombinationer av m spelare. T ex med 13 spelare och 4 kontroller blir detta
(13 över 4) = 715 matcher,
istället för bara 13...

Vad jag minns hade ursprungsproblemet en annan förutsättning, men den kanske har förändrats (till det bättre).