Påskenøtt 2

[skf95]

Vis at det blant fire vilkårlige tall, alltid finnes to tall med en differanse som er delelig med $3$.

[Gustav]

Anta det motsatte, og la $a_1,a_2,a_3,a_4$ være tallene. La $a_{i,j}=a_i-a_j \,mod(3)$. Da er $a_{i,j}$ ekvivalent med enten 1 eller 2 for alle $i\neq j$.

Vi har nå at $a_{4,1}=a_{4,3}+a_{3,2}+a_{2,1}$. De eneste mulighetene er da at $a_{4,1}$ er enten $1+1+2$ eller $1+2+2$ opp til rekkefølgen på leddene. Det er nå lett å sjekke at da må enten $a_{4,2}$ eller $a_{3,1}$ være ekvivalent med 0 modulo 3. Dermed har vi en motsigelse, og påstanden følger.

[Brahmagupta]

Jeg antar at det her er snakk om heltall. Siden vi har 4 tall må minst to av dem gi samme rest ved divisjon på 3 (pigeonhole-principle) og dermed
vil differansen mellom disse være delelig på 3.

Litt mer presist: La tallene være [tex]a_1,a_2,a_3,a_4[/tex]. For hver [tex]a_i[/tex] kan vi
finne unike tall [tex]b_i[/tex] og [tex]r_i[/tex] med [tex]r_i\in\{0,1,2\}[/tex] slik at [tex]a_i=3b_i+r_i[/tex]. Siden hver enkelt r kun kan ta
3 verdier må det finnes indekser [tex]j,k[/tex] slik at [tex]r_j=r_k[/tex] og dermed er [tex]a_j-a_k=(3b_j+r_j)-(3b_k+r_k)=3(b_j-b_k)[/tex]

[Gustav]

Siden vi har 4 tall må minst to av dem gi samme rest ved divisjon på 3 (pigeonhole-principle) og dermed
vil differansen mellom disse være delelig på 3.

Definitivt det mest elegante beviset