Zadanie 3
2006
Etap II
★★★★☆Kombinatoryka
Logika
6 punktów i 10 odcinków - trójkąt
Treść zadania
W przestrzeni danych jest 6 punktów, z których żadne cztery nie leżą na jednej płaszczyźnie. Łącząc niektóre z tych punktów narysowano 10 odcinków. Wykaż, że w ten sposób uzyskano co najmniej jeden trójkąt.
Umiejętności (3)
Wymagane umiejętności:
Grafy
Dowód nie wprost
Zdobywane umiejętności:
Grafy
Wskazówki (0/4)
Wskazówka 1
Zastanów się, ile maksymalnie odcinków można narysować między 6 punktami. Ile odcinków 'brakuje' do pełnego połączenia wszystkich punktów?
Wskazówka 2
Rozważ sytuację odwrotną: zamiast patrzeć na narysowane odcinki, pomyśl o tych, których NIE narysowano. Co by się stało, gdyby trójkąt nie istniał?
Wskazówka 3
Policz, ile jest wszystkich możliwych trójek punktów. Zgodnie z założeniem, że nie ma trójkątów, każda taka trójka musi być 'zepsuta' przez co najmniej jeden brakujący odcinek.
Wskazówka 4
Mamy 5 brakujących odcinków. Każdy z nich 'psuje' 4 trójki, co daje łącznie 'zepsutych' trójek. Czy to gwarantuje, że wszystkie 20 *różnych* trójek jest zepsutych? Pomyśl, co się stanie, gdy dwa brakujące odcinki wychodzą z tego samego punktu.