Zasada pudełkowa beemos: Korzystając z zasady pudełkowej udowodnij poniższe twierdzenie: W każdym zbiorze złożonym z n liczb naturalnych istnieje podzbiór, którego suma elementów dzieli się przez n. Doszedłem do wniosku że jeśli którakolwiek z liczb jest podzielna przez n to nie trzeba niczego udowadniać, natomiast jeśli żadna z liczb nie jest podzielna przez n to daje ona resztę z dzielenia przez n należącą do przedziału {1,2, ... ,n−1}. A więc liczb jest n a szufladek na resztę z dzielenia n−1,więc w co najmniej jednej szufladce będą liczby o takiej samej reszcie z dzielenie. Tylko teraz jak udowodnić że istnieje podzbiór liczb których suma daje liczbę podzielną przez n? (bo rzeczywiście tak jest)
24 mar 17:27
24 mar 18:01
wredulus_pospolitus: A co Ci daje, że masz dwie liczby o tej samej reszcie, skoro tutaj mowa o SUMIE liczb, a nie różnicy
24 mar 18:02
beemos: a7: Dzięki, już rozumiem jak to rozwiązać chociaż sam bym na to pewnie nie wpadł. wredulus pospolitus: Tak, masz rację. Po prostu gdy wyliczałem wszystkie możliwe sumy podzbiorów to nie pasowało to do zasady szufladkowej Dirichleta i też za bardzo nie wiedziałem co z tym można zrobić, więc intuicyjnie pomyślałem że można to udowodnić przedstawiając sumy reszt z dzielenia poszczególnych liczb, ale rozwiązanie okazuje się prostsze chociaż trudno je wymyślić.
24 mar 18:32
a7: bardzo proszę emotka
24 mar 18:49