La a og b være heltall større enn 1, og la dem være slik at de ikke har noen felles divisorer.
Bevis at:
[tex]\sum^{a-1}_{i=1} \lfloor \frac{bi}{a} \rfloor = \sum^{b-1}_{j=1} \lfloor \frac{aj}{b} \rfloor[/tex],
og finn verdien av summen.
PS: Noen kjenner kanskje denne igjen fra the Art and Craft of Problem Solving av Paul Zeits. Anbefaler den sterkt som andre ofte før har gjort på dette forumet.
Heltallige summer
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Heisan, kom nettop hjem fra IMO (se:http://www.imo-official.org/), Jørgen Vold Rennemo fra Norge tok gull!!!
Her er løsningen min til oppgaven:
La: [tex]\frac{ka}{b}= \lfloor \frac{ka}{b} \rfloor + x_{k} \forall k \in {1,2,...,b-1}[/tex]
[tex]x_{k} \in (0,1)[/tex]
[tex]ka=b \lfloor \frac{ka}{b} \rfloor + bx_{k}[/tex]
[tex]ka \equiv bx_{k} [/tex] [tex]mod b[/tex]
Fordi settet [tex]\{a, 2a,..., (b-1)a\}[/tex] danner settet: [tex]\{1,2,...b-1\}[/tex] modulo b (i en viss rekkefølge) og at [tex]bx_{k}<b[/tex] må nødvendigvis: [tex]\{bx_{1}, bx_{2},...,bx_{b-1}\}[/tex] være lik [tex]\{1,2,...,b-1\} [/tex] (igenn i en viss rekkefølge)
[tex]\sum ^{b-1}_{i=1} bx_{i}=1+2+3+...+b-1=\frac{(b-1)b}{2}[/tex]
[tex]\sum ^{b-1}_{i=1} ia=a \frac{(b-1)b}{2}[/tex]
[tex]\sum ^{b-1}_{i=1} b \lfloor \frac{ia}{b} \rfloor =a \frac{(b-1)b}{2}- \frac{(b-1)b}{2}=b \frac {(a-1)(b-1)}{2}[/tex]
Derfor er [tex]\sum ^{b-1}_{i=1} \lfloor \frac{ia}{b} \rfloor =\frac {(a-1)(b-1)}{2}[/tex]
Om man nå bytter ut b med a og omvendt, ser man at:
[tex]\sum ^{b-1}_{i=1} \lfloor \frac{ia}{b} \rfloor =\frac {(a-1)(b-1)}{2}= \sum ^{a-1}_{i=1} \lfloor \frac{ib}{a} \rfloor[/tex]
Edit: Liten stavefeil der
Her er løsningen min til oppgaven:
La: [tex]\frac{ka}{b}= \lfloor \frac{ka}{b} \rfloor + x_{k} \forall k \in {1,2,...,b-1}[/tex]
[tex]x_{k} \in (0,1)[/tex]
[tex]ka=b \lfloor \frac{ka}{b} \rfloor + bx_{k}[/tex]
[tex]ka \equiv bx_{k} [/tex] [tex]mod b[/tex]
Fordi settet [tex]\{a, 2a,..., (b-1)a\}[/tex] danner settet: [tex]\{1,2,...b-1\}[/tex] modulo b (i en viss rekkefølge) og at [tex]bx_{k}<b[/tex] må nødvendigvis: [tex]\{bx_{1}, bx_{2},...,bx_{b-1}\}[/tex] være lik [tex]\{1,2,...,b-1\} [/tex] (igenn i en viss rekkefølge)
[tex]\sum ^{b-1}_{i=1} bx_{i}=1+2+3+...+b-1=\frac{(b-1)b}{2}[/tex]
[tex]\sum ^{b-1}_{i=1} ia=a \frac{(b-1)b}{2}[/tex]
[tex]\sum ^{b-1}_{i=1} b \lfloor \frac{ia}{b} \rfloor =a \frac{(b-1)b}{2}- \frac{(b-1)b}{2}=b \frac {(a-1)(b-1)}{2}[/tex]
Derfor er [tex]\sum ^{b-1}_{i=1} \lfloor \frac{ia}{b} \rfloor =\frac {(a-1)(b-1)}{2}[/tex]
Om man nå bytter ut b med a og omvendt, ser man at:
[tex]\sum ^{b-1}_{i=1} \lfloor \frac{ia}{b} \rfloor =\frac {(a-1)(b-1)}{2}= \sum ^{a-1}_{i=1} \lfloor \frac{ib}{a} \rfloor[/tex]
Edit: Liten stavefeil der
Sist redigert av Zivert den 24/07-2008 00:29, redigert 1 gang totalt.
Pent, kan for underholdningens skyld legge ut min egen løsning.
La [tex]a = q \cdot b + r , \ (q,r \in \mathbb{Z}), ( 0<r<b)[/tex]
La oss parere leddene i summen [tex]S=\sum^{b-1}_{i=1} \lfloor \frac{ia}{b} \rfloor[/tex] slik:
[tex]S=\large( \lfloor \frac{a}{b} \rfloor + \lfloor \frac{(b-1)a}{b} \rfloor \large) + \large( \lfloor \frac{2a}{b} \rfloor + \lfloor \frac{(b-2)a}{b} \rfloor \large)+...+\large( \lfloor \frac{\frac{b-1}{2}a}{b} \rfloor + \lfloor \frac{\frac{b+1}{2}a}{b} \rfloor \large)[/tex]
(Her antar vi at b ikke er delelig på 2)
La oss skrive det generelle leddparet: [tex]L_k=\lfloor \frac{ka}{b} \rfloor + \lfloor \frac{(b-k)a}{b} \rfloor[/tex] slik:
[tex]L_k=\lfloor \frac{k(qb+r)}{b} \rfloor + \lfloor a-\frac{k(qb+r)}{b} \rfloor=\lfloor kq+\frac{r}{b} \rfloor + \lfloor a-kq-\frac{r}{b} \rfloor=kq+\lfloor \frac{r}{b} \rfloor + a-kq - \lceil \frac{r}{b} \rceil=a-1[/tex] ettersom [tex]\frac{r}{b}[/tex] aldri er et heltall.
Da kan vi skrive om S slik:
[tex]S={(a-1)+(a-1)+...+(a-1)}[/tex] ([tex]\frac{b-1}{2}[/tex] ganger)
[tex]\Rightarrow S=\frac{(a-1)(b-1)}{2}[/tex]
Hvis b derimot er delelig på 2, fungerer ikke denne pareringen. Vi kan imidlertidig parere alle utenom det midterste leddet i rekken
[tex]R=\sum^{b-1}_{i=1} \lfloor \frac{ia}{b} \rfloor = \large( \lfloor \frac{a}{b} \rfloor + \lfloor \frac{(b-1)a}{b} \rfloor \large) + \large( \lfloor \frac{2a}{b} \rfloor + \lfloor \frac{(b-2)a}{b} \rfloor \large)+...+\large( \lfloor \frac{\frac{b-2}{2}a}{b} \rfloor + \lfloor \frac{\frac{b+2}{2}a}{b} \rfloor \large)+\large( \lfloor \frac{\frac{b}{2}a}{b} \rfloor \large)=\frac{(a-1)(b-2)}{2}+\lfloor \frac{a}{2} \rfloor =\frac{(a-1)(b-2)}{2}+\frac{a-1}{2}[/tex]
(Ettersom a ikke er delelig på 2 fordi b er delelig på 2)
[tex]= \frac{(a-1)(b-1)}{2}[/tex]
Vi kan ved samme argument vise at [tex]\sum^{a-1}_{j=1} \lfloor \frac{jb}{a} \rfloor = \frac{(a-1)(b-1)}{2}[/tex] ved å bytte om variablene a og b.
@ Sivert: se nyeste tråd
La [tex]a = q \cdot b + r , \ (q,r \in \mathbb{Z}), ( 0<r<b)[/tex]
La oss parere leddene i summen [tex]S=\sum^{b-1}_{i=1} \lfloor \frac{ia}{b} \rfloor[/tex] slik:
[tex]S=\large( \lfloor \frac{a}{b} \rfloor + \lfloor \frac{(b-1)a}{b} \rfloor \large) + \large( \lfloor \frac{2a}{b} \rfloor + \lfloor \frac{(b-2)a}{b} \rfloor \large)+...+\large( \lfloor \frac{\frac{b-1}{2}a}{b} \rfloor + \lfloor \frac{\frac{b+1}{2}a}{b} \rfloor \large)[/tex]
(Her antar vi at b ikke er delelig på 2)
La oss skrive det generelle leddparet: [tex]L_k=\lfloor \frac{ka}{b} \rfloor + \lfloor \frac{(b-k)a}{b} \rfloor[/tex] slik:
[tex]L_k=\lfloor \frac{k(qb+r)}{b} \rfloor + \lfloor a-\frac{k(qb+r)}{b} \rfloor=\lfloor kq+\frac{r}{b} \rfloor + \lfloor a-kq-\frac{r}{b} \rfloor=kq+\lfloor \frac{r}{b} \rfloor + a-kq - \lceil \frac{r}{b} \rceil=a-1[/tex] ettersom [tex]\frac{r}{b}[/tex] aldri er et heltall.
Da kan vi skrive om S slik:
[tex]S={(a-1)+(a-1)+...+(a-1)}[/tex] ([tex]\frac{b-1}{2}[/tex] ganger)
[tex]\Rightarrow S=\frac{(a-1)(b-1)}{2}[/tex]
Hvis b derimot er delelig på 2, fungerer ikke denne pareringen. Vi kan imidlertidig parere alle utenom det midterste leddet i rekken
[tex]R=\sum^{b-1}_{i=1} \lfloor \frac{ia}{b} \rfloor = \large( \lfloor \frac{a}{b} \rfloor + \lfloor \frac{(b-1)a}{b} \rfloor \large) + \large( \lfloor \frac{2a}{b} \rfloor + \lfloor \frac{(b-2)a}{b} \rfloor \large)+...+\large( \lfloor \frac{\frac{b-2}{2}a}{b} \rfloor + \lfloor \frac{\frac{b+2}{2}a}{b} \rfloor \large)+\large( \lfloor \frac{\frac{b}{2}a}{b} \rfloor \large)=\frac{(a-1)(b-2)}{2}+\lfloor \frac{a}{2} \rfloor =\frac{(a-1)(b-2)}{2}+\frac{a-1}{2}[/tex]
(Ettersom a ikke er delelig på 2 fordi b er delelig på 2)
[tex]= \frac{(a-1)(b-1)}{2}[/tex]
Vi kan ved samme argument vise at [tex]\sum^{a-1}_{j=1} \lfloor \frac{jb}{a} \rfloor = \frac{(a-1)(b-1)}{2}[/tex] ved å bytte om variablene a og b.
@ Sivert: se nyeste tråd
-
mrcreosote
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
Geometrisk: Tegn trekanten T med hjørner i (0,0), (a,0) og (a,b). Siden a og b er koprime, vil ikke sida mellom (0,0) og (a,b) skjære i noen punkter med 2 heltallige koordinater (gitterpunkter) unntatt nettopp endepunktene. Summen med a-1 som øvre grense vil nå være lik antall gitterpunkter ekte inni T. (Lange argumenter kan lages, men man overbeviser seg lett om det med ei god tegning.)
Lar vi k være antall slike indre gitterpunkter gir Picks teorem oss at arealet av trekanten er [tex]\frac12ab = k+\frac{a+b+1}2-1[/tex], så vi har [tex]k=\frac12(a-1)(b-1)[/tex].
Samme argument for den andre summen.
Lar vi k være antall slike indre gitterpunkter gir Picks teorem oss at arealet av trekanten er [tex]\frac12ab = k+\frac{a+b+1}2-1[/tex], så vi har [tex]k=\frac12(a-1)(b-1)[/tex].
Samme argument for den andre summen.