Na płaszczyźnie znajduje się n punktów czerwonych i n punktów niebieskich. Udowodnij, że możemy połączyć je w n różnokolorowych par tak, że żadne dwa odcinki łączące punkty w parze nie przecinają się.
#1
Napisano 18.06.2014 - 14:37
Napisano 25.09.2011 - 17:55
#2
Napisano 18.06.2014 - 22:13
Tzn trzeba dorzucić założenie, że te punkty są w położeniu ogólnym, bo inaczej teza nie jest prawdziwa.
Najpierw łączymy dowolnie w różnokolorowe pary. Jeśli żadne dwa odcinki nie przecinają się , to OK. W przeciwnym razie, niech oraz będą przecinającymi się odcinkami. Wtedy zmazujemy te odcinki, a rysujemy oraz , które mają róznokolorowe końce i nie przecinają się.
W razie potrzeby powtarzamy wyżej opisaną procedurę aż do skutku.
#3
Napisano 19.06.2014 - 01:10
Miałem inny pomysł na dowód ale znalazłem kontrprzykład
Odcinakami tego nie połączysz, co przeczy
... że żadne dwa odcinki łączące punkty w parze nie przecinają się.
Ogólnie połączyć krzywymi można.
Co do mojego pomysłu na dowód z krzywymi
Łączymy dwa "skrajne" różnokolorowe punkty, po czym "odcinamy" je wraz z krzywą która je łączy. Następnie zajmujemy się następną parą punktów itd. Podział płaszczyzny na n rozłącznych obszarów jest zawsze możliwy więc każde dwa różnokolorowe punkty zostaną połączone krzywymi które się nie przecinają.
Jeśli rzuciłem choć promyczek światła na problem który postawiłeś - podziękuj. Nad kreską
#4
Napisano 19.06.2014 - 08:59
we wskazówce mam napisane żeby korzystać z dowodu nie wprost: wybrac najkrótszy odcinek miedzy punktami, i z nierówność trójkąta to wykazac