n+1 og multiplum av n

Mange finner bevis vanskelig. Her er rom for spørsmål vedrørende bevis, og for å dele dine bevis med andre. Vi tenker først og fremst videregående nivå, men det er ingen begrensninger her.

n+1 og multiplum av n

Innlegg stensrud » 26/11-2014 15:46

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?
stensrud offline
Descartes
Descartes
Innlegg: 438
Registrert: 08/11-2014 21:13
Bosted: Cambridge

Re: n+1 og multiplum av n

Innlegg Vektormannen » 26/11-2014 17:23

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.
Elektronikk @ NTNU | nesizer
Vektormannen offline
Euler
Euler
Brukerens avatar
Innlegg: 5889
Registrert: 26/09-2007 18:35
Bosted: Trondheim

Re: n+1 og multiplum av n

Innlegg Brahmagupta » 26/11-2014 17:24

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.
Brahmagupta offline
Guru
Guru
Innlegg: 628
Registrert: 06/08-2011 00:56

Re: n+1 og multiplum av n

Innlegg stensrud » 26/11-2014 18:05

Brahmagupta skrev: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?
stensrud offline
Descartes
Descartes
Innlegg: 438
Registrert: 08/11-2014 21:13
Bosted: Cambridge

Re: n+1 og multiplum av n

Innlegg Brahmagupta » 26/11-2014 20:50

stensrud skrev: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.
Brahmagupta offline
Guru
Guru
Innlegg: 628
Registrert: 06/08-2011 00:56

Hvem er i forumet

Brukere som leser i dette forumet: Ingen registrerte brukere og 2 gjester