trudne zadanie o szachownicy

_el_doopa · Post autor: **_el_doopa** » 29 lis 2004, o 16:45

dana jest szachownica n x n (n>=2)
na czarno pomalowano 2n pól
wykazać ze istnieje równoległobok o wierzchołkach w czarnych polach.
(nie umiem zrobic tego zadania)

półpasiec · Post autor: **półpasiec** » 1 gru 2004, o 00:55

tutaj az narzuca sie zasada szufladkowa, ale nie wiem w jaki sposob wyeliminowac wspolniniowosc punktow. Jeslibysmy okreslili dla kazdej pary wektor od jednego punktu do drugiego i wektory przeciwne uwazali za jeden, to wszystkich wektorow na szachownicy byloby 2n(n-1), natomiast wektorow byloby n(2n-1), zatem pewne dwa bylyby takie same. No ale tutaj nie jest powiedziane, ze nie moga lezec na jednej linii to dupa... na razie tutaj sie zacialem, ale moze cos jeszcze wykombinuje, a czy Ty je zrobiles??

g · Post autor: g » 3 gru 2004, o 16:35

lepiej mi sie tlumaczy na punktach kratowych.
z dirichleta (czy z czegos tam innego, w kazdym razie jest to oczywiste) jestesmy w stanie wybrac n takich par punktow, ze odcinek ktory tworza jest poziomy. mozliwych dlugosci takich odcinkow jest n-1 ({1,2,...,n}). znowu dirichlet i mamy, ze sa dwa odcinki rownolegle i tej samej dlugosci. koniec.

_el_doopa · Post autor: **_el_doopa** » 3 gru 2004, o 21:40

Czy to sie lekko nie psuje jak np
mamy dwa odcinki rownej dlugosci wspoliniowe??

g · Post autor: g » 4 gru 2004, o 12:41

jak mamy dwa takie odcinki wspolliniowe to one nam daja jeszcze dwa odcinki. powiedzmy, ze nasze wspolliniowe maja dlugosc a, zas odleglosc miedzy ich lewymi koncami wynosi b. mamy zatem jeszcze odciniki dlugosci b i a+b no i a oczywiscie. z dirichleta wynika ze wsrod n-2 par punktow (bo odjelismy te dwie wspolliniowe) bedzie conajmniej jedna o dlugosci a, b lub a+b. chociaz to w sumie tworzy nowe patologiczne przypadki... w kazdym razie da sie, ale nie chce mi sie myslec

półpasiec · Post autor: **półpasiec** » 4 gru 2004, o 13:13

mozna inaczej pokazac, ze istnieje n roznych odcinkow.
Niech d wierszy zawiera wiecej niz jeden punkt. Niech wiersz i bedzie mial xi pol czarnych(nie numerujemy ich po kolei), wiec zalozmy, ze x1,x2,...xd>1. W wierszu, w ktorym jest xi pol istnieje co najmniej xi-1 odcinkow roznej dlugosci. Wszystkich pol jest
x1+x2+...+xn=2n
x1-1+x2-1+...+xd-1=2n-d - (xd+1+xd+2+...+xn),
ale liczby xd+1,xd+2,...,xn sa rowne 1 lub 0, wiec ich suma nie przekracza n-d zatem 2n-d-(xd+1+xd+2+...+xn)>=2n-d-n+d=n. Zatem, istnieje co najmniej n odcinkow, wiec pewne dwa sie powtarzaja, a przy tym nie leza na jednej linii