Et høflig tall er et tall som kan skrives som summen av etterfølgende positive heltall.
Vis at alle tall som ikke er en potens av 2 er høflige.
Høflige tall
Moderators: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Ah, noe lignende ble gitt på årets matematikkdag ved NTNU til de VGS-elevene som kom opp der. Da ble man bedt om å finne hvilke tall som ikke kan skrives som sum av etterfølgende, positive heltall. Det viste seg jo da at det var potenser av 2, men så vidt jeg vet var det ikke mange som klarte å bevise dette.
-
Nebuchadnezzar
- Fibonacci
- Posts: 5648
- Joined: 24/05-2009 14:16
- Location: NTNU
La oss anta at [tex]2^h[/tex] er et høflig tall. Vi lar [tex]\;k=2^h\;[/tex] der [tex]\;h>0\;[/tex]
[tex]k \, =\, \sum_{i=a}^b\,i[/tex] der [tex]\;b>a\;[/tex] og [tex]\;a>-1\;[/tex]
[tex]k \, = \, 2^h \, =\, \sum_{i=a}^b\,i \, = \, \sum_{j=0}^{b-a}\, (j+a)\, = \, \sum_{j=0}^{b-a}\, j \,+ \, \sum_{j=0}^{b-a}\, a \, = \, \frac{(a-b)(b-a+1)}{2}+(b-a+1)a[/tex]
Ganger begge sider med [tex]2[/tex]
[tex]2^{k+1}\,=\,(a-b)(b-a+1)+(b-a+1)a \,=\, (b-a+1)(b-a-2a)[/tex]
La oss anta at [tex]b-a[/tex] er et partall. Da er [tex]b-a+1[/tex] et oddetall. Her får vi en motsigelse, siden 2^{k+1} kun kan bestå av partal faktorer. Om [tex]b-a[/tex] er oddetall så er [tex]b-a-2a[/tex] oddetall. Igjen får vi en motsigelse. Dermed kan ikke [tex]k[/tex] være et høflig tall.
Å bevise at alle de andre tallene er høflige overlater jeg til noen andre ^^
[tex]k \, =\, \sum_{i=a}^b\,i[/tex] der [tex]\;b>a\;[/tex] og [tex]\;a>-1\;[/tex]
[tex]k \, = \, 2^h \, =\, \sum_{i=a}^b\,i \, = \, \sum_{j=0}^{b-a}\, (j+a)\, = \, \sum_{j=0}^{b-a}\, j \,+ \, \sum_{j=0}^{b-a}\, a \, = \, \frac{(a-b)(b-a+1)}{2}+(b-a+1)a[/tex]
Ganger begge sider med [tex]2[/tex]
[tex]2^{k+1}\,=\,(a-b)(b-a+1)+(b-a+1)a \,=\, (b-a+1)(b-a-2a)[/tex]
La oss anta at [tex]b-a[/tex] er et partall. Da er [tex]b-a+1[/tex] et oddetall. Her får vi en motsigelse, siden 2^{k+1} kun kan bestå av partal faktorer. Om [tex]b-a[/tex] er oddetall så er [tex]b-a-2a[/tex] oddetall. Igjen får vi en motsigelse. Dermed kan ikke [tex]k[/tex] være et høflig tall.
Å bevise at alle de andre tallene er høflige overlater jeg til noen andre ^^
"Å vite hva man ikke vet er og en slags allvitenhet" - Piet Hein
https://s.ntnu.no/Integralkokeboken
Lektor - Matematikk, Fysikk og Informatikk
https://s.ntnu.no/Integralkokeboken
Lektor - Matematikk, Fysikk og Informatikk
Det 'motsatte resultatet' som nettopp ble vist, dvs at ingen toerpotenser er høflige, var forøvrig også en oppgave i finalen i Abelkonkurransen i ett eller annet år. Antar selvfølgelig også at ett enkelt tall ikke regnes som en sum av etterfølgende positive heltall - i så fall er jo alle tall åpenbart høflige.
Vi har at summen av heltallene fra og med 1 til n er [tex]\frac {n(n+1)} 2[/tex]. Summen av heltallene fra og med 1 til m er tilsvarende [tex]\frac {m(m+1)} 2[/tex]. Da er summen av heltallene fra og med m+1 til n lik [tex]\frac {n(n+1)} 2 - {m(m+1)} 2 = \frac {(n-m)(n+m+1)} 2[/tex]. For å få 'noe vi kan jobbe med' må vi da ha at [tex]m+1<n[/tex], og altså [tex]m+2 \leq n[/tex] for ellers består 'summen' vår bare av ett tall.
Vi ser så at om et tall [tex]k[/tex] ikke er en toerpotens kan [tex]2k[/tex] skrives på formen [tex]2k=ab[/tex], der [tex]a[/tex] og [tex]b[/tex] har motsatt paritet og begge er større enn 1. Anta uten tap av generalitet at [tex]a<b[/tex] (vi kan ikke ha likhet, da tallene har motsatt paritet).Vi ser da at vi ved å sette [tex]n=\frac {a+b-1} 2[/tex] og [tex]m=\frac {b-a-1} 2[/tex] har vi [tex]n-m=a[/tex] og [tex]n+m+1=b[/tex], så summen av tall fra m+1 til og med n er [tex]\frac{(n-m)(n+m+1)} 2=\frac{ab} 2 = \frac {2k} 2 = k[/tex].
Det gjenstår så å vise at [tex]\frac {a+b-1} 2[/tex]og [tex]\frac {a-b-1} 2[/tex] faktisk er positive, hele tall (det holder å vise at [tex]m[/tex] er ikkenegativt, da summen vår, som løper fra m+1 til n, godt kan starte på [tex]1=0+1[/tex]) med en differanse på minst 2. At de er hele tall følger av at a og b har motsatt paritet. a+b (og b-a) er altså et oddetall, så a+b-1 er derfor delelig med to (og b-a-1 er også delelig med to), og begge er derfor heltall. Differansen deres er [tex]\frac {(a+b-1)-(b-a-1)} 2 = \frac {2a} 2 = a[/tex], som av antagelse er større enn 1, og derfor minst to. At [tex]n=\frac {a+b-1} 2[/tex] er positivt er opplagt, da a og b begge er større enn 1, og at [tex]m=\frac {b-a-1} 2[/tex] er ikkenegativt er likeopplagt, da [tex]b>a[/tex], så [tex]b-a \geq 1[/tex], så [tex]m \geq \frac {1-1} 2 = 0[/tex].
Vi har at summen av heltallene fra og med 1 til n er [tex]\frac {n(n+1)} 2[/tex]. Summen av heltallene fra og med 1 til m er tilsvarende [tex]\frac {m(m+1)} 2[/tex]. Da er summen av heltallene fra og med m+1 til n lik [tex]\frac {n(n+1)} 2 - {m(m+1)} 2 = \frac {(n-m)(n+m+1)} 2[/tex]. For å få 'noe vi kan jobbe med' må vi da ha at [tex]m+1<n[/tex], og altså [tex]m+2 \leq n[/tex] for ellers består 'summen' vår bare av ett tall.
Vi ser så at om et tall [tex]k[/tex] ikke er en toerpotens kan [tex]2k[/tex] skrives på formen [tex]2k=ab[/tex], der [tex]a[/tex] og [tex]b[/tex] har motsatt paritet og begge er større enn 1. Anta uten tap av generalitet at [tex]a<b[/tex] (vi kan ikke ha likhet, da tallene har motsatt paritet).Vi ser da at vi ved å sette [tex]n=\frac {a+b-1} 2[/tex] og [tex]m=\frac {b-a-1} 2[/tex] har vi [tex]n-m=a[/tex] og [tex]n+m+1=b[/tex], så summen av tall fra m+1 til og med n er [tex]\frac{(n-m)(n+m+1)} 2=\frac{ab} 2 = \frac {2k} 2 = k[/tex].
Det gjenstår så å vise at [tex]\frac {a+b-1} 2[/tex]og [tex]\frac {a-b-1} 2[/tex] faktisk er positive, hele tall (det holder å vise at [tex]m[/tex] er ikkenegativt, da summen vår, som løper fra m+1 til n, godt kan starte på [tex]1=0+1[/tex]) med en differanse på minst 2. At de er hele tall følger av at a og b har motsatt paritet. a+b (og b-a) er altså et oddetall, så a+b-1 er derfor delelig med to (og b-a-1 er også delelig med to), og begge er derfor heltall. Differansen deres er [tex]\frac {(a+b-1)-(b-a-1)} 2 = \frac {2a} 2 = a[/tex], som av antagelse er større enn 1, og derfor minst to. At [tex]n=\frac {a+b-1} 2[/tex] er positivt er opplagt, da a og b begge er større enn 1, og at [tex]m=\frac {b-a-1} 2[/tex] er ikkenegativt er likeopplagt, da [tex]b>a[/tex], så [tex]b-a \geq 1[/tex], så [tex]m \geq \frac {1-1} 2 = 0[/tex].