Zadanie 3
2021
Etap II
★★★★☆Kombinatoryka
Teoria liczb
Kolorowanie liczb
Treść zadania
Niech będzie dodatnią liczbą całkowitą. Każdą z liczb pomalowano jednym z kolorów w taki sposób, że każde dwie różne liczby o sumie podzielnej przez zostały pomalowane różnymi kolorami. Wyznacz najmniejszą liczbę , dla której taka sytuacja jest możliwa.
Umiejętności (5)
Wymagane umiejętności:
Reszty z dzielenia
Grafy
Ciągi liczbowe
Zdobywane umiejętności:
Zasada szufladkowa
Grafy
Wskazówki (0/4)
Wskazówka 1
Pogrupuj liczby od 1 do 100 według ich reszt z dzielenia przez 4. Kiedy suma dwóch różnych liczb jest podzielna przez 4, w zależności od ich reszt?
Wskazówka 2
Zastanów się, które zbiory liczb (o tych samych resztach) wymagają, aby każdy ich element miał inny kolor. Poszukaj największego takiego zbioru.
Wskazówka 3
Przeanalizuj grupy o resztach 0 i 2. Co wynika z warunku zadania dla kolorów liczb wewnątrz każdej z tych grup? Jaka jest zależność między kolorami liczb z grupy o reszcie 1 a kolorami z grupy o reszcie 3?
Wskazówka 4
Policz, ile jest liczb w każdej z czterech grup. Wykorzystaj swoje obserwacje, aby znaleźć dolne ograniczenie na liczbę kolorów . Czy potrafisz skonstruować poprawne kolorowanie przy użyciu tej liczby kolorów?