szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 21 sie 2015, o 16:51 
Użytkownik

Posty: 92
Lokalizacja: Garwolin
Mam takie zadanko:

Wykazać, że z dowolnego zbioru 100 dodatnich liczb całkowitych można tak wybrać pewien niepusty podzbiór, by suma liczb z tego podzbioru była podzielna przez 100.

Wychodzę od tego, że gdyby jakakolwiek liczba wśród tych wybranych była podzielna przez 100, to mamy tezę (podzbiór jednoelementowy), więc rozważmy zbiór w którym są same niepodzielne prez 100 liczby. Wtedy reszty z dzielenia tych liczb przez 100 należą do zbioru \left\{ 1, 2, ..., 99\right\} Zauważyłem, że gdyby resztom n i 100-n były przypisane liczby, to mamy tezę. To samo się tyczy liczb n, 50-n, m, 50-m. Tylko kompletnie nie wiem jak wykorzystać to do rozwiązania zadania. Myślę, że da się jakoś z tego rozumowania wyciągnąć tezę, ale nie mogę do niej dojść. Co należy zrobić?

Pozdrawiam.
Góra
Mężczyzna Offline
PostNapisane: 21 sie 2015, o 16:57 
Gość Specjalny
Avatar użytkownika

Posty: 9097
Lokalizacja: Łódź
Niech X=\{x_{1}, x_{2},..,x_{100}\}. Rozważ następujące sumy:
S_{1}=x_{1} \\\ S_{2}=x_{1}+x_{2} \\ ... \\ S_{100}=x_{1}+x_{2}+...+x_{100}
Góra
Mężczyzna Offline
PostNapisane: 21 sie 2015, o 17:05 
Użytkownik

Posty: 92
Lokalizacja: Garwolin
Takie rozwiązanie jest w broszurze, ale nie rozumiem tego. Przecież to nam nie daje dowodu na to, że któraś suma będzie podzielna przez 100. Może ktoś mi objaśnić czego nie widzę?
Góra
Mężczyzna Offline
PostNapisane: 21 sie 2015, o 17:10 
Gość Specjalny
Avatar użytkownika

Posty: 9097
Lokalizacja: Łódź
Jeżeli któraś suma jest podzielna przez 100 to jest koniec zadania. W przeciwnym wypadku istnieją dwie sumy (S_{i}, S_{j}, i>j) dające tą samą resztę przy dzieleniu przez 100. Stąd podzielne przez 100 jest S_{i}-S_{j}. Zauważmy, że:
S_{i}-S_{j}=x_{j+1}+...+x_{i},
czyli x_{j+1}+...+x_{i} jest podzielne przez 100. Oznacza to, że podzbiór \{x_{j+1},..,x_{i}\} \subset X spełnia warunek z zadania.
Góra
Mężczyzna Offline
PostNapisane: 21 sie 2015, o 17:16 
Użytkownik

Posty: 92
Lokalizacja: Garwolin
Dzięki wielkie :)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Podzielność przez 100 - zadanie 3  Ruahyin  1
 podzielnosc przez 100  ttoommeekkzz  1
 wykaż, że liczba jest podzielna przez 10  pawel6582  5
 Zasada Szufladkowa, podzielność  Milczek  1
 Uzasadnienie podzielności wyrażenia przez 120.  Valiors  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl