Code: Select all
En person skal velge åtte mynter av fem ulike myntsorter: 50 øre, 1, 5, 10, og 20 kr.
a) Hvor mange forskjellige valg fins det?
b) Hvor mange valg er det med høyst to 20 kr. mynter?
(Kombinatorikk) Hvordan løser jeg denne oppgaven?
Moderators: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Øver til eksamen ved å titte på gamle eksamensoppgaver, og kommer ingen vei med denne:
Hvis man tar rekkefølge i betraktning, er det vel 5^8 forskjellige oppstillinger av myntene, men det er vel i oppgavens ånd at man ser på to utvalg hvor antallet av hver mynt er likt, som det samme. Klarer bare å komme meg frem til et svar ved å skrive en liten rekursiv metode i Java, men har en følelse av at det ikke er optimalt...
Enten 1,2,3,4 eller 5 av typene mynter er valgt.
Hvis kun 1 type er valgt er det 5 mulige kombinasjoner
Hvis 2 typer er valgt, f.eks. (n,8-n,0,0,0) er det [tex]\frac{60}{3!}[/tex] mulige måter å plukke ut 2 av 5 på. Hver av disse gir opphav til 7 muligheter så vi får 70 muligheter.
Hvis 3 typer mynter er valgt får vi på samme vis 10 måter å plukke ut 3 av 5 på. Vi har at hver mulighet ser slik ut: (n,m,8-n-m,0,0) der n=1,2,..,6.
n=1 gir at m=1,2,3,4,5,6
n=2 gir at m=1,2,3,4,5
n=3 gir at m=1,2,3,4
n=4 gir at m=1,2,3
n=5 gir at m=1,2
n=6 gir at m=1
Total 6+5+4+3+2+1=21 måter. Vi får derfor 21*10=210 nye muligheter.
Dersom 4 av myntsortene velges har vi 5 måter å plukke ut 4 av 5 på.
(n,m,k,8-n-m-k,0)
La
n=1:
m=1 gir at k=1,2,3,4,5
m=2 gir at k=1,2,3,4
m=3 gir at k=1,2,3
etc.
Totalt 5+4+3+2+1=15
La n=2:
m=1 gir k=1,2,3,4
etc.
Totalt 4+3+2+1=10
Fortsetter vi får vi 3+2+1=6, 2+1=3, 1
Totalt 15+10+6+3+1=35 muligheter. Ganger vi dette med 5 får vi 175 nye muligheter.
For 5 typer mynter er (n,m,k,l,8-n-m-k-l)
n=1,m=1:
k=1 gir at l=1,2,3,4
k=2 gir at l=1,2,3
etc.
Totalt 4+3+2+1=10
n=1,m=2:
k=1 gir at l=1,2,3
k=2 gir at l=1,2
etc.
Totalt 3+2+1=6
Fortsetter vi slik får vi for n=1 totalt 10+6+3+1=20 muligheter
Vi ser at det totalt blir 20+10+4+1=35 muligheter dersom vi velger ut alle 5 myntsortene.
Tilsammen blir det 5+70+210+175+35=495 ifølge mine beregninger
EDIT: Rettet på en slurvefeil. Samme svar som Fish ja:)
Hvis kun 1 type er valgt er det 5 mulige kombinasjoner
Hvis 2 typer er valgt, f.eks. (n,8-n,0,0,0) er det [tex]\frac{60}{3!}[/tex] mulige måter å plukke ut 2 av 5 på. Hver av disse gir opphav til 7 muligheter så vi får 70 muligheter.
Hvis 3 typer mynter er valgt får vi på samme vis 10 måter å plukke ut 3 av 5 på. Vi har at hver mulighet ser slik ut: (n,m,8-n-m,0,0) der n=1,2,..,6.
n=1 gir at m=1,2,3,4,5,6
n=2 gir at m=1,2,3,4,5
n=3 gir at m=1,2,3,4
n=4 gir at m=1,2,3
n=5 gir at m=1,2
n=6 gir at m=1
Total 6+5+4+3+2+1=21 måter. Vi får derfor 21*10=210 nye muligheter.
Dersom 4 av myntsortene velges har vi 5 måter å plukke ut 4 av 5 på.
(n,m,k,8-n-m-k,0)
La
n=1:
m=1 gir at k=1,2,3,4,5
m=2 gir at k=1,2,3,4
m=3 gir at k=1,2,3
etc.
Totalt 5+4+3+2+1=15
La n=2:
m=1 gir k=1,2,3,4
etc.
Totalt 4+3+2+1=10
Fortsetter vi får vi 3+2+1=6, 2+1=3, 1
Totalt 15+10+6+3+1=35 muligheter. Ganger vi dette med 5 får vi 175 nye muligheter.
For 5 typer mynter er (n,m,k,l,8-n-m-k-l)
n=1,m=1:
k=1 gir at l=1,2,3,4
k=2 gir at l=1,2,3
etc.
Totalt 4+3+2+1=10
n=1,m=2:
k=1 gir at l=1,2,3
k=2 gir at l=1,2
etc.
Totalt 3+2+1=6
Fortsetter vi slik får vi for n=1 totalt 10+6+3+1=20 muligheter
Vi ser at det totalt blir 20+10+4+1=35 muligheter dersom vi velger ut alle 5 myntsortene.
Tilsammen blir det 5+70+210+175+35=495 ifølge mine beregninger
EDIT: Rettet på en slurvefeil. Samme svar som Fish ja:)
Last edited by Gustav on 08/06-2009 11:50, edited 1 time in total.
Dette blir vel antall uordnede utvalg med tilbakelegging når vi velger 8 fra en mengde på 5 objekter.
Det bør da bli [tex]{8+5-1\choose 8}=495[/tex] mulige valg.
Hvis vi krever høyst to tjuere, får vi
[tex]{8+4-1\choose 8}+{7+4-1\choose 7}+{6+4-1\choose 6}=369[/tex] muligheter.
Det bør da bli [tex]{8+5-1\choose 8}=495[/tex] mulige valg.
Hvis vi krever høyst to tjuere, får vi
[tex]{8+4-1\choose 8}+{7+4-1\choose 7}+{6+4-1\choose 6}=369[/tex] muligheter.
Ah. Nå fant jeg akkurat en post med samme type problem som del a) litt lenger bakover i forumet også, men takk skal du ha. Jeg kom frem til samme tallet med java-programmet mitt, som regnet det ut rekursivt omtrent som plutarco beskriver. Men det er jo litt greiere å kunne en formel for det, og jeg kan jo ikke akkurat begynne å programmere under en matteeksamen. Etter å ha tenkt litt skjønner jeg hva du vil frem til i den andre delen også (høyst to tjuere). Tusen takk :)