/ Forside / Karriere / Uddannelse / Højere uddannelser / Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn

Kodeord


Reklame
Top 10 brugere
Højere uddannelser
#NavnPoint
Nordsted1 1588
erling_l 1224
ans 1150
dova 895
gert_h 800
molokyle 661
berpox 610
creamygirl 610
3773 570
10  jomfruane 570
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

Søg
Reklame
Statistik
Spørgsmål : 177560
Tips : 31968
Nyheder : 719565
Indlæg : 6408951
Brugere : 218888

Månedens bedste
Årets bedste
Sidste års bedste