n+1 og multiplum av n

[stensrud]

Har begynt med litt problemløsing i det siste, og dette er mitt første forsøk på et bevis:

"Show that among any n + 1 positive integers, there must be two whose difference is a multiple of n."

(Tar utgangspunkt i at det vi har n+1 tall der differansen av to tall ikke er et multiplum av n.)
La m være et tilfeldig tall blant de n+1 tallene. Dermed kan ingen av de andre tallene skrives på formen m+-nx, siden dette ville gitt en differanse på nx, altså et multiplum av n. Kall tallene på formen m+-nx umulige. Videre velger vi et nytt tall (m+1), og det gjør alle tall på formen (m+1)+-nx umulige. Deretter velges (m+2), så (m+3)... Slik fortsetter det, helt til (m+(n-1)) er valgt. Det er da valgt n forskjellige tall. Men nå er alle tall umulige! Dermed må differansen mellom det siste tallet og et av de andre være et multiplum av n.

Synes kanskje at det ble litt langt/knotete i.e. uelegant? Noen som kunne gitt litt feedback på føringen av beviset?

[Vektormannen]

Velger du ut m, så det påfølgende tallet m+1, og så videre, eller misforstår jeg notasjonen din? Det skal være et utvalg av n + 1 vilkårlige positive heltall, ikke nødvendigvis etterfølgende.

[Brahmagupta]

Idéen i beviset ditt er riktig, men som du sier er det litt knotete. Du velger altså først et vilkårlig tall $m$ og utelukker alle
tall på formen $m+nx$, men så velger du tallet $m+1$. Du kan strengt tatt ikke vite at dette tallet er blant de $n+1$ tallene.
Det samme gjelder for resten av prosessen. Som sagt er idéen i beviset god, men det blir ikke helt formelt.

Her er en formell versjon av beviset ditt.

La de $n+1$ tallene være $a_1,a_2,\cdots , a_n,a_{n+1}$. For hver $a_m$ $1\leq m\leq n+1$ kan vi finne unike $b_m, r_m$ slik at
$a_m=nb_m+r_m$ hvor $0\leq r_m<n$. Siden vi har $n+1$ rester og $r_m\in\{0,1,2,\cdots,n-1\}$ må det finnes $i,j$ slik at $r_i=r_j$
og dermed har vi at $a_i-a_j=(nb_i+r_i)-(nb_j+r_j)=n(b_i-b_j)+(r_i-r_j)=n(b_i-b_j)$ som er delelig på $n$.

Dette sier at vi kun har $n$ mulige rester ved divisjon på $n$ og hvis vi deler $n+1$ tall på $n$ må vi få minst
to like rester og dermed må differansen mellom disse tallene være delelig på n.

Hvis du kjenner til kongruensregning og restklasser kan vi også bare si at blant $n+1$ heltall må minst to være i samme restklasse
modulo $n$ og dermed vil $n$ dele differansen mellom disse.

[stensrud]

Idéen i beviset ditt er riktig, men som du sier er det litt knotete. Du velger altså først et vilkårlig tall $m$ og utelukker alle
tall på formen $m+nx$, men så velger du tallet $m+1$. Du kan strengt tatt ikke vite at dette tallet er blant de $n+1$ tallene.
Det samme gjelder for resten av prosessen. Som sagt er idéen i beviset god, men det blir ikke helt formelt.

Her er en formell versjon av beviset ditt.

La de $n+1$ tallene være $a_1,a_2,\cdots , a_n,a_{n+1}$. For hver $a_m$ $1\leq m\leq n+1$ kan vi finne unike $b_m, r_m$ slik at
$a_m=nb_m+r_m$ hvor $0\leq r_m<n$. Siden vi har $n+1$ rester og $r_m\in\{0,1,2,\cdots,n-1\}$ må det finnes $i,j$ slik at $r_i=r_j$
og dermed har vi at $a_i-a_j=(nb_i+r_i)-(nb_j+r_j)=n(b_i-b_j)+(r_i-r_j)=n(b_i-b_j)$ som er delelig på $n$.

Dette sier at vi kun har $n$ mulige rester ved divisjon på $n$ og hvis vi deler $n+1$ tall på $n$ må vi få minst
to like rester og dermed må differansen mellom disse tallene være delelig på n.

Hvis du kjenner til kongruensregning og restklasser kan vi også bare si at blant $n+1$ heltall må minst to være i samme restklasse
modulo $n$ og dermed vil $n$ dele differansen mellom disse.

Takk for at du tok deg tid til å forklare! Jeg var klar over at tallene ikke måtte være påfølgene, men klarte ikke helt å formulere det på en god måte... Uansett, mens vi er inne på restmengder:

hvis det er slik at to forskjellige tall som dividert på n gir lik restmengde har en differanse som er delelig på n, kan man da si: divisjon på n kan gi (0,1,2,3...,n-1) som rest, altså n forskjellige rester. Og at hvis en da har n+1 tall vil 2 av dem ifølge dueboksprinsippet måtte ha samme rest, altså ha en differanse delelig på n?

Hadde det vært et fullstendig bevis etter litt renskriving osv?

[Brahmagupta]

Takk for at du tok deg tid til å forklare! Jeg var klar over at tallene ikke måtte være påfølgene, men klarte ikke helt å formulere det på en god måte... Uansett, mens vi er inne på restmengder:

hvis det er slik at to forskjellige tall som dividert på n gir lik restmengde har en differanse som er delelig på n, kan man da si: divisjon på n kan gi (0,1,2,3...,n-1) som rest, altså n forskjellige rester. Og at hvis en da har n+1 tall vil 2 av dem ifølge dueboksprinsippet måtte ha samme rest, altså ha en differanse delelig på n?

Hadde det vært et fullstendig bevis etter litt renskriving osv?

Ja, det fungerer fint.