Trener OMJ

Zadania

Nauka

Zadanie 2

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

Powiązane zadania:

Zad. 5 (2017)
Zad. 5 (2017)
Treść zadania
Każdą liczbę całkowitą dodatnią pomalowano na pewien kolor. Okazało się, że dla każdej pary liczb całkowitych aa, bb większych od 11 liczby a+ba + b i abab są tego samego koloru. Wykaż, że wszystkie liczby większe od 44 zostały pomalowane tym samym kolorem.
Zadania PDFRozwiązania PDF
Zgłoś błąd
Umiejętności (5)
Wymagane umiejętności:
Podzielność
Analiza przypadków
Konstrukcja przykładu
Zdobywane umiejętności:
Niezmienniki
Analiza przypadków
Wskazówki (0/4)
Wskazówka 1
Zacznij od zbadania małych liczb. Używając par (a,b)(a,b) takich jak (2,3)(2,3), (3,3)(3,3) czy (3,4)(3,4), spróbuj pokazać, że liczby 5, 6, 7, 8, 9 muszą mieć ten sam kolor.
Wskazówka 2
Wykaż przez indukcję, że wszystkie liczby n>4n>4 mają ten sam kolor co liczba 6. Załóż, że to prawda dla liczb od 5 do n−1n-1 i udowodnij dla nn.
Wskazówka 3
Podziel dowód indukcyjny na dwa przypadki: gdy nn jest liczbą złożoną i gdy nn jest liczbą pierwszą. Zauważ, że dla n=abn=ab kolor zależy od koloru mniejszej liczby a+ba+b.
Wskazówka 4
Dla nn pierwszego (np. next≥11n ext{≥} 11), zapisz n=3+(n−3)n=3+(n-3). Kolor nn jest więc taki sam jak kolor liczby m=3(n−3)m=3(n-3). Znajdź dla mm taki rozkład na czynniki cext⋅dc ext{·} d, aby suma c+dc+d była mniejsza od nn.
Prześlij rozwiązanie

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

Zaloguj się