|
| Antal kombinationer i Kryds & Bolle Fra : Brian Fisker |
Dato : 18-02-02 10:33 |
|
Beklager, hvis dette er forkert forum...
Men lige et hurtigt spørgsmål til "den lille matematiker".
Hvor mange forskellige kombinationer, kan de tre krydser og de tre
boller placeres i Kryds & Bolle? Rækkefølgen af krydsene indbyrdes og
bollerne indbyrdes har ingen betydning.
Mvh
Brian
| |
Torben Ægidius Mogen~ (18-02-2002)
| Kommentar Fra : Torben Ægidius Mogen~ |
Dato : 18-02-02 13:24 |
|
"Brian Fisker" <Roye@kom.auc.dk> writes:
> Beklager, hvis dette er forkert forum...
>
> Men lige et hurtigt spørgsmål til "den lille matematiker".
>
> Hvor mange forskellige kombinationer, kan de tre krydser og de tre
> boller placeres i Kryds & Bolle? Rækkefølgen af krydsene indbyrdes og
> bollerne indbyrdes har ingen betydning.
Den naive løsning:
Der er ni felter, som hver kan være blank, kryds eller bolle. Det
giver 3^9 = 19683 muligheder.
Det passer dog ikke helt på reglerne af spillet, da kryds og bolle
bliver sat skiftevis. Derfor kan der højest være en forskel på 1 i
antallet af krydser og boller. Efter N>0 træk, vil der være enten
ned(N/2) krydser og op(N/2) boller eller omvendt (hvor ned() og op()
hhv. runder ned og op). Hvis N er lige er der ingen forskel på de to
muligheder, så det er bedst at adskille de to muligheder mens man
tæller.
N=2M (M=0..4): placer M krydser i 9 felter og derefter M boller i de
resterende (9-M) felter: K(9,M)*K(9-M,M), hvor K(x,y) = x!/y!/(x-y)!.
Ialt altså
sum fra M=0 til 4 af K(9,M)*K(9-M,M) = 3139
For ulige N, dvs. N=2M+1 er der symmetrisk enten 1 flere krydser end
boller eller 1 mere boller end krydser. Vi antager det første og
ganger med to bagefter:
2*(sum fra M=0 til 4 af K(9,M+1)*K(9-M-1,M)) = 2*2907 = 5814
Ialt giver det 8953 muligheder, altså mindre end halvdelen af den
naive løsning.
Men det er ikke helt godt nok endnu: Spillet slutter så snart der er
tre på linie. Vi kan altså ikke tælle kombinationer med, hvor der er
tre på linie to eller flere steder. Det bliver kompliceret at stille
dette op som kombinatoriske formler, så det er nemmere at lave et
lille program, der prøver samtlige kombinationer af krydser og boller
og smider de ulovlige væk. Det giver ialt 8681 muligheder.
Nu ser jeg lige, at du allerede har begrænset dig til præcis tre
krydser og tre boller, uden begrænsninger for placering (så det kan
godt give to linier). Du får det direkte ved at indsætte M=3 i
K(9,M)*K(9-M,M), altså 1680.
Torben Mogensen (torbenm@diku.dk)
| |
Anders Borum (18-02-2002)
| Kommentar Fra : Anders Borum |
Dato : 18-02-02 20:30 |
|
"Torben Ægidius Mogensen" <torbenm@sjofn.diku.dk> skrev i en meddelelse
news:w5zo272d2x.fsf@sjofn.diku.dk...
> "Brian Fisker" <Roye@kom.auc.dk> writes:
[klip]
> Nu ser jeg lige, at du allerede har begrænset dig til præcis tre
> krydser og tre boller, uden begrænsninger for placering (så det kan
> godt give to linier). Du får det direkte ved at indsætte M=3 i
> K(9,M)*K(9-M,M), altså 1680.
Hvad hvis man vil ikke vil skelne mellem kombinationer som kan
roteres eller spejles over i hinanden. Hvad bliver tallet hvis man
udnytter Polyas tælleformel?
Hilsen Anders
| |
Ingolf (20-02-2002)
| Kommentar Fra : Ingolf |
Dato : 20-02-02 18:23 |
|
"Torben Ægidius Mogensen" <torbenm@sjofn.diku.dk> wrote in message
news:w5zo272d2x.fsf@sjofn.diku.dk...
> "Brian Fisker" <Roye@kom.auc.dk> writes:
>
> > Beklager, hvis dette er forkert forum...
> >
> > Men lige et hurtigt spørgsmål til "den lille matematiker".
> >
> > Hvor mange forskellige kombinationer, kan de tre krydser og de tre
> > boller placeres i Kryds & Bolle? Rækkefølgen af krydsene indbyrdes og
> > bollerne indbyrdes har ingen betydning.
>
> Den naive løsning:
>
> Der er ni felter, som hver kan være blank, kryds eller bolle. Det
> giver 3^9 = 19683 muligheder.
>
> Det passer dog ikke helt på reglerne af spillet, da kryds og bolle
> bliver sat skiftevis. Derfor kan der højest være en forskel på 1 i
> antallet af krydser og boller. Efter N>0 træk, vil der være enten
> ned(N/2) krydser og op(N/2) boller eller omvendt (hvor ned() og op()
> hhv. runder ned og op). Hvis N er lige er der ingen forskel på de to
> muligheder, så det er bedst at adskille de to muligheder mens man
> tæller.
>
> N=2M (M=0..4): placer M krydser i 9 felter og derefter M boller i de
> resterende (9-M) felter: K(9,M)*K(9-M,M), hvor K(x,y) = x!/y!/(x-y)!.
> Ialt altså
>
> sum fra M=0 til 4 af K(9,M)*K(9-M,M) = 3139
>
> For ulige N, dvs. N=2M+1 er der symmetrisk enten 1 flere krydser end
> boller eller 1 mere boller end krydser. Vi antager det første og
> ganger med to bagefter:
>
> 2*(sum fra M=0 til 4 af K(9,M+1)*K(9-M-1,M)) = 2*2907 = 5814
>
> Ialt giver det 8953 muligheder, altså mindre end halvdelen af den
> naive løsning.
>
Que?
Det var dog en afsindig lang udregning for noget så enkelt!
Der er ialt 9 felter på spillepladen. Hver spiller har 3 brikker/ture.
Første spiller har 9 muligheder...
Anden spiller har 8 muligheder...
Første spiller har 7 muligheder...
Anden spiller har 6 muligheder...
Første spiller har 5 muligheder...
Anden spiller har 4 muligheder.
Og nu er spillet slut.
Ergo er 9*8*7*6*5*4 = 60.480 muligheder.
| |
Rune Zedeler (21-02-2002)
| Kommentar Fra : Rune Zedeler |
Dato : 21-02-02 19:23 |
|
Ingolf wrote:
> Ergo er 9*8*7*6*5*4 = 60.480 muligheder.
Nej, han sagde, at rækkefølgen var ligegyldig.
Med din metode vil den samme opstilling blive talt med flere gange, da
den kan være nået "på forskellig måde".
-Rune
| |
Henning Præstegaard (21-02-2002)
| Kommentar Fra : Henning Præstegaard |
Dato : 21-02-02 20:50 |
|
"Ingolf" <DoNot_Spam_ingolf@musling.dk> skrev i en meddelelse
> Og nu er spillet slut.
> Ergo er 9*8*7*6*5*4 = 60.480 muligheder.
>
Njaa. Så langt behøver men ikke at gå.
I kryds & bolle med 9 felter og tre brikker er det
altid den der starter der vinder.
mvh
Henning
| |
Lasse Reichstein Nie~ (21-02-2002)
| Kommentar Fra : Lasse Reichstein Nie~ |
Dato : 21-02-02 22:12 |
|
"Henning Præstegaard" <uncle@get2net.dk> writes:
> I kryds & bolle med 9 felter og tre brikker er det
> altid den der starter der vinder.
Der er ingen vindende strategi i kryds og bolle, så
det er forkert at sige at det er den der starter der
vinder. Hvis begge spillere spiller optimalt, så er
der ingen vinder.
/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgment merely degrades the spirit divine.'
| |
Henning Præstegaard (22-02-2002)
| Kommentar Fra : Henning Præstegaard |
Dato : 22-02-02 21:18 |
|
"Lasse Reichstein Nielsen" <lrn@hotpop.com> skrev i en meddelelse
>
> Der er ingen vindende strategi i kryds og bolle, så
> det er forkert at sige at det er den der starter der
> vinder. Hvis begge spillere spiller optimalt, så er
> der ingen vinder.
>
Det kommer vist an på hvilke regler du hentyder til.
(som jeg ikke kender)
Hvis man efter at have sat tre brikker og så må flytte, vil
den der starter vinde, hvis den der starter holder sig til hjørnerne.
Så vil dar altid komme en række frem som modstanderen ikke kan dække.
mvh
Henning
| |
Brian Axelgaard (22-02-2002)
| Kommentar Fra : Brian Axelgaard |
Dato : 22-02-02 22:55 |
|
Der er forskellige regler til kryds og bolle! Der er nogle som spiller med
at man ikke må flytte sin brik over en anden brik, man må faktisk kun flytte
den et felt ad gangen... så varer spillet sjældent længe.
Den version jeg selv spiller må man praktisk talt alt. Dog har jeg aldrig
hørt om en vinder taktik, kun hvis man spiller mod n00b´s, det er seævf.
sjovt nok en gang i mellem.
Findes der ikke en K&B-Klub i DK...
Jeg fandt for nyligt ud af at der lige frem findes en liga for skak.... sygt
nok, man kan oddse på det og det hele. Det var sgu anledning til dagens gode
grin her hjemme :)
| |
Rune Zedeler (25-02-2002)
| Kommentar Fra : Rune Zedeler |
Dato : 25-02-02 16:58 |
|
"Henning Præstegaard" wrote:
> Hvis man efter at have sat tre brikker og så må flytte, vil
> den der starter vinde, hvis den der starter holder sig til hjørnerne.
> Så vil dar altid komme en række frem som modstanderen ikke kan dække.
Hvordan det?
X
---
X
O
---
X
O
X
---
X
OO
X
---
X
OOX
X
---
XO
OOX
X
Eller:
X
---
X
O
---
X
O
X
---
X
OO
X
---
X
OOX
X
---
X O
OOX
X
-Rune
| |
|
|