matematikk.net

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.

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

Zivert skrev:Jørgen Vold Rennmo

Rennemo.

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

Bra løsning Jarle!

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.

Ah, geometriske bevis er det ultimate. Picks teorem har jeg vært litt borti før, men ikke så mye. Er vel bare å putte det i verktøykassa =)