trudne zadanie o szachownicy

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
_el_doopa
Użytkownik
Użytkownik
Posty: 453
Rejestracja: 22 sie 2004, o 23:09
Płeć: Mężczyzna
Pomógł: 16 razy

trudne zadanie o szachownicy

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)
Ostatnio zmieniony 1 gru 2004, o 22:15 przez _el_doopa, łącznie zmieniany 1 raz.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

półpasiec
Gość Specjalny
Gość Specjalny
Posty: 534
Rejestracja: 8 lip 2004, o 17:05
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 1 raz
Pomógł: 17 razy

trudne zadanie o szachownicy

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??

Awatar użytkownika
g
Użytkownik
Użytkownik
Posty: 1553
Rejestracja: 21 sie 2004, o 16:44
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 59 razy

trudne zadanie o szachownicy

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
Użytkownik
Użytkownik
Posty: 453
Rejestracja: 22 sie 2004, o 23:09
Płeć: Mężczyzna
Pomógł: 16 razy

trudne zadanie o szachownicy

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

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

Awatar użytkownika
g
Użytkownik
Użytkownik
Posty: 1553
Rejestracja: 21 sie 2004, o 16:44
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 59 razy

trudne zadanie o szachownicy

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
Gość Specjalny
Gość Specjalny
Posty: 534
Rejestracja: 8 lip 2004, o 17:05
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 1 raz
Pomógł: 17 razy

trudne zadanie o szachownicy

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

ODPOWIEDZ