For et positivt heltall [tex]n[/tex] har vi [tex]n+1[/tex] positive heltall [tex]a_1, a_2 \ldots a_{n+1}[/tex] mellom 0 og 2n. De følgende oppgavene er rangert sånn omtrent etter vanskelighetsgrad.
a) Vis at to av heltallene [tex]a_i[/tex] og [tex]a_j[/tex] er slik at enten [tex]a_i=a_j[/tex] eller [tex]a_i=a_j+n[/tex].
b) Vis at to av heltallene og ikke har noen felles faktor.
c) Vis at ett av heltallene deler et annet .
Heltallsrekke
Moderators: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Vil det si [tex]0 \leq a_i \leq 2n[/tex], eller [tex]0 < a_i < 2n[/tex]? Jeg antar sistnevnte, ettersom hvis ikke kan vi la alle være multipler av 2 som motsier b).
EDIT: jeg antar i b) at en av antakelsene er at alle a_i'ene er ulike? Hvis ikke kan vi la dem alle være lik f.eks 2.
EDIT2: og jeg innser nå at moteksempelet mitt i toppen ikke duger siden de er positive... Men jeg antar at det er mellom (og lik) 1 og 2n som gjelder.
EDIT: jeg antar i b) at en av antakelsene er at alle a_i'ene er ulike? Hvis ikke kan vi la dem alle være lik f.eks 2.
EDIT2: og jeg innser nå at moteksempelet mitt i toppen ikke duger siden de er positive... Men jeg antar at det er mellom (og lik) 1 og 2n som gjelder.
Last edited by Charlatan on 02/07-2010 02:05, edited 2 times in total.
a)
Antar det siste som Charlatan sier.
Anta at alle [tex]a_i[/tex]-ene er forskjellige og [tex]a_j\neq a_i+n[/tex]
Vi plukker et heltall [tex]a_1[/tex] fra mengden [tex]\{1,...,2n\}[/tex].
Deretter et heltall [tex]a_2[/tex] fra mengden [tex]\{1,...,2n\}\setminus \{a_1, a_1\pm n\}[/tex].
Etter [tex]n[/tex] utplukk er kardinaliteten til [tex]\{1,...,2n\}\setminus \{a_1, a_1\pm n, a_2, a_2\pm n, ..., a_n, a_n\pm n\}[/tex] 0, så det er ingen kandidater for [tex]a_{n+1}[/tex], vi får en motsigelse.
Antar det siste som Charlatan sier.
Anta at alle [tex]a_i[/tex]-ene er forskjellige og [tex]a_j\neq a_i+n[/tex]
Vi plukker et heltall [tex]a_1[/tex] fra mengden [tex]\{1,...,2n\}[/tex].
Deretter et heltall [tex]a_2[/tex] fra mengden [tex]\{1,...,2n\}\setminus \{a_1, a_1\pm n\}[/tex].
Etter [tex]n[/tex] utplukk er kardinaliteten til [tex]\{1,...,2n\}\setminus \{a_1, a_1\pm n, a_2, a_2\pm n, ..., a_n, a_n\pm n\}[/tex] 0, så det er ingen kandidater for [tex]a_{n+1}[/tex], vi får en motsigelse.
Med nærmere omtanke: for n=1 må vi ha to tall mellom 0 og 2, så jeg tolker det som at intervallet er [tex]0 < a_i \leq 2n[/tex].
c) Vi fører induksjon. Det gjelder selvsagt for n=1, så anta det gjelder for n = k.
Anta at vi har [tex]a_1,...,a_{k+2}[/tex] (uten tap av generalitet) i monotont stigende rekkefølge slik at [tex]1 \leq a_i \leq 2(k+1)[/tex].
Anta at ingen deler hverandre. Dersom vi har k+1 tall mindre eller lik 2k, vil et av dem dele et annet ved hypotesen, så vi må nødvendigvis ha at [tex]a_{k+2}=2k+2[/tex], og [tex]a_{k+1}=2k+1[/tex]. Ved antakelsen er ingen av tallene lik k+1, ettersom det i så fall ville ha delt [tex]a_{k+2}[/tex]. Men dersom vi legger til k+1 i tallmengden vi induksjonshyptesen gi at et av tallene (mindre eller lik 2k) deler et annet. Dermed må [tex]a_i[/tex] dele k+1 for en [tex]i \leq k[/tex] (siden de ikke deler noen andre tall av vår antakelse, og k+1 kan ikke dele noen tall mindre eller lik 2k). Men det betyr at [tex]a_i[/tex] deler [tex]a_{k+2}[/tex] som er en motsigelse.
Altså må et av tallene dele et annet, og ved induksjon så gjelder det for enhver n.
c) Vi fører induksjon. Det gjelder selvsagt for n=1, så anta det gjelder for n = k.
Anta at vi har [tex]a_1,...,a_{k+2}[/tex] (uten tap av generalitet) i monotont stigende rekkefølge slik at [tex]1 \leq a_i \leq 2(k+1)[/tex].
Anta at ingen deler hverandre. Dersom vi har k+1 tall mindre eller lik 2k, vil et av dem dele et annet ved hypotesen, så vi må nødvendigvis ha at [tex]a_{k+2}=2k+2[/tex], og [tex]a_{k+1}=2k+1[/tex]. Ved antakelsen er ingen av tallene lik k+1, ettersom det i så fall ville ha delt [tex]a_{k+2}[/tex]. Men dersom vi legger til k+1 i tallmengden vi induksjonshyptesen gi at et av tallene (mindre eller lik 2k) deler et annet. Dermed må [tex]a_i[/tex] dele k+1 for en [tex]i \leq k[/tex] (siden de ikke deler noen andre tall av vår antakelse, og k+1 kan ikke dele noen tall mindre eller lik 2k). Men det betyr at [tex]a_i[/tex] deler [tex]a_{k+2}[/tex] som er en motsigelse.
Altså må et av tallene dele et annet, og ved induksjon så gjelder det for enhver n.