Duvprincipen?

I en regelbunden 3982-hörning indelas hörnen i par och de båda punkterna i varje par förbinds med en rät linje. Visa att de 1991 sträckor som erhålls inte alla kan ha olika längd.

Det är ekvivalent att visa följande:

Det existerar inte en uppdelning av kongruensklasserna 0, ..., 3981 (mod 3982) som a_1, a_2, ..., a_1991, b_1, b_2, ... b_1991 så att

a_i - b_i = i (mod 3982)

Nu är det bara att trixa lite med kongruenser och använda att pariteten blir fel.

Hej, nu kan jag egentligen inget om sådan här matematik, men så här ser jag på problemet.
Du har 1991 linjer att placera ut, men det maximala avståndet(räknat i hörn) är 1991 - 1, vilket ju är färre än antalet linjer. alltså så måste det finnas minst 2st linjer som har samma avstånd.
eftersom jag inte kan sånt här så har jag säkert skämt ut mig nu

Vad läser du för matte?

Jag förstår inte varför de är ekvivalenta. Kan du förklara?

Först och främst definierar vi ett nytt avstånd: Om A och B är två hörn på 3982-hörningen, så låter vi

d(A, B) = längden (i antal kanter) av den kortaste vägen mellan A och B om man går längs med polygonens ytterkant

(det vill säga, d(A, B) = x om det ligger x-1 hörn mellan A och B som kortast)

Detta avstånd är förstås inte detsamma som längden av sträckan mellan a och b, men man kan inse vi kan skriva längden på sträckan från A till B som

|AB| = f(d(A, B))

där f är en injektiv (faktiskt strikt ökande) funktion. Särskilt gäller att två sträckor AB och CD har samma längd om och endast om d(A, B) = d(C,D).

Så då kan vi alltså formulera om frågan som såhär:

En regelbunden 3982-hörnings hörn delas in i par (A_1, B_1), ..., (A_1991, B_1991). Visa att de 1991 talen

d(A_1, b_1), ..., d(A_1991, B_1991)

inte kan vara alla olika.

(Egentligen har vi inte gjort så mycket än. Fördelen med det här nya avståndsmåttet d är att det alltid är ett heltal, och då är lättare att resonera kring.)


Numrera nu hörnen i 3982-hörningen med 0, 1, ..., 3981, i den ordningen. Notera att om A har nummer a och B har nummer b, och B ligger "efter" A i ordningen, så är

d(A, B) ≡ b - a (mod 3982).


Nu ska jag visa att

a): "det går att hitta en uppdelning av hörnen i par (A_1, B_1), ..., (A_1991, B_1991) så att de 1991 talen d(A_i, B_i) alla är olika"

är ekvivalent med

b) "det existerar en uppdelning av 0, ..., 3982 i par (a_1, b_1), ..., (a_1991, b_1991) så att b_i - a_i ≡ i (mod 3982) för alla i med 1 ≤ i ≤ 1991".

Anta först att a) gäller. Eftersom det bara finns 1991 möjliga värden på d(A_i, B_i) så måste då d(A_i, B_i) anta vart och ett av värdena 1, 2, ..., 1991. Genom att numrera om paren (A_i, B_i) så kan vi alltså hitta en uppdelning så att

d(A_i, B_i) = i.

Detta betyder att

b_i - a_i ≡ ±i (mod 3982).

Om vi nu byter ut B_i mot A_i i alla par där b_i - a_i ≡ -i (mod 3982), så är då (a_i, b_i) en uppdelning av talen 0, ..., 3981 så att

b_i - a_i ≡ i (mod 3982).

Anta omvänt att b) gäller. Gör då motsvarande uppdelning (A_i, B_i) av hörnen i 3982. Då kommer d(A_i, B_i) = i, och dessa värden är alltså alla olika.

Jag glömde nästan bort och tacka dig. Mycket pedagogiskt och bra svar. Tack så mycket