IMO-longlist 1989 oppg.9
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
La [tex]f(m)[/tex] være antallet toer-faktorer i [tex]m![/tex] ([tex]f(m)[/tex] er det største tallet [tex]k[/tex] slik at [tex]2^k \mid m![/tex]). Vis at det finnes uendelig mange positive heltall [tex]m[/tex] slik at [tex]m-f(m)=1989[/tex].
-
mrcreosote
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
Tallet m kan skrives unikt som
[tex]m=\sum_{i\ge0} m_i2^i[/tex] der [tex]m_i\in\{0,1\}[/tex]; binærformen til m.
Observer at produktet av 2^k påfølgende positive heltall inneholder nøyaktig 2^k-1 faktorer 2 hvis det første er kongruent med 1 modulo 2^{k+1}. Derfor vil antall faktorer 2 i m være
[tex]f(m)=\sum_{i\ge0} m_i(2^i-1)=m-\sum_{i\ge0} m_i[/tex]
Følgelig er m-f(m) antall 1-ere i binærrepresentasjonen av m, så alle tall som har nøyaktig 1989 1-ere når de er skrevet på binærform vil oppfylle ligninga.
[tex]m=\sum_{i\ge0} m_i2^i[/tex] der [tex]m_i\in\{0,1\}[/tex]; binærformen til m.
Observer at produktet av 2^k påfølgende positive heltall inneholder nøyaktig 2^k-1 faktorer 2 hvis det første er kongruent med 1 modulo 2^{k+1}. Derfor vil antall faktorer 2 i m være
[tex]f(m)=\sum_{i\ge0} m_i(2^i-1)=m-\sum_{i\ge0} m_i[/tex]
Følgelig er m-f(m) antall 1-ere i binærrepresentasjonen av m, så alle tall som har nøyaktig 1989 1-ere når de er skrevet på binærform vil oppfylle ligninga.
Morsomt problem.
Vi observerer at [tex]f(m) = \sum^{\infty}_{i=1} \lfloor \frac{m}{2^i} \rfloor [/tex] ettersom vi teller over antall faktorer i [tex]m![/tex], dvs. antall multipler av [tex]2, 4, 8,...[/tex] osv. som eksisterer i tallfølgen [tex]1,2,...,m[/tex]. Denne har naturlig en øvre grense på [tex]i=n[/tex] hvor n er det største tallet slik at [tex]2^n \leq m[/tex] Da får vi [tex]f(m)= \sum^{n}_{i=1} \lfloor \frac{m}{2^i} \rfloor.[/tex]
La [tex]g(m):=m-f(m).[/tex]
Etter litt eksperimentering med [tex]f(m)[/tex] og [tex]g(m)[/tex] for [tex]m[/tex] fra [tex]1[/tex] til [tex]32[/tex] gir oss noen egenskaper til [tex]g(m)[/tex] vi vil prøve å bevise:
For alle ikke-negative [tex]r[/tex]:
[tex](1): g(2^r)=1[/tex]
[tex](2): g(2^r-1)=r [/tex]
[tex](3): g(m+1)-g(m) \leq 1[/tex]
Anta at disse er riktige. (vi beviser dem senere)
Siden [tex]g(2^r-1)=r[/tex] ser vi at [tex]g(m)[/tex] ikke har noen øvre grense.
Siden [tex]g(m+1)-g(m) \leq 1[/tex] vil aldri [tex]g(m)[/tex] "hopper over" noen heltall etter hvert som den vokser.
Derfor kan vi si at siden [tex]g(2^r)=1[/tex], ser vi at [tex]g(m)[/tex] alltid vil "falle tilbake" til [tex]1[/tex], og når [tex]m[/tex] etter hvert vokser til [tex]2^{r+1}-1[/tex], må [tex]g(m)[/tex] ha vokst til [tex]r+1[/tex], som vi har fra (2). Dette skjer uten å hoppe over noen heltall underveis, ettersom [tex]g(m+1)-g(m) \leq 1[/tex]. Dette betyr at [tex]g(m)[/tex] vil "passere" ethvert positivt heltall under [tex]r+1[/tex] mellom [tex]m=2^{r}[/tex] og [tex]m=2^{r+1}[/tex]. Det vil si at [tex]g(m)=1989[/tex] (eller [tex]2008[/tex] for den saks skyld) et uendelig antall ganger.
Jeg håper det ikke var noe uklart der.
Her kommer bevisene:
[tex](1): g(2^r)=1[/tex]
Vi beviser det ved å bruke at [tex]f(m) = \sum^{n}_{i=1} \lfloor \frac{m}{2^i} \rfloor [/tex].
[tex]f(2^r)=\sum^{n}_{i=1} \lfloor \frac{2^r}{2^i} \rfloor =\sum^{n}_{i=1} \lfloor 2^{r-i} \rfloor[/tex]. Etter definisjonen av [tex]n[/tex], ser vi at [tex]n=r[/tex], og vi får at [tex]f(2^r)=\sum^{r}_{i=1} \lfloor 2^{r-i} \rfloor[/tex]
Men [tex]2^{r-i}[/tex] er et heltall for alle [tex]r-i \geq 0[/tex], dvs. [tex]r \geq i[/tex], og dette er alltid sant siden [tex]i[/tex] har en øvre grense [tex]r[/tex]. Da får vi videre at [tex]f(2^r)=\sum^{r}_{i=1} 2^{r-i}=2^{r+1}\sum^{r}_{i=1} (\frac{1}{2})^{i-1}=2^{r+1}(\frac{1-2^{-r}}{2})=2^r-1[/tex].
Da har vi at [tex]g(2^r)=2^r-f(2^r)=2^r-(2^r-1)=1.[/tex]
Dermed er [tex](1)[/tex] bevist.
[tex](2): g(2^r-1)=r[/tex]
Vi bruker samme metode:
[tex]f(2^r-1)=\sum^{n}_{i=1} \lfloor \frac{2^{r}-1}{2^i} \rfloor =\sum^{n}_{i=1} \lfloor 2^{r-i}-(\frac{1}{2})^i \rfloor[/tex]
I dette tilfellet er [tex]n=r-1[/tex]. Det betyr at [tex]2^{r-i}[/tex] sin laveste verdi er [tex]2[/tex], og at det er alltid et heltall.
[tex](\frac{1}{2})^i[/tex] er derimot alltid mellom [tex]0[/tex] og [tex]1[/tex], og siden for positivt heltall [tex]p[/tex], og [tex]0<q<1: \ \lfloor p-q \rfloor=p-1[/tex], har vi at [tex]\lfloor 2^{r-i}-(\frac{1}{2})^i \rfloor=2^{r-i}-1[/tex].
Det gir oss at [tex] f(2^r-1)=\sum^{r-1}_{i=1} 2^{r-i}-1=2^{r+1}[\sum^{r-1}_{i=1} (\frac{1}{2})^{i-1}]-(r-1)=2^{r+1}(\frac{1-2^{1-r}}{2})-(r-1)=(2^r-2)-(r-1)=2^r-1-r[/tex]
Da har vi at [tex]g(2^r-1)=(2^r-1)-f(2^r-1)=2^r-1-(2^r-1-r)=r[/tex].
Dermed er [tex](2)[/tex] bevist.
[tex](3): g(m+1)-g(m) \leq 1[/tex]
Et forholdsvis lett og rett-fram bevis:
Naturlig nok er:
[tex]f(m+1) \geq f(m) \\ \Leftrightarrow f(m)-f(m+1) \leq 0 \\ \Leftrightarrow [(m+1)-f(m+1)]-[m-f(m)] \leq 1 \\ \Leftrightarrow g(m+1)-g(m) \leq 1[/tex].
Dermed er [tex](3)[/tex] bevist, og sammen med [tex](1)[/tex] og [tex](2)[/tex] beviser det at [tex]m-f(m)=1989[/tex] har et uendelig antall løsninger.
EDIT: Der kom mrcreo meg i forkjøpet med et kortere og litt mer elegant bevis.
Vi observerer at [tex]f(m) = \sum^{\infty}_{i=1} \lfloor \frac{m}{2^i} \rfloor [/tex] ettersom vi teller over antall faktorer i [tex]m![/tex], dvs. antall multipler av [tex]2, 4, 8,...[/tex] osv. som eksisterer i tallfølgen [tex]1,2,...,m[/tex]. Denne har naturlig en øvre grense på [tex]i=n[/tex] hvor n er det største tallet slik at [tex]2^n \leq m[/tex] Da får vi [tex]f(m)= \sum^{n}_{i=1} \lfloor \frac{m}{2^i} \rfloor.[/tex]
La [tex]g(m):=m-f(m).[/tex]
Etter litt eksperimentering med [tex]f(m)[/tex] og [tex]g(m)[/tex] for [tex]m[/tex] fra [tex]1[/tex] til [tex]32[/tex] gir oss noen egenskaper til [tex]g(m)[/tex] vi vil prøve å bevise:
For alle ikke-negative [tex]r[/tex]:
[tex](1): g(2^r)=1[/tex]
[tex](2): g(2^r-1)=r [/tex]
[tex](3): g(m+1)-g(m) \leq 1[/tex]
Anta at disse er riktige. (vi beviser dem senere)
Siden [tex]g(2^r-1)=r[/tex] ser vi at [tex]g(m)[/tex] ikke har noen øvre grense.
Siden [tex]g(m+1)-g(m) \leq 1[/tex] vil aldri [tex]g(m)[/tex] "hopper over" noen heltall etter hvert som den vokser.
Derfor kan vi si at siden [tex]g(2^r)=1[/tex], ser vi at [tex]g(m)[/tex] alltid vil "falle tilbake" til [tex]1[/tex], og når [tex]m[/tex] etter hvert vokser til [tex]2^{r+1}-1[/tex], må [tex]g(m)[/tex] ha vokst til [tex]r+1[/tex], som vi har fra (2). Dette skjer uten å hoppe over noen heltall underveis, ettersom [tex]g(m+1)-g(m) \leq 1[/tex]. Dette betyr at [tex]g(m)[/tex] vil "passere" ethvert positivt heltall under [tex]r+1[/tex] mellom [tex]m=2^{r}[/tex] og [tex]m=2^{r+1}[/tex]. Det vil si at [tex]g(m)=1989[/tex] (eller [tex]2008[/tex] for den saks skyld) et uendelig antall ganger.
Jeg håper det ikke var noe uklart der.
Her kommer bevisene:
[tex](1): g(2^r)=1[/tex]
Vi beviser det ved å bruke at [tex]f(m) = \sum^{n}_{i=1} \lfloor \frac{m}{2^i} \rfloor [/tex].
[tex]f(2^r)=\sum^{n}_{i=1} \lfloor \frac{2^r}{2^i} \rfloor =\sum^{n}_{i=1} \lfloor 2^{r-i} \rfloor[/tex]. Etter definisjonen av [tex]n[/tex], ser vi at [tex]n=r[/tex], og vi får at [tex]f(2^r)=\sum^{r}_{i=1} \lfloor 2^{r-i} \rfloor[/tex]
Men [tex]2^{r-i}[/tex] er et heltall for alle [tex]r-i \geq 0[/tex], dvs. [tex]r \geq i[/tex], og dette er alltid sant siden [tex]i[/tex] har en øvre grense [tex]r[/tex]. Da får vi videre at [tex]f(2^r)=\sum^{r}_{i=1} 2^{r-i}=2^{r+1}\sum^{r}_{i=1} (\frac{1}{2})^{i-1}=2^{r+1}(\frac{1-2^{-r}}{2})=2^r-1[/tex].
Da har vi at [tex]g(2^r)=2^r-f(2^r)=2^r-(2^r-1)=1.[/tex]
Dermed er [tex](1)[/tex] bevist.
[tex](2): g(2^r-1)=r[/tex]
Vi bruker samme metode:
[tex]f(2^r-1)=\sum^{n}_{i=1} \lfloor \frac{2^{r}-1}{2^i} \rfloor =\sum^{n}_{i=1} \lfloor 2^{r-i}-(\frac{1}{2})^i \rfloor[/tex]
I dette tilfellet er [tex]n=r-1[/tex]. Det betyr at [tex]2^{r-i}[/tex] sin laveste verdi er [tex]2[/tex], og at det er alltid et heltall.
[tex](\frac{1}{2})^i[/tex] er derimot alltid mellom [tex]0[/tex] og [tex]1[/tex], og siden for positivt heltall [tex]p[/tex], og [tex]0<q<1: \ \lfloor p-q \rfloor=p-1[/tex], har vi at [tex]\lfloor 2^{r-i}-(\frac{1}{2})^i \rfloor=2^{r-i}-1[/tex].
Det gir oss at [tex] f(2^r-1)=\sum^{r-1}_{i=1} 2^{r-i}-1=2^{r+1}[\sum^{r-1}_{i=1} (\frac{1}{2})^{i-1}]-(r-1)=2^{r+1}(\frac{1-2^{1-r}}{2})-(r-1)=(2^r-2)-(r-1)=2^r-1-r[/tex]
Da har vi at [tex]g(2^r-1)=(2^r-1)-f(2^r-1)=2^r-1-(2^r-1-r)=r[/tex].
Dermed er [tex](2)[/tex] bevist.
[tex](3): g(m+1)-g(m) \leq 1[/tex]
Et forholdsvis lett og rett-fram bevis:
Naturlig nok er:
[tex]f(m+1) \geq f(m) \\ \Leftrightarrow f(m)-f(m+1) \leq 0 \\ \Leftrightarrow [(m+1)-f(m+1)]-[m-f(m)] \leq 1 \\ \Leftrightarrow g(m+1)-g(m) \leq 1[/tex].
Dermed er [tex](3)[/tex] bevist, og sammen med [tex](1)[/tex] og [tex](2)[/tex] beviser det at [tex]m-f(m)=1989[/tex] har et uendelig antall løsninger.
EDIT: Der kom mrcreo meg i forkjøpet med et kortere og litt mer elegant bevis.
-
mrcreosote
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
Ser riktig ut det, Jarle. Du hadde fått full pott i en konkurranse, det hadde ikke jeg; "Observer at..." og "Derfor..." kunne det vel med fordel vært gjort litt mer ut av.
Kanskje, men jeg tror etter litt forklaring din løsning hadde fått full pott den og.
Dette er andre gang jeg har sett noen har tatt et par linjers bevis ved å transformere til et annet tallsystem, som utenom trengtes flere sider. Må prøve dette her.
Dette er andre gang jeg har sett noen har tatt et par linjers bevis ved å transformere til et annet tallsystem, som utenom trengtes flere sider. Må prøve dette her.
Bra det, da kan vel jeg komme med min løsning/skisse (som baserer seg på noe av det samme som deres løsninger).
[tex]g(x)=x-f(x)[/tex]
[tex]n= \lfloor log_2 x \rfloor[/tex]
[tex]f(x)=\sum_{i=1}^{n}\lfloor \frac{x}{2^i} \rfloor[/tex]
[tex]x=2^n+y[/tex] der [tex]0 \leq y \leq 2^t -1[/tex]
[tex]f(2^n+y)=\sum_{i=1}^{n}\lfloor \frac{2^n+y}{2^i} \rfloor= \sum_{i=1}^{n}\lfloor 2^{n-i}+\frac{y}{2^i} \rfloor=\sum_{i=1}^{n}(\lfloor 2^{n-i} \rfloor+\lfloor \frac{y}{2^i}\rfloor)=\sum_{i=1}^n 2^{n-i} + \sum_{i=1}^n \lfloor \frac{y}{2^i}\rfloor = 2^n-1+ \sum_{i=1}^{\lfloor log_2 y \rfloor} \lfloor \frac{y}{2^i}\rfloor= 2^n-1+f(y) [/tex]
[tex]g(x)=g(2^n+y)=(2^n+y)-(2^n-1+f(y))=g(y)+1[/tex]
Vi vet at ethvert postitivt heltall [tex]x[/tex] kan skrives på formen [tex]2^{x_1}+2^{x_2}+\cdots+2^{x_t}[/tex] der[tex]x_i \in \mathbb{N}[/tex] og t er et gitt positivt heltall. Nå har vi at:
[tex]g(x)=g(2^{x_1}+2^{x_2}+\cdots+2^{x_t})=g(2^{x_j})+t-1[/tex] Og da:
[tex]g(2^{x_j}) =\sum_{i=1}^{\infty}\lfloor \frac{2^{x_j}}{2^i} \rfloor=2^j-1 \Rightarrow g(2^{x_j})=1 \Rightarrow g(2^{x_1}+2^{x_2}+\cdots+2^{x_t})= t[/tex]
Dette betyr at om [tex]m[/tex] kan skrives på formen [tex]2^{x_1}+\cdots+ 2^{x_{1989}}[/tex] så er [tex]m-f(m)=1989[/tex]. Det er opplagt uendelig mange slike positive heltall (legg f.eks til 1 på den største [tex]x_i[/tex])
[tex]g(x)=x-f(x)[/tex]
[tex]n= \lfloor log_2 x \rfloor[/tex]
[tex]f(x)=\sum_{i=1}^{n}\lfloor \frac{x}{2^i} \rfloor[/tex]
[tex]x=2^n+y[/tex] der [tex]0 \leq y \leq 2^t -1[/tex]
[tex]f(2^n+y)=\sum_{i=1}^{n}\lfloor \frac{2^n+y}{2^i} \rfloor= \sum_{i=1}^{n}\lfloor 2^{n-i}+\frac{y}{2^i} \rfloor=\sum_{i=1}^{n}(\lfloor 2^{n-i} \rfloor+\lfloor \frac{y}{2^i}\rfloor)=\sum_{i=1}^n 2^{n-i} + \sum_{i=1}^n \lfloor \frac{y}{2^i}\rfloor = 2^n-1+ \sum_{i=1}^{\lfloor log_2 y \rfloor} \lfloor \frac{y}{2^i}\rfloor= 2^n-1+f(y) [/tex]
[tex]g(x)=g(2^n+y)=(2^n+y)-(2^n-1+f(y))=g(y)+1[/tex]
Vi vet at ethvert postitivt heltall [tex]x[/tex] kan skrives på formen [tex]2^{x_1}+2^{x_2}+\cdots+2^{x_t}[/tex] der[tex]x_i \in \mathbb{N}[/tex] og t er et gitt positivt heltall. Nå har vi at:
[tex]g(x)=g(2^{x_1}+2^{x_2}+\cdots+2^{x_t})=g(2^{x_j})+t-1[/tex] Og da:
[tex]g(2^{x_j}) =\sum_{i=1}^{\infty}\lfloor \frac{2^{x_j}}{2^i} \rfloor=2^j-1 \Rightarrow g(2^{x_j})=1 \Rightarrow g(2^{x_1}+2^{x_2}+\cdots+2^{x_t})= t[/tex]
Dette betyr at om [tex]m[/tex] kan skrives på formen [tex]2^{x_1}+\cdots+ 2^{x_{1989}}[/tex] så er [tex]m-f(m)=1989[/tex]. Det er opplagt uendelig mange slike positive heltall (legg f.eks til 1 på den største [tex]x_i[/tex])