[Kombinatoryka] 2 x kombi

pawelsuz · Post autor: **pawelsuz** » 27 wrz 2009, o 11:14

1) Na plaszczyźnie mamy N białych i N czarnych punktów. Żadne 3 sposród tych 2N punktow nie są współliniowe. Udowodnić, że mozna te punkty połączyć N nieprzecinającymi się odcinkami tak, aby każdy odcinek łączył biały punkt z czarnym.
2) Kwadrat o boku n podzielono na \(\displaystyle{ n^{2}}\) kwadratów jednostkowych. Wyznaczyć wszystkie naturalne n, dla których można ten kwadrat podzielić wzdłuż linii podziału na kwadraty, z których każdy ma krawędź długości 2 lub 3.

Dumel · Post autor: **Dumel** » 27 wrz 2009, o 11:33

1. udowodnij nie wprost że warunki zadania spełnia N odcinków o najmniejszej możliwej sumie długości

abc666 · Post autor: **abc666** » 27 wrz 2009, o 13:02

2. Oczywiście, możliwe jest to tylko dla kwadratów o polu \(\displaystyle{ 6p}\) gdzie \(\displaystyle{ p \in \mathbb{Z}}\). Niech nasz kwadrat ma bok równy \(\displaystyle{ 6k+a}\) gdzie \(\displaystyle{ k \in \mathbb{Z}}\) oraz \(\displaystyle{ a \in \{0,1,2,3,4,5\}}\). Wtedy pole równe jest \(\displaystyle{ 36k^2+12ak+a^2}\). Pierwsze dwa składniki są podzielne przez 6. \(\displaystyle{ a^2}\) jest podzielne przez 6 tylko wtedy jeśli \(\displaystyle{ a=0}\) stąd rozwiązaniem są n podzielne przez 6. Łatwo pokazać sposób konstruowania takich kwadratów. Po prostu łączymy odpowiednią ilość kwadratów o boku 6.

Jakieś za łatwe to zadanie.

Dumel · Post autor: **Dumel** » 27 wrz 2009, o 13:27

abc chyba źle zrozumiałeś treść zadania.
dla n podzielnych przez 2 lub 3 banał
jeżeli n daje resztę 1 z dzielenia przez 6, to sprawę załatwia takie pokolorowanie: (przykład dla n=13) liczba szarych pól jest nieparzysta, a każdy kwadrat o boku 2 lub 3 przysłania ich parzystą liczbę więc pokrycie nie jest możliwe.

dla reszty 5 można podobnie, jeśli pawelsuz będziesz miał dalej kłopoty, napiszę jak.

abc666 · Post autor: **abc666** » 27 wrz 2009, o 14:26

Hahaha wizyta u okulisty się przybliża :/. Dwa razy czytałem treść i widziałem tam "pola o boku 2 i 3". o_O

pawelsuz · Post autor: **pawelsuz** » 27 wrz 2009, o 16:29

Dumel pisze: liczba szarych pól jest nieparzysta, a każdy kwadrat o boku 2 lub 3 przysłania ich parzystą liczbę więc pokrycie nie jest możliwe.

Chyba coś źle zrozumialem, bo kwadrat o boku 3 zajmuje 9 pól, czyli nieparzysta...
i ogólnie średnio kumam to rozwiązanie, które zapewne jest poprawne, ale nie mogę tego ogarnąć:/

Klorel · Post autor: **Klorel** » 27 wrz 2009, o 16:34

Spójrz na pokolorowanie i szare pola

Dumel · Post autor: **Dumel** » 27 wrz 2009, o 21:04

pawelsuz pisze:
Dumel pisze: liczba szarych pól jest nieparzysta, a każdy kwadrat o boku 2 lub 3 przysłania ich parzystą liczbę więc pokrycie nie jest możliwe.
Chyba coś źle zrozumialem, bo kwadrat o boku 3 zajmuje 9 pól, czyli nieparzysta...
i ogólnie średnio kumam to rozwiązanie, które zapewne jest poprawne, ale nie mogę tego ogarnąć:/

chodziło o to, że przysłania parzystą liczbę szarych pól

pawelsuz · Post autor: **pawelsuz** » 27 wrz 2009, o 21:19

Skumałem o co chodzi na boisku:d Dzięki Dumel!

patry93 · Post autor: **patry93** » 25 gru 2009, o 16:13

Mały odkop.

Dumel pisze:1. udowodnij nie wprost że warunki zadania spełnia N odcinków o najmniejszej możliwej sumie długości

Mógłby ktoś pokazać, jak?

Dumel · Post autor: **Dumel** » 25 gru 2009, o 22:30

gdyby się wtedy jakieś odcinki AB i CD przecinały - powiedzmy w punkcie X, to mamy sprzeczność bo połączenie A-C i B-D daje mniejszą sumę (dwie nierówności trójkąta)