Zadanie 4
2012
Etap II
★★★★☆Kombinatoryka
Logika
Kolorowanie punktów płaszczyzny
Treść zadania
Każdy punkt płaszczyzny należy pomalować na pewien kolor w taki sposób, aby każda prosta była jednokolorowa lub dwukolorowa. Jaka jest największa możliwa liczba kolorów, których można użyć do pomalowania punktów tej płaszczyzny? Odpowiedź uzasadnij.
Umiejętności (5)
Wymagane umiejętności:
Analiza przypadków
Konstrukcja przykładu
Zdobywane umiejętności:
Analiza przypadków
Konstrukcja przykładu
Zasada ekstremalna
Wskazówki (0/4)
Wskazówka 1
Warunek zadania mówi, że na każdej prostej mogą być co najwyżej dwa kolory. Co z tego wynika, jeśli spróbujemy umieścić na jednej prostej trzy punkty o trzech różnych kolorach?
Wskazówka 2
Problem ma dwie części. Najpierw spróbuj udowodnić, że nie da się użyć pewnej liczby kolorów, np. czterech. Następnie podaj przykład kolorowania, które pokazuje, że mniejsza liczba kolorów jest możliwa.
Wskazówka 3
Załóż, że istnieją cztery punkty, każdy w innym kolorze. Co możemy powiedzieć o ich wzajemnym położeniu? Rozważ prostą przechodzącą przez dwa z nich i jej przecięcie z prostą łączącą dwa pozostałe.
Wskazówka 4
Aby pokazać, że trzy kolory są możliwe, rozważ prostą konstrukcję. Weź dwie przecinające się proste. Jak można pokolorować punkty na tych prostych i poza nimi, używając łącznie trzech kolorów?