Zadania z kombinatoryki

[Angela09]

Czy mógłby ktoś pomóc mi rozwiązać poniższe zadania?

Zadanie 18 Udowodnij, że wśród dowolnych \(\displaystyle{ 7}\) różnych liczb całkowitych muszą być takie dwie, których suma lub różnica dzieli się przez \(\displaystyle{ 10}\).

Zadanie 19 Niech dany będzie zbiór \(\displaystyle{ 2016}\) liczb całkowitych \(\displaystyle{ a_1, a_2, . . . , a_{2016}}\). Wykaż, że istnieje w nim taki podzbiór, że suma wszystkich jego elementów jest podzielna przez \(\displaystyle{ 2016}\).

[Janusz Tracz]

18) Może nieformalnie ale oddaje to idee. Zauważmy najpierw, że zadanie można sprowadzić do skończonej liczby przypadków. Bo wybór siedmiu liczb całkowitych których suma lub różnica ma być podzielna przez \(\displaystyle{ 10}\) sprowadza się do sprawdzenia, że dla siedmiu reszt z dzielenia przez \(\displaystyle{ 10}\) znajdzie się taka suma lub różnica która przystaje do \(\displaystyle{ 0}\) modulo \(\displaystyle{ 10}\). Więc całość można na upartego sprawdzić w skończonej liczbie przypadków \(\displaystyle{ {10 \choose 7} }\) wybierając \(\displaystyle{ 7}\) z elementów \(\displaystyle{ \ZZ_{10}}\). Ale to było by, żmudne dlatego zauważymy, że wybierając \(\displaystyle{ 7}\) elementów \(\displaystyle{ \ZZ_{10}}\) zawsze znajdzie się para \(\displaystyle{ r_1,r_2\in\ZZ_{10}}\) taka, że \(\displaystyle{ r_1+r_2}\) dzieli się przez \(\displaystyle{ 10}\). Wynika to z zasady szufladkowania i widać to patrząc na pewien schemat:

\(\displaystyle{ \text{jeśli wybierzemy } r_1=0 \text{ to } r_2 \text{ nie może być równe } 0 \text{ aby teza nie była spełniona} }\)
\(\displaystyle{ \text{jeśli wybierzemy } r_1=1 \text{ to } r_2 \text{ nie może być równe } 9 \text{ aby teza nie była spełniona}}\)
\(\displaystyle{ \text{jeśli wybierzemy } r_1=2 \text{ to } r_2 \text{ nie może być równe } 8 \text{ aby teza nie była spełniona}}\)
\(\displaystyle{ \text{jeśli wybierzemy } r_1=3 \text{ to } r_2 \text{ nie może być równe } 7 \text{ aby teza nie była spełniona}}\)
\(\displaystyle{ \text{jeśli wybierzemy } r_1=4 \text{ to } r_2 \text{ nie może być równe } 6 \text{ aby teza nie była spełniona}}\)
\(\displaystyle{ \text{jeśli wybierzemy } r_1=5 \text{ to } r_2 \text{ nie może być równe } 5 \text{ aby teza nie była spełniona}}\)

dalej symetrycznie. Jednak zauważymy, że mamy \(\displaystyle{ 6}\) takich reguł (reguł wybierania licz) a my wybieramy \(\displaystyle{ 7}\) więc co najmniej jedna nie będzie spełniona.

[Angela09]

super, bardzo dziękuję!:)