Zadanie z zasady szufladkowej
-
robertm19
- Użytkownik
- Posty: 1847
- Rejestracja: 8 lip 2008, o 21:16
- Płeć: Mężczyzna
- Lokalizacja: Staszów/Warszawa
- Podziękował: 7 razy
- Pomógł: 378 razy
Zadanie z zasady szufladkowej
Niech s będzie zbiorem 17 punktów niewspółliniowych. Punkty te łączymy odcinkami i kolorujemy odcinki na żółto, niebieski i czerwono. Wykazać, że istniej zawsze trójkąt o krawędziach tego samego koloru.
-
patry93
- Użytkownik
- Posty: 1251
- Rejestracja: 30 sty 2007, o 20:22
- Płeć: Mężczyzna
- Lokalizacja: Koziegłówki/Wrocław
- Podziękował: 352 razy
- Pomógł: 33 razy
Zadanie z zasady szufladkowej
Luźne pomysły:
1) Wszystkich odcinków masz jeśli się nie mylę \(\displaystyle{ \frac{17 \cdot 16}{2} = 136}\).
Masz 3 kolory, więc z Uogólnionej Zasady Szufladkowej Dirichleta, skoro \(\displaystyle{ 136 = 45 \cdot 3 + 1}\), to co najmniej 46 pewnych odcinków jest jednego koloru. Ciężko teraz coś z tego wywnioskować, ale być może da się to ruszyć dalej (ja mam zaćmę )
2) Z UZSD skoro \(\displaystyle{ 16=5 \cdot 3 + 1}\) to z pewnego punktu (niech to będzie A) wychodzi co najmniej 6 odcinków jednego koloru (niech ich końce będą w punktach B, C, D, E, F, G). Niech tym kolorem będzie czerwony. Jeśli odcinki o początkach i końcach w punktach B, ..., G są czerwone, to mamy trójkąt, więc załóżmy bez straty ogólności, że są niebieskie. Mamy więc \(\displaystyle{ \frac{6!}{2! (6-2)!} = 15}\) odcinków niebieskich. No, ale co to oznacza? Jeśli się nie mylę, to to, że uzyskaliśmy aż kilka(!?) trójkątów niebieskich (np. BC, BD, CD są niebieskie, więc BCD jest niebieskim trójkątem).
Nie daję głowy, że to jest dobrze, więc prosiłbym również o sprawdzenie
-- 21 marca 2009, 18:53 --
O, i przy okazji - treść zadania chyba (nie jestem pewny) posiada błąd Tzn. nie "17 punktów niewspółliniowych", bo wtedy może się zdarzyć np. 10 punktów współliniowych, ale powinno być raczej "17 punktów takich, że każde 3 są niewspółliniowe" -- 21 marca 2009, 21:47 --Aha! Widzę błąd!
No, teraz już powinno być dobrze, ale nadal proszę o sprawdzenie
1) Wszystkich odcinków masz jeśli się nie mylę \(\displaystyle{ \frac{17 \cdot 16}{2} = 136}\).
Masz 3 kolory, więc z Uogólnionej Zasady Szufladkowej Dirichleta, skoro \(\displaystyle{ 136 = 45 \cdot 3 + 1}\), to co najmniej 46 pewnych odcinków jest jednego koloru. Ciężko teraz coś z tego wywnioskować, ale być może da się to ruszyć dalej (ja mam zaćmę )
2) Z UZSD skoro \(\displaystyle{ 16=5 \cdot 3 + 1}\) to z pewnego punktu (niech to będzie A) wychodzi co najmniej 6 odcinków jednego koloru (niech ich końce będą w punktach B, C, D, E, F, G). Niech tym kolorem będzie czerwony. Jeśli odcinki o początkach i końcach w punktach B, ..., G są czerwone, to mamy trójkąt, więc załóżmy bez straty ogólności, że są niebieskie. Mamy więc \(\displaystyle{ \frac{6!}{2! (6-2)!} = 15}\) odcinków niebieskich. No, ale co to oznacza? Jeśli się nie mylę, to to, że uzyskaliśmy aż kilka(!?) trójkątów niebieskich (np. BC, BD, CD są niebieskie, więc BCD jest niebieskim trójkątem).
Nie daję głowy, że to jest dobrze, więc prosiłbym również o sprawdzenie
-- 21 marca 2009, 18:53 --
O, i przy okazji - treść zadania chyba (nie jestem pewny) posiada błąd Tzn. nie "17 punktów niewspółliniowych", bo wtedy może się zdarzyć np. 10 punktów współliniowych, ale powinno być raczej "17 punktów takich, że każde 3 są niewspółliniowe" -- 21 marca 2009, 21:47 --Aha! Widzę błąd!
Tutaj jest źle, bo nie można założyć tego, że są niebieskie, bo mogą być żółte. Mamy zatem 6 punktów i 2 kolory. Znów z ZSD mamy co najmniej 3 odcinki (b. s. o. niebieskie) z jednego punktu, niech tym punktem będzie B i niech końce tych niebieskich odcinków znajdują się w punktach C, D, E. Jeśli odcinki stworzone z punktów C, D, E są niebieskie, to mamy trójkąt o niebieskich bokach, więc załóżmy, że są żółte. A to już oznacza, że mamy trójkąt CDE o żółtych bokach, co kończy dowód.Jeśli odcinki o początkach i końcach w punktach B, ..., G są czerwone, to mamy trójkąt, więc załóżmy bez straty ogólności, że są niebieskie.
No, teraz już powinno być dobrze, ale nadal proszę o sprawdzenie