Trener OMJ

Zadania

Nauka

Zadanie 3

2017
Etap III
★★★★☆
Kombinatoryka
Teoria liczb
Kolorowanie liczb

Powiązane zadania:

Zad. 3 (2021)
Zad. 2 (2006)
Treść zadania
Niech nn będzie dodatnią liczbą całkowitą. Każdą z liczb 1,2,3,…,10001, 2, 3, \ldots, 1000 pomalowano jednym z nn kolorów. Okazało się, że każde dwie liczby, z których jedna jest dzielnikiem drugiej są pomalowane różnymi kolorami. Wyznacz najmniejszą liczbę nn, dla której taka sytuacja jest możliwa.
Zadania PDFRozwiązania PDF
Zgłoś błąd
Umiejętności (5)
Wymagane umiejętności:
Podzielność
Zasada ekstremalna
Konstrukcja przykładu
Zdobywane umiejętności:
Podzielność
Konstrukcja przykładu
Wskazówki (0/4)
Wskazówka 1
Zastanów się, co oznacza warunek z zadania. Jeśli masz ciąg liczb a1,a2,…,aka_1, a_2, \ldots, a_k taki, że a1∣a2∣…∣aka_1 | a_2 | \ldots | a_k, to ile co najmniej kolorów potrzeba, aby je pomalować?
Wskazówka 2
Aby znaleźć najmniejszą możliwą liczbę kolorów, poszukaj najdłuższego łańcucha podzielności a1∣a2∣…∣aka_1 | a_2 | \ldots | a_k wśród liczb od 1 do 1000. Długość tego łańcucha da dolne ograniczenie na nn.
Wskazówka 3
Aby łańcuch podzielności był jak najdłuższy, kolejne liczby powinny rosnąć jak najwolniej. Rozważ ciąg, w którym każda następna liczba jest dwukrotnością poprzedniej, zaczynając od 1.
Wskazówka 4
Udowodnij, że znaleziona liczba kolorów wystarcza. Zdefiniuj kolor liczby mm jako liczbę jej czynników pierwszych, liczonych z krotnościami (np. dla 12=22⋅312=2^2 \cdot 3 ta liczba to 2+1=32+1=3). Sprawdź, czy to kolorowanie jest poprawne.
Prześlij rozwiązanie

Zaloguj się, aby przesłać swoje rozwiązanie

Zaloguj się