La [tex]\prod^{1996}_{n=1}(1+nx^{3^n})=1+a_1x^{k_1}+a_2x^{k_2}+...+a_mx^{k_m}[/tex]
Hvor
[tex]a_1,a_2,...,a_m \not = 0, \ k_1<k_2<...<k_m[/tex]
Finn [tex]a_{1996}[/tex]
Produktrekke
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Vi legger merke til at eksponentene til uttrykket vil være alle tall som kan skrives i base 3 uten tallet 2, der enhetssifferet er 0 (opp til [1...10][sub]3[/sub] med 1996 1'ere)
Vi har løst oppgaven dersom vi kan finne det 1996-te tallet som har denne egenskapen. Dette er enkelt og greit - vi finner binærekspansjonen til 1996, og "leser" denne i base 3. Multipliserer vi med 3, har vi eksponenten vi leter etter.
Siden 1996 = [11111001100][sub]2[/sub], vil eksponenten vi er ute etter være [111110011000][sub]3[/sub], og vi ser at koeffisienten som søkes er 3*4*7*8*9*10*11=665280.
Vi har løst oppgaven dersom vi kan finne det 1996-te tallet som har denne egenskapen. Dette er enkelt og greit - vi finner binærekspansjonen til 1996, og "leser" denne i base 3. Multipliserer vi med 3, har vi eksponenten vi leter etter.
Siden 1996 = [11111001100][sub]2[/sub], vil eksponenten vi er ute etter være [111110011000][sub]3[/sub], og vi ser at koeffisienten som søkes er 3*4*7*8*9*10*11=665280.
Sist redigert av daofeishi den 02/03-2008 18:12, redigert 1 gang totalt.
Få se din løsning da! Alltid fint å se ulike tilnærmingsmetoder 
... Hadde vært fint å få på plass en spoilerfunksjon på forumet for å skjule svar...
Edit: Og gratulerer med plass i Abelfinale, Jarle!
... Hadde vært fint å få på plass en spoilerfunksjon på forumet for å skjule svar...
Edit: Og gratulerer med plass i Abelfinale, Jarle!
takk for det
Helt enig med spoilerfunksjonen forresten.
Ok, min løsning:
La [tex]f(t)=\prod^{t}_{n=1}(1+nx^{3^n})[/tex]
Vi finner [tex]f(t)[/tex] for [tex]t=1,2,3,4[/tex]: (Som faktisk er ganske lett til en produktsum å være)
[tex]f(1)=1+x^3[/tex]
[tex]f(2)=1+x^3+2x^9+2x^{12}[/tex]
[tex]f(3)=1+x^3+2x^9+2x^{12}+3x^{27}+3x^{30}+6x^{36}+6x^{39}[/tex]
[tex]f(4)=1+x^3+2x^9+2x^{12}+3x^{27}+3x^{30}+6x^{36}+6x^{39}+4x^{81}+4x^{84}+8x^{90}+8x^{93}+12x^{108}+12x^{111}+24x^{120}[/tex]
Vi observerer mønsteret og kan lage disse formodningene.
(1): Eksponenten til det siste leddet i [tex]f(t)[/tex], er [tex]\frac{3}{2}(3^{t}-1)[/tex]
Bevis:
Det gjelder for [tex]f(1)[/tex]. Anta at det gjelder for alle [tex]k \leq t[/tex]
[tex]f(k+1)=f(k)[1+(k+1)x^{3^{k+1}}]=f(k)+(k+1)f(k)x^{3^{k+1}}[/tex]
Nå blir den høyeste eksponenten [tex]\frac{3}{2}(3^{k}-1)+3^{k+1}=\frac{3}{2}(3^{k+1}-1)[/tex]. Ved induksjon må det gjelde for alle t.
(2): Koeffisienten i summen [tex]f(t)[/tex] blir ikke forandret i [tex]f(t+1)[/tex].
Bevis:
[tex]f(t+1)=f(t)+(t+1)f(t)x^{3^{t+1}}[/tex]
Nå, ettersom [tex]2\cdot 3^t +1 < 3^{t} \Leftrightarrow 3^{t+1}>\frac{3}{2}(3^{t}-1)[/tex], som betyr at hvert ledd i [tex]f(t)[/tex] som ganges med [tex]x^{3^{t+1}}[/tex] får en eksponent høyere enn den største eksponenten i [tex]f(t)[/tex].
I [tex]f(t+1)=f(t)+(t+1)f(t)x^{3^{t+1}}[/tex], blir alle leddene til produktet i det andre leddet ikke lagt til koeffisientene i det første leddet, siden alle eksponentene er høyere.
(3): f(t) har [tex]2^t[/tex] ledd.
Bevis:
Fra (1) så vi at [tex]f(t+1)=f(t)+(t+1)f(t)x^{3^{t+1}}[/tex], og siden ingen koeffisienter til de tilhørige eksponentene av x forandres i [tex]f(t)[/tex], og det adderes like mange ledd i [tex](t+1)f(t)x^{3^{t+1}}[/tex], vil dermed leddene fordobles for hver etterfølgende t. Siden [tex]f(1)[/tex] har 2 ledd, vil [tex]f(t)[/tex] ha [tex]2^t [/tex] ledd.
Siden koeffisientene ikke forandres etter de først har oppstått, vil ikke den øvre grensen på 1996 på produktsummen ha noe å si, så lenge [tex]a_{1996} [/tex]har oppstått.
Siden [tex]2^{10}<1996<2^{11}[/tex], vil dette først skje i [tex]f(11)[/tex].
Etter litt testing med tall, fant jeg ut av dette:
Vi observerer at [tex]1996=2^{10}+2^{9}+2^{8}+2^{7}+2^{6}+12[/tex].
Så la oss se på koeffisienten [tex]a_{12}[/tex] i [tex]f(6)[/tex]. Som en konsekvens av (3), vil koeffisienten [tex]a_r[/tex] i [tex]f(t)[/tex], bli ganget med [tex](t+1)[/tex], og satt [tex]2^t[/tex] plasser lenger ut i rekken, så [tex]a_r(t+1)=a_{r+2^t}. [/tex] På samme måte blir [tex]a_r(t+1)(t+2)=a_{r+2^t+2^{t+1}}[/tex] og [tex]a_r(t+1)(t+2)(t+3)(t+4)(t+5)=a_{r+2^t+2^{t+1}+2^{t+2}+2^{t+3}+2^{t+4}}[/tex]. La nå [tex]r=12,[/tex] og [tex]t=6 \Rightarrow 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot a_{12}=a_{1996}. [/tex] Siden vi i [tex]f(4)[/tex] ser at [tex]a_{12}=12[/tex], så er [tex]a_{1996}=\frac{12!}{6!}=665280[/tex]
Ganske møysommelig altså, men ledet til riktig svar.
Når jeg først prøvde på dette leste jeg ikke eksponenten til å være 3^n, men 3n, så gjett hvem som satt i flere timer og strevde med den..
Helt enig med spoilerfunksjonen forresten.
Ok, min løsning:
La [tex]f(t)=\prod^{t}_{n=1}(1+nx^{3^n})[/tex]
Vi finner [tex]f(t)[/tex] for [tex]t=1,2,3,4[/tex]: (Som faktisk er ganske lett til en produktsum å være)
[tex]f(1)=1+x^3[/tex]
[tex]f(2)=1+x^3+2x^9+2x^{12}[/tex]
[tex]f(3)=1+x^3+2x^9+2x^{12}+3x^{27}+3x^{30}+6x^{36}+6x^{39}[/tex]
[tex]f(4)=1+x^3+2x^9+2x^{12}+3x^{27}+3x^{30}+6x^{36}+6x^{39}+4x^{81}+4x^{84}+8x^{90}+8x^{93}+12x^{108}+12x^{111}+24x^{120}[/tex]
Vi observerer mønsteret og kan lage disse formodningene.
(1): Eksponenten til det siste leddet i [tex]f(t)[/tex], er [tex]\frac{3}{2}(3^{t}-1)[/tex]
Bevis:
Det gjelder for [tex]f(1)[/tex]. Anta at det gjelder for alle [tex]k \leq t[/tex]
[tex]f(k+1)=f(k)[1+(k+1)x^{3^{k+1}}]=f(k)+(k+1)f(k)x^{3^{k+1}}[/tex]
Nå blir den høyeste eksponenten [tex]\frac{3}{2}(3^{k}-1)+3^{k+1}=\frac{3}{2}(3^{k+1}-1)[/tex]. Ved induksjon må det gjelde for alle t.
(2): Koeffisienten i summen [tex]f(t)[/tex] blir ikke forandret i [tex]f(t+1)[/tex].
Bevis:
[tex]f(t+1)=f(t)+(t+1)f(t)x^{3^{t+1}}[/tex]
Nå, ettersom [tex]2\cdot 3^t +1 < 3^{t} \Leftrightarrow 3^{t+1}>\frac{3}{2}(3^{t}-1)[/tex], som betyr at hvert ledd i [tex]f(t)[/tex] som ganges med [tex]x^{3^{t+1}}[/tex] får en eksponent høyere enn den største eksponenten i [tex]f(t)[/tex].
I [tex]f(t+1)=f(t)+(t+1)f(t)x^{3^{t+1}}[/tex], blir alle leddene til produktet i det andre leddet ikke lagt til koeffisientene i det første leddet, siden alle eksponentene er høyere.
(3): f(t) har [tex]2^t[/tex] ledd.
Bevis:
Fra (1) så vi at [tex]f(t+1)=f(t)+(t+1)f(t)x^{3^{t+1}}[/tex], og siden ingen koeffisienter til de tilhørige eksponentene av x forandres i [tex]f(t)[/tex], og det adderes like mange ledd i [tex](t+1)f(t)x^{3^{t+1}}[/tex], vil dermed leddene fordobles for hver etterfølgende t. Siden [tex]f(1)[/tex] har 2 ledd, vil [tex]f(t)[/tex] ha [tex]2^t [/tex] ledd.
Siden koeffisientene ikke forandres etter de først har oppstått, vil ikke den øvre grensen på 1996 på produktsummen ha noe å si, så lenge [tex]a_{1996} [/tex]har oppstått.
Siden [tex]2^{10}<1996<2^{11}[/tex], vil dette først skje i [tex]f(11)[/tex].
Etter litt testing med tall, fant jeg ut av dette:
Vi observerer at [tex]1996=2^{10}+2^{9}+2^{8}+2^{7}+2^{6}+12[/tex].
Så la oss se på koeffisienten [tex]a_{12}[/tex] i [tex]f(6)[/tex]. Som en konsekvens av (3), vil koeffisienten [tex]a_r[/tex] i [tex]f(t)[/tex], bli ganget med [tex](t+1)[/tex], og satt [tex]2^t[/tex] plasser lenger ut i rekken, så [tex]a_r(t+1)=a_{r+2^t}. [/tex] På samme måte blir [tex]a_r(t+1)(t+2)=a_{r+2^t+2^{t+1}}[/tex] og [tex]a_r(t+1)(t+2)(t+3)(t+4)(t+5)=a_{r+2^t+2^{t+1}+2^{t+2}+2^{t+3}+2^{t+4}}[/tex]. La nå [tex]r=12,[/tex] og [tex]t=6 \Rightarrow 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot a_{12}=a_{1996}. [/tex] Siden vi i [tex]f(4)[/tex] ser at [tex]a_{12}=12[/tex], så er [tex]a_{1996}=\frac{12!}{6!}=665280[/tex]
Ganske møysommelig altså, men ledet til riktig svar.
Når jeg først prøvde på dette leste jeg ikke eksponenten til å være 3^n, men 3n, så gjett hvem som satt i flere timer og strevde med den..