szukanie zaawansowane
 [ Posty: 8 ] 
Autor Wiadomość
Mężczyzna Online
PostNapisane: 17 sty 2017, o 19:43 
Użytkownik
Avatar użytkownika

Posty: 982
Lokalizacja: Jasło/Kraków
Mamy 66 niewspółliniowych punktów na płaszczyźnie. Wszystkie łączymy odcinkami
koloru czerwonego, żółtego, zielonego lub niebieskiego. Udowodnij, że zawsze
znajdzie się trójkąt jednego koloru.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 18 sty 2017, o 02:40 
Moderator

Posty: 4299
Lokalizacja: Kraków PL
Jeżeli są trójkami niewspółliniowe, to można z nich zbudować {66\choose3}\!=45760 trójkątów. Boki każdego trójkąta są oznaczone poczwórnie kolorami, więc takich jednokolorowych trójkątów będzie dokładnie 4\cdot45760=183040 , a 183040>1 .
Góra
Mężczyzna Offline
PostNapisane: 18 sty 2017, o 17:24 
Użytkownik
Avatar użytkownika

Posty: 3272
Lokalizacja: blisko
Nie widzi mi się to rozwiązanie
Góra
Mężczyzna Offline
PostNapisane: 18 sty 2017, o 19:59 
Użytkownik

Posty: 1086
Lokalizacja: Lublin/Warszawa
Bardzo znane zadanie.

Można to przepisać na terminologię grafową: klika 66 wierzchołkowa, której krawędzie kolorujemy 4 kolorami. Trzeba pokazać, że znajdzie się monochromatyczny trójkąt.
Tak naprawdę to zadanie jest związane z liczbami i twierdzeniem Ramsey'a - zachodzi R\left(3, 3, 3, 3 \right)  \le 66.
https://pl.wikipedia.org/wiki/Twierdzenie_Ramseya

Podobne zadanie tutaj (zawodnicy to wierzchołki, a miasta to kolory krawędzi) - rozwiązanie:
http://archom.ptm.org.pl/?q=node/780
Góra
Mężczyzna Offline
PostNapisane: 18 sty 2017, o 20:12 
Moderator

Posty: 4299
Lokalizacja: Kraków PL
Nie ulega wątpliwości, że wszystkie (punkty) należy rozumieć jako każdą parę.
Mruczek miałby rację, gdyby w temacie zadania było: każdą parę łączymy odcinkiem o jednym z czterech kolorów.
Góra
Mężczyzna Offline
PostNapisane: 18 sty 2017, o 20:21 
Użytkownik
Avatar użytkownika

Posty: 3272
Lokalizacja: blisko
Tu jest dokładnie to samo:

https://www.matematyka.pl/414064.htm#p5460606
Góra
Mężczyzna Offline
PostNapisane: 18 sty 2017, o 20:35 
Użytkownik

Posty: 1086
Lokalizacja: Lublin/Warszawa
SlotaWoj napisał(a):
Nie ulega wątpliwości, że wszystkie (punkty) należy rozumieć jako każdą parę.
Mruczek miałby rację, gdyby w temacie zadania było: każdą parę łączymy odcinkiem o jednym z czterech kolorów.


Tak, autor temat po prostu się przejęzyczył. Jestem pewny, że chodziło o moją (i arek1357 wersję). To znane zadanie, liczba 66 i cztery kolory na to wskazują.
Góra
Mężczyzna Online
PostNapisane: 18 sty 2017, o 20:38 
Użytkownik
Avatar użytkownika

Posty: 982
Lokalizacja: Jasło/Kraków
Dziękuje za źródła.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 8 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 punkty i odcinki  Anonymous  1
 Punkty połączone odcinkiem  cain11  0
 Ile prostych wyznaczają punkty na płaszczyźnie  Waylays  7
 jak sprawdzić punkty wspólne dwóch ciągów - zadanie 3  Rebus27  6
 punkt w kole, punkty na trójkącie, punkty na okręgu.  piotrek9299  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl