Zadanie 2
2005
Etap II
★★★★☆Teoria liczb
Kombinatoryka
111 liczb - suma podzielna przez 11
Powiązane zadania:
Zad. 3 (2005)
Treść zadania
Danych jest 111 dodatnich liczb całkowitych. Wykaż, że spośród nich można wybrać 11 takich liczb, których suma jest podzielna przez 11.
Umiejętności (4)
Wymagane umiejętności:
Zasada szufladkowa
Reszty z dzielenia
Zdobywane umiejętności:
Zasada szufladkowa
Reszty z dzielenia
Wskazówki (0/4)
Wskazówka 1
Problem dotyczy podzielności przez 11, więc kluczowe będą reszty. Ile jest możliwych reszt z dzielenia przez 11? Spróbuj pogrupować dane 111 liczb według tych reszt.
Wskazówka 2
Masz 111 liczb i 11 grup (reszt). Czy ta dysproporcja nie sugeruje użycia zasady szufladkowej Dirichleta? Określ, co jest 'gołębiami', a co 'szufladkami'.
Wskazówka 3
Zastosuj zasadę szufladkową do 111 liczb i 11 reszt. Jaki jest minimalny gwarantowany rozmiar jednej z grup liczb, które mają tę samą resztę?
Wskazówka 4
Wiesz już, że istnieje grupa co najmniej 11 liczb o tej samej reszcie . Wybierz z niej 11 liczb. Jaka będzie reszta z dzielenia ich sumy przez 11?