På abelkonkurransen del to kom en oppgave der en skulle finne antall ordnede tripler [tex](x,y,z)[/tex] av positive heltall som tilfredsstiller [tex]xyz=500[/tex]. Ettersom [tex]500=2^{2}5^{3}[/tex], blir svaret [tex](3+2+1)(4+3+2+1)=60[/tex]. (Orker ikke skrive hele framgangsmåten, antar de fleste her kjenner til metoden. Hvis ikke, sjekk denne posten (riktignok med andre verdier http://openstudy.com/updates/504d7460e4b0d222920bb465).
Dette går greit, men hva om jeg skal finne antall uordnede tripler? Tenker ikke på oppgaven over spesielt, men generelt. Skal jeg først regne ut antall ordnede tripler, og så trekke fra noe, eller kan jeg sette opp et uttrykk direkte?
PS: Sikkert opplagt, men med ordnet mener jeg at f.eks. [tex](3,6,2)[/tex] og [tex](2,3,6)[/tex] er forskjellige tripler, mens med ordnede er de samme trippel.
Antall uordnede tripler (x,y,z)
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Man må gruppere de uordnede triplene (a,b,c) i klassene
i) $a\neq b$, $a\neq c$, $b\neq c$
ii) a=b, $c\neq a$
iii) a=b=c
Så må man summere antallet tripler av type i) ganget med $3!$, antallet tripler av type ii) ganget med 3, og antallet tripler av type iii)
i) $a\neq b$, $a\neq c$, $b\neq c$
ii) a=b, $c\neq a$
iii) a=b=c
Så må man summere antallet tripler av type i) ganget med $3!$, antallet tripler av type ii) ganget med 3, og antallet tripler av type iii)
Det får jeg ikke til å stemme. Sikker på at du skrev riktig? Dersom jeg klarer å klassifisere de uordnede triplene i gruppene du nevner (i, ii, iii), så kan jeg jo bare summere antallet i hver klasse, og dermed være ferdig (ettersom alle uordnedetripler må være i én av klassene). Trenger derfor ikke gange med noe som helst. Problemet er at jeg ikke ser hvordan jeg skal klare å klassifisere dem.
Situasjonen er som følgende: Et produkt av tre positive heltall er [tex]abc=36[/tex]. Jeg ønsker å finne ut hvor mange forskjellige kombinasjoner av heltall jeg kan lage, der rekkefølgen på tallene ikke spiller noen rolle. Jeg vet svaret er 8 (ved systematisk å sette opp alle mulighetene): [tex](1, 1, 36)/ (1, 2, 18)/ (1, 4, 9)/ (1, 3, 12)/ (2, 2, 9)/ (2, 3, 6)/ (3, 3, 4)/ (1, 6, 6)[/tex]. (Av ordnede tripler blir det [tex](3+2+1)(3+2+1)=36[/tex] stykker). Jeg ønsker altså å vise at det ikke finnes flere muligheter enn disse 8 (selv om jeg ser at det ikke gjør det ved "gjett og sjekk"). How?
Situasjonen er som følgende: Et produkt av tre positive heltall er [tex]abc=36[/tex]. Jeg ønsker å finne ut hvor mange forskjellige kombinasjoner av heltall jeg kan lage, der rekkefølgen på tallene ikke spiller noen rolle. Jeg vet svaret er 8 (ved systematisk å sette opp alle mulighetene): [tex](1, 1, 36)/ (1, 2, 18)/ (1, 4, 9)/ (1, 3, 12)/ (2, 2, 9)/ (2, 3, 6)/ (3, 3, 4)/ (1, 6, 6)[/tex]. (Av ordnede tripler blir det [tex](3+2+1)(3+2+1)=36[/tex] stykker). Jeg ønsker altså å vise at det ikke finnes flere muligheter enn disse 8 (selv om jeg ser at det ikke gjør det ved "gjett og sjekk"). How?
$36=2^23^2$.
Tar utgangspunkt i trippelen (1,1,1), og ser på hvordan man kan fordele primtallsfaktorene til 36 på de tre koordinatene i trippelen.
Uordnede tripler: Enten er begge 2-tallene sammen eller hver for seg, altså enten $(1,2,2)$ eller $(1,1,2^2)$
Tilfellet (1,2,2) gir opphav til 2+2=4 muligheter for å fordele de to 3-tallene.
Tilfellet (1,1,2^2) gir opphav til 2+2=4 muligheter for å fordele de to 3-tallene. Altså totalt 4+4=8 uordnede tripler.
Eksplisitt er alle uordnede tripler
(3^2,2,2) (2,2,9) type ii)
(1,2,23^2) (1,2,18) type i)
(3,2*3,2) (2,3,6) type i)
(1,2*3,2*3) (1,6,6) type ii)
(1,3^2,2^2) (1,4,9) type i)
(1,1,2^23^2) (1,1,36) type ii)
(3,3,2^2) (3,3,4) type ii)
(1,3,2^2*3) (1,3,12) type i)
Det jeg mente i mitt første svar var at man kan gruppere disse uordnede triplene i de tre nevnte klasser, for å så gange dem opp med de nevnte faktorene og ende opp med antallet ordnede tripler, altså motsatt vei av det du siktet til. F.eks. har vi her at det er ingen tripler hvor alle koordinatene er like, mens det er 4 uordnede tripler der to av koordinatene er like, og 4 tripler der alle koordinatene er forskjellige. Altså har vi at 0+4*3+4*3! = 12+24=36 ordnede tripler. (Dette er i seg selv et bevis på at det ikke fins flere enn 8 uordnede tripler: vi vet at antallet ordnede tripler er 36, og hadde det eksistert flere enn 8 uordnede, ville antallet ordnede vært større enn 36 utfra resonnementet over.)
Man kan nå prøve å generalisere til tilfellet $2^p3^q$. Situasjonen blir straks mye verre for uordnede tripler.
La p=2,q=3:
De to 2-tallene kan enten settes i samme koordinat, eller hver for seg, å vi får to typer tripler $(1,1,2^2)$ og $(1,2,2)$.
$(1,1,2^2)$: Det er 3 måter å gruppere de tre 3-tallene på: enten at alle er plassert sammen, to er sammen eller alle er plassert på forskjellige koordinater
- Dersom alle 3-tallene er plassert sammen gir dette opphav til to ulike uordnede tripler $(1,3^3, 2^2)$ og $(1,1,2^23^3)$
- Dersom alle 3-tallene er plassert på forskjellige koordinater gir dette opphav til kun én uordnet trippel: $(3,3,2^23)$
- Dersom to av 3-tallene er i samme koordinat gir dette opphav til 2+1=3 ulike uordnede tripler.
Tar utgangspunkt i trippelen (1,1,1), og ser på hvordan man kan fordele primtallsfaktorene til 36 på de tre koordinatene i trippelen.
Uordnede tripler: Enten er begge 2-tallene sammen eller hver for seg, altså enten $(1,2,2)$ eller $(1,1,2^2)$
Tilfellet (1,2,2) gir opphav til 2+2=4 muligheter for å fordele de to 3-tallene.
Tilfellet (1,1,2^2) gir opphav til 2+2=4 muligheter for å fordele de to 3-tallene. Altså totalt 4+4=8 uordnede tripler.
Eksplisitt er alle uordnede tripler
(3^2,2,2) (2,2,9) type ii)
(1,2,23^2) (1,2,18) type i)
(3,2*3,2) (2,3,6) type i)
(1,2*3,2*3) (1,6,6) type ii)
(1,3^2,2^2) (1,4,9) type i)
(1,1,2^23^2) (1,1,36) type ii)
(3,3,2^2) (3,3,4) type ii)
(1,3,2^2*3) (1,3,12) type i)
Det jeg mente i mitt første svar var at man kan gruppere disse uordnede triplene i de tre nevnte klasser, for å så gange dem opp med de nevnte faktorene og ende opp med antallet ordnede tripler, altså motsatt vei av det du siktet til. F.eks. har vi her at det er ingen tripler hvor alle koordinatene er like, mens det er 4 uordnede tripler der to av koordinatene er like, og 4 tripler der alle koordinatene er forskjellige. Altså har vi at 0+4*3+4*3! = 12+24=36 ordnede tripler. (Dette er i seg selv et bevis på at det ikke fins flere enn 8 uordnede tripler: vi vet at antallet ordnede tripler er 36, og hadde det eksistert flere enn 8 uordnede, ville antallet ordnede vært større enn 36 utfra resonnementet over.)
Man kan nå prøve å generalisere til tilfellet $2^p3^q$. Situasjonen blir straks mye verre for uordnede tripler.
La p=2,q=3:
De to 2-tallene kan enten settes i samme koordinat, eller hver for seg, å vi får to typer tripler $(1,1,2^2)$ og $(1,2,2)$.
$(1,1,2^2)$: Det er 3 måter å gruppere de tre 3-tallene på: enten at alle er plassert sammen, to er sammen eller alle er plassert på forskjellige koordinater
- Dersom alle 3-tallene er plassert sammen gir dette opphav til to ulike uordnede tripler $(1,3^3, 2^2)$ og $(1,1,2^23^3)$
- Dersom alle 3-tallene er plassert på forskjellige koordinater gir dette opphav til kun én uordnet trippel: $(3,3,2^23)$
- Dersom to av 3-tallene er i samme koordinat gir dette opphav til 2+1=3 ulike uordnede tripler.