Matematik

Kombinationer

10. august 2007 af DeciMat (Slettet)

Nu er det gået i sort igen. Til tider ligner jeg en comp. der får virus.

På en brat 8*8 er der tegnet kvadratter 1*1 og i hver kvadrats centrum er der tegnet et punkt. Man skal finde ud af på hvor mange måder man kan komme fra den ene kvadrets centrum til de andres centrum. Men må ikke gå den samme VEJ to gange.

Jeg tænker: for at det skal være en vej, så går man f.eks. fra 1-2, 1-3, ...1-8. Hvor 1 alene ikke kan være en vej; altså 7 veje. Det samme fremgangmåde gælder 2, 3, ...8.
Ergo må der være 8*(8-1) veje i alt. Sæt i formel n(n-1)
Passer det eller er jeg igen efter noget som ikke findes?

Tak for all hjælp jeg kan få.

DeciMat

Brugbart svar (0)

Svar #1
10. august 2007 af Erik Morsing (Slettet)

jeg får 61, kontrollerer lige igen.

Brugbart svar (0)

Svar #2
10. august 2007 af Erik Morsing (Slettet)

Nej 63, rigtigt, brug et skakbræt

Svar #3
10. august 2007 af DeciMat (Slettet)

Ok, nu er klappen blevet tykkere.
Jeg tæller for
1 til andre 7 veje
2 til andre 7 veje
...
...
8 til andre 7 veje

i alt 8*(8-1) = 8*7= 56
veje, da der kan ikke være en "vej" altså en længde til samme kvadrats centrum . Med andre ord antal veje 8^2=64 minus de 8 "ingen veje" (1 til 1 ingen vej, 2 til 2 ingen vej osv..) Derfor 8^2-8=64-8 =56
n^2-n eller n(n-1)

Hvor er det jeg tager fejl? Er mit spørgsmål utvetydigt?

DeciMat

Brugbart svar (0)

Svar #4
10. august 2007 af Erik Morsing (Slettet)

Jeg tog faktisk bare mit skakbræt og spadserede en tur, kigger lige på dit.

Svar #5
10. august 2007 af DeciMat (Slettet)

Lind, sheaf, daniel, Rasmussen og stræberpigen hvor er I? I skal altså hjælpe inden jeg begynder at rive mig i håret. Og der er altså ikke ret meget tilbage :)
(af håret altså)

DeciMat

Brugbart svar (0)

Svar #6
10. august 2007 af Billal001 (Slettet)

#5 Haha :D

Brugbart svar (0)

Svar #7
10. august 2007 af Erik Morsing (Slettet)

Hvis vi regner det ene hjørne for lige så god som det andet, da de jo ikke er nummererede, så kan du jo bare spadsere turen. Forestil dig, at det er så stort, at du kan gå på det. Nu tegner du en plet, der hvor du har været, og når alle felter er plettede netop een gang, så er du færdig. Ellers har jeg ikke forstået spørgsmålet.

Svar #8
10. august 2007 af DeciMat (Slettet)

Ja, jeg kan se at spørgsmålet ikke er helt korrekt. Således, min måde at gribe til løsning. Hvis jeg skla forestille mig at gå på det, så kan jeg gå fra 1 til samtlige andre på 63 forskellige måder. Det samme fra 2, 3 ...8. Så må svaret være. 8*63 sæt i formel 8*(8^2-1)=n(n^2-1)=n*n^2-n
Hvilket betyder på 504 forskellige måder. Nu lyder som rigtigt.

Tak for hjælpen.

DeciMat

Brugbart svar (0)

Svar #9
10. august 2007 af Erik Morsing (Slettet)

#8
Jeg antager, at felterne er fuldstændig identiske, så er det ligegyldigt, hvor du starter. Hvis de var nummererede, som du nu har gjort, ja så er det en anden sag. Jeg regnede med, at du søgte det mindste tal, for hvilket du kunne nå alle felter uden at krydse noget felt mere end en gang. Jeg kommer til at tænke på Königsberg broerne, kender du det problem?

Brugbart svar (0)

Svar #10
11. august 2007 af sheaf (Slettet)

Det vil jeg slet ikke indlade mig på for opgaven er ikke klart formuleret: Er der tale om disjunkte ture (eneste fællespunkter er start- og slutpunkt), parvist disjunkte ture eller kant-disjunkte ture (ingen ture har en kant tilfælles). Det er heller ikke klart hvordan turene kan forgår: parallelt med kvadraternes sider, diagonalt, ...

I det simplest tænkelige tilfælde kan man tænke sig opstillingen repræsenteret ved en graf i hvilken ethvert af de 64 centre er et punkt og nabopunkter forbundet med en kant repræsenterende en vej imellem dem.

Vælg vilkårlige punkter a og b i grafen.

Et kantsnit er en mængde af kanter der fjerner enhver forbindelse mellem a og b. Det mindste antal kanter der opfylder dette kaldes k(a,b).

Det største antal kant-disjunkte veje (d.v.s. ingen af disse veje har en fælles kant) mellem a og b kaldes v(a,b).

Der findes en grafteoretisk algoritme der kan bestemme k(a,b) og til alt held findes en sætning der hedder Menger's sætning som siger, at for vilkårlige punkter i enhver graf er v(a,b) = l(a,b).

Prøv at google på max flow min cut algorithm.

Skriv et svar til: Kombinationer

Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk? Klik her for at oprette en bruger.