Zadanie 3
2005
Etap III
★★★★☆Kombinatoryka
Logika
Kolorowanie odcinków w przestrzeni
Treść zadania
W przestrzeni danych jest takich punktów (), że żadne cztery nie leżą na jednej płaszczyźnie. Każde dwa z tych punktów połączono odcinkiem niebieskim lub czerwonym. Udowodnij, że można tak wybrać jeden z tych kolorów, aby każde dwa punkty były połączone odcinkiem lub łamaną wybranego koloru.
Umiejętności (5)
Wymagane umiejętności:
Grafy
Dowód nie wprost
Analiza przypadków
Zdobywane umiejętności:
Grafy
Dowód nie wprost
Wskazówki (0/4)
Wskazówka 1
Wyobraź sobie punkty jako wierzchołki grafu, a kolorowe odcinki jako krawędzie. Co oznacza, że dwa punkty są 'połączone odcinkiem lub łamaną' tego samego koloru? Jak to się ma do pojęcia spójności grafu?
Wskazówka 2
Zastosuj dowód nie wprost. Załóż, że ani graf niebieski, ani czerwony nie jest spójny. Co to oznacza dla każdego z nich?
Wskazówka 3
Jeśli graf niebieski jest niespójny, to zbiór punktów można podzielić na dwa niepuste zbiory, i , bez żadnych niebieskich odcinków między nimi. Jaki kolor muszą mieć wszystkie odcinki łączące z ? Zastosuj tę samą logikę do niespójnego grafu czerwonego.
Wskazówka 4
Masz teraz dwa podziały punktów: na zbiory oraz na . Każdy punkt należy więc do jednej z czterech grup (np. do i jednocześnie do ). Zbadaj kolory odcinków między punktami z różnych grup, aby znaleźć sprzeczność.