10 svar
411 visningar
Dunderklumpen 51 – Fd. Medlem
Postad: 11 feb 2017 11:25 Redigerad: 25 apr 2022 12:05

Kluring #2

n stycken personer samlas för att spela ett spel som kräver att k personer spelar med varandra per omgång.

Vad är det minsta antalet spelomgångar för att var person skall ha spelat minst en omgång med alla andra?

Affe Jkpg 6630
Postad: 11 feb 2017 13:08

Låt oss säga att k personer är ett fotbollslag!

Antal fotbollslag skriver vi som

m=nk

När man gör ett spelschema gör man ett rutmönster m*m rutor stort

Alla lag möter varandra både borta och hemma i detta rutmönster och så blir det en diagonal med m rutor där så att säga laget möter sig själv.

Vi skriver antalet spelomgångar med bokstaven O

Ofotboll=m2-m

I detta fall är det ju inte både hemma- och borta-spelomgång

Sedan ska ju spelarna möta sig själva också

Vi får då:

O=12(m2-m) +mO=12(m2+m)Vi provar med något enkel fall:n=4k=2m=nk=2O=12(22+2)=3

Dunderklumpen 51 – Fd. Medlem
Postad: 11 feb 2017 13:53
Affe Jkpg skrev :

Låt oss säga att k personer är ett fotbollslag!

Antal fotbollslag skriver vi som

m=nk

När man gör ett spelschema gör man ett rutmönster m*m rutor stort

Alla lag möter varandra både borta och hemma i detta rutmönster och så blir det en diagonal med m rutor där så att säga laget möter sig själv.

Vi skriver antalet spelomgångar med bokstaven O

Ofotboll=m2-m

I detta fall är det ju inte både hemma- och borta-spelomgång

Sedan ska ju spelarna möta sig själva också

Vi får då:

O=12(m2-m) +mO=12(m2+m)Vi provar med något enkel fall:n=4k=2m=nk=2O=12(22+2)=3

 Valiant effort. Tyvärr inte vad jag syftar på.

Jag tänker mig så här:

4 personer, vi kallar dem (A, B, C, D) sitter och spelar Steet Fighter, 2 personer kan spela samtidigt. För att alla skall ha mött alla i en match behöver omgångarna vara följande.

(A,B) (A,C) (A,D) (B,C) (B,D) (C,D) för totalt 6 omgångar.

tomast80 4245
Postad: 11 feb 2017 14:10

Det behövs minst nk omgångar.

pbadziag 75 – Fd. Medlem
Postad: 11 feb 2017 14:20

Har inget bevis att strategin är den optimala, men det kan du försöka som nästa steg: 

Dela n i p=2n/k grupper med k/2 deltagare i en grupp. Den sista gruppen kan bli mindre. Låt sedan grupperna paras med varandra i 

p(p-1)/2

omgångar. Den mindre gruppen skall då kompletteras med spelare från andra "lag" än deras föreskrivna partnergrupp. Strategin tyck funka när n inte är för stort.

Dunderklumpen 51 – Fd. Medlem
Postad: 11 feb 2017 14:38 Redigerad: 11 feb 2017 15:55
tomast80 skrev :

Det behövs minst nk omgångar.

Det stämmer inte. Om n=5 och k=3 kan man göra följande:


Alla deltagare:(A,B,C,D,E)

Nädvändiga omgångar: (A,B,C) (C,D,E) (A,B,D) (B,D,E) (A,B,E) altså 5st.

 

Edit: Det stämmer då k=2.

Dunderklumpen 51 – Fd. Medlem
Postad: 11 feb 2017 15:02 Redigerad: 11 feb 2017 15:03
pbadziag skrev :

Har inget bevis att strategin är den optimala, men det kan du försöka som nästa steg: 

Dela n i p=2n/k grupper med k/2 deltagare i en grupp. Den sista gruppen kan bli mindre. Låt sedan grupperna paras med varandra i 

p(p-1)/2

omgångar. Den mindre gruppen skall då kompletteras med spelare från andra "lag" än deras föreskrivna partnergrupp. Strategin tyck funka när n inte är för stort.

 Formeln fungerar defenitivt så länge som k=2, men annars verkar den falla samman.

Affe Jkpg 6630
Postad: 11 feb 2017 15:11

Jaha det var ett litet fotbollslag med endast en spelare :-)

När man gör ett spelschema gör man ett rutmönster n*n rutor stort

Alla lag möter varandra både borta och hemma i detta rutmönster och så blir det en diagonal med n rutor där så att säga laget möter sig själv.

Vi skriver antalet spelomgångar med bokstaven O

Ofotboll=n2-n

I detta fall är det ju inte både hemma- och borta-spelomgång

O= 12 ( n2 n)

Provar vi igen:

n=4

O=12(42-4)=6

Dunderklumpen 51 – Fd. Medlem
Postad: 11 feb 2017 16:16
Affe Jkpg skrev :

Jaha det var ett litet fotbollslag med endast en spelare :-)

När man gör ett spelschema gör man ett rutmönster n*n rutor stort

Alla lag möter varandra både borta och hemma i detta rutmönster och så blir det en diagonal med n rutor där så att säga laget möter sig själv.

Vi skriver antalet spelomgångar med bokstaven O

Ofotboll=n2-n

I detta fall är det ju inte både hemma- och borta-spelomgång

O= 12 ( n2 n)

Provar vi igen:

n=4

O=12(42-4)=6

 Formeln stämmer mycket riktigt, men bara då k=2.

gusK 25 – Fd. Medlem
Postad: 11 feb 2017 19:33
Dunderklumpen skrev :
tomast80 skrev :

Det behövs minst nk omgångar.

Det stämmer inte. Om n=5 och k=3 kan man göra följande:


Alla deltagare:(A,B,C,D,E)

Nädvändiga omgångar: (A,B,C) (C,D,E) (A,B,D) (B,D,E) (A,B,E) altså 5st.

 

Edit: Det stämmer då k=2.

 Det scenario du skriver om här är felaktigt då (B,D,E) inte behövs efter som alla dessa är med i en annan omgång. Rätt svar borde då vara 4?

Dunderklumpen 51 – Fd. Medlem
Postad: 11 feb 2017 19:38
gusK skrev :
Dunderklumpen skrev :
tomast80 skrev :

Det behövs minst nk omgångar.

Det stämmer inte. Om n=5 och k=3 kan man göra följande:


Alla deltagare:(A,B,C,D,E)

Nädvändiga omgångar: (A,B,C) (C,D,E) (A,B,D) (B,D,E) (A,B,E) altså 5st.

 

Edit: Det stämmer då k=2.

 Det scenario du skriver om här är felaktigt då (B,D,E) inte behövs efter som alla dessa är med i en annan omgång. Rätt svar borde då vara 4?

 

Ah. Det stämmer.

Svara
Close