Witam, oto kilka zadań, które sprawiły mi trudność. Dodam od siebie, że sugerowane rozwiązania są metodą szufladkową.
Zadanie 1.22. Pokazac, ze dla dowolnych n + 1 róznych dodatnich liczb
całkowitych mniejszych badz równych 2n istnieja dwie, które sumuja sie do
2n + 1.
Zadanie 1.23. Pokazac, ze dla dowolnych n + 1 róznych dodatnich liczb
całkowitych mniejszych badz równych 2n istnieja dwie, które sa wzglednie
pierwsze.
Zadanie 1.24. Pokazac, ze dla dowolnych n dodatnich liczb całkowitych
istnieje podzbiór, którego suma liczb jest podzielna przez n.
Zadanie 1.25. Niech A bedzie dwudziestoelementowym podzbiorem zbioru
{1, 4, 7, 10, 13, . . ., 100}. Udowodnij, ze A zawiera dwie rózne liczby, których
suma jest równa 104.
Zadanie 1.26. Niech dla ustalonego n naturalnego A bedzie podzbiorem
mocy n + 1 zbioru [2n]. Udowodnic, ze A zawiera dwie rózne liczby a i b,
takie ze a jest dzielnikiem b.
Metody dowodzenia twierdzeń
- jarekp
- Użytkownik
- Posty: 173
- Rejestracja: 7 paź 2007, o 14:40
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 1 raz
- Pomógł: 56 razy
Metody dowodzenia twierdzeń
zadanie 1.22
sumę 2n za pomocą liczb od 1 do n możemy uzyskać na n sposobów.
mamy więc n szufladek(każda reprezentuje 1 sposób uzyskania sumy 2n+1). do nich 'wkładamy' liczby (w taki sposób, że np. do szufladki która reprezentuje sposób uzyskania sumy 2n+1 za pomocą liczb a i b wkładamy liczbę a lub b)
mamy więc rozmieścić n+1 liczb w n szufladkach czyli w jednej znajdą się dwie liczby.
Liczby te dają więc sumę 2n+1 c.n.u
[ Dodano: 10 Października 2007, 09:57 ]
1.23
podzielmy przedział na n części. Będą to nasze szufladki. Każda szufladka odpowiada dwóm kolejnym liczbom z przedziału w następujący sposób:
1 szufladka odpowiada liczbom 1,2
szufladka 2 liczbom 3,4 a szufladka n liczbom 2n-1,2n itp.
Mamy więc n szufladek i rozmieszczamy w nich n+1 liczb. W takim razie w jednej szufladce na pewno znajdą sie dwie liczby.będą więc one kolejnymi liczbami naturalnymi czyli będą względnie pierwsze. c.n.u.
reszta jak wrócę z zajęć
[ Dodano: 10 Października 2007, 13:52 ]
1.25 wychodzi zbyt optymistycznie- są dwie takie pary liczb:) oto moje rozwiązanie:
sumę 104 z liczb w podanym zbiorze możemy otrzymać na 16 sposobów.
Będą to nasze szufladki(każda reprezentuje 1 sposób uzyskania sumy 104)
wkładamy do nich(na zasadzie takiej samej jak w rozwiązaniu zadania 1.22) 20 liczb z danego podzbioru
mamy dwie sytuacje: w owym 20 elementowym podzbiorze znalazły się liczby 1 i 52
i sytuacje przeciwną. Rozważamy sytuację pierwszą(1 i 52 są w podzbiorze) jako mniej korzystną.
tych liczb nie możemy umieścić w szufladkach gdyż nie istnieją odpowiadające im szufladki(te liczby nie dają z żadną inną liczbą ze zbioru A sumy 104)
Pozostaje nam zatem rozmieścić 20-2 liczb w 16 szufladkach czyli zgodnie z zasadą dirichleta
w pewnej szufladce będą na pewno 2 liczby. Będą ona dawały sumę 104 c.n.u.
PS.Rozmieszczamy 18 liczb w 16 szufladkach czyli dostaniemy dwie szufladki w których będą dwie liczby. To jest podejrzane bo zwykle wychodzi jedna Na wszelki wypadek sprawdź czy sumy nie można uzyskać na 17 sposobów. Oczywiście nie liczyłem tego wypisując wszystkie możliwości stąd mógł się pojawić błąd
[ Dodano: 10 Października 2007, 14:33 ]
1.24
mamy n liczb: \(\displaystyle{ a_{1}, a_{2}, ... , a_{n}}\)
tworzymy następujące podzbiory i ich sumy:
\(\displaystyle{ a_{1}}\) suma =\(\displaystyle{ a_{1}}\)
\(\displaystyle{ {a_{1},a_{2}}}\) suma =\(\displaystyle{ a_{1}+a_{2}}\)
\(\displaystyle{ ...}\)
\(\displaystyle{ a_{1}, ... , a_{n}}\) suma\(\displaystyle{ =a_{1}+a_{2}+... +a_{n}}\)
każda z tych sum jest różna i jest ich n.
Jeśli któraś z nich jest podzielna przez n to koniec zadania
Jeśli nie to znaczy że przy dzieleniu przez n dają reszty różne od zera.
takich reszt jest n-1 a sum jest n. A więc z zasady dirichleta wynika że pewne dwie sumy mają takie same reszty.
jeśli więc odejmiemy te sumy od siebie otrzymamy liczbę podzielną przez n.
niech będą to sumy
\(\displaystyle{ a_{1}+a_{2}+... +a_{k}}\) i \(\displaystyle{ a_{1}+a_{2}+... +a_{l}}\) ,k>l
odpowiadają im zbiory\(\displaystyle{ a_{1}, ... , a_{k}}\) i \(\displaystyle{ a_{1}, ... , a_{l}}\)
Zatem suma \(\displaystyle{ a_{1}+a_{2}+... +a_{k}-(a_{1}+a_{2}+... +a_{l})=a_{k}+... +a_{l+1}}\) jest podzielna przez n.
i odpowiadający jej podzbiór to\(\displaystyle{ a_{l+1}, ... , a_{k}}\) c.n.u.
sumę 2n za pomocą liczb od 1 do n możemy uzyskać na n sposobów.
mamy więc n szufladek(każda reprezentuje 1 sposób uzyskania sumy 2n+1). do nich 'wkładamy' liczby (w taki sposób, że np. do szufladki która reprezentuje sposób uzyskania sumy 2n+1 za pomocą liczb a i b wkładamy liczbę a lub b)
mamy więc rozmieścić n+1 liczb w n szufladkach czyli w jednej znajdą się dwie liczby.
Liczby te dają więc sumę 2n+1 c.n.u
[ Dodano: 10 Października 2007, 09:57 ]
1.23
podzielmy przedział na n części. Będą to nasze szufladki. Każda szufladka odpowiada dwóm kolejnym liczbom z przedziału w następujący sposób:
1 szufladka odpowiada liczbom 1,2
szufladka 2 liczbom 3,4 a szufladka n liczbom 2n-1,2n itp.
Mamy więc n szufladek i rozmieszczamy w nich n+1 liczb. W takim razie w jednej szufladce na pewno znajdą sie dwie liczby.będą więc one kolejnymi liczbami naturalnymi czyli będą względnie pierwsze. c.n.u.
reszta jak wrócę z zajęć
[ Dodano: 10 Października 2007, 13:52 ]
1.25 wychodzi zbyt optymistycznie- są dwie takie pary liczb:) oto moje rozwiązanie:
sumę 104 z liczb w podanym zbiorze możemy otrzymać na 16 sposobów.
Będą to nasze szufladki(każda reprezentuje 1 sposób uzyskania sumy 104)
wkładamy do nich(na zasadzie takiej samej jak w rozwiązaniu zadania 1.22) 20 liczb z danego podzbioru
mamy dwie sytuacje: w owym 20 elementowym podzbiorze znalazły się liczby 1 i 52
i sytuacje przeciwną. Rozważamy sytuację pierwszą(1 i 52 są w podzbiorze) jako mniej korzystną.
tych liczb nie możemy umieścić w szufladkach gdyż nie istnieją odpowiadające im szufladki(te liczby nie dają z żadną inną liczbą ze zbioru A sumy 104)
Pozostaje nam zatem rozmieścić 20-2 liczb w 16 szufladkach czyli zgodnie z zasadą dirichleta
w pewnej szufladce będą na pewno 2 liczby. Będą ona dawały sumę 104 c.n.u.
PS.Rozmieszczamy 18 liczb w 16 szufladkach czyli dostaniemy dwie szufladki w których będą dwie liczby. To jest podejrzane bo zwykle wychodzi jedna Na wszelki wypadek sprawdź czy sumy nie można uzyskać na 17 sposobów. Oczywiście nie liczyłem tego wypisując wszystkie możliwości stąd mógł się pojawić błąd
[ Dodano: 10 Października 2007, 14:33 ]
1.24
mamy n liczb: \(\displaystyle{ a_{1}, a_{2}, ... , a_{n}}\)
tworzymy następujące podzbiory i ich sumy:
\(\displaystyle{ a_{1}}\) suma =\(\displaystyle{ a_{1}}\)
\(\displaystyle{ {a_{1},a_{2}}}\) suma =\(\displaystyle{ a_{1}+a_{2}}\)
\(\displaystyle{ ...}\)
\(\displaystyle{ a_{1}, ... , a_{n}}\) suma\(\displaystyle{ =a_{1}+a_{2}+... +a_{n}}\)
każda z tych sum jest różna i jest ich n.
Jeśli któraś z nich jest podzielna przez n to koniec zadania
Jeśli nie to znaczy że przy dzieleniu przez n dają reszty różne od zera.
takich reszt jest n-1 a sum jest n. A więc z zasady dirichleta wynika że pewne dwie sumy mają takie same reszty.
jeśli więc odejmiemy te sumy od siebie otrzymamy liczbę podzielną przez n.
niech będą to sumy
\(\displaystyle{ a_{1}+a_{2}+... +a_{k}}\) i \(\displaystyle{ a_{1}+a_{2}+... +a_{l}}\) ,k>l
odpowiadają im zbiory\(\displaystyle{ a_{1}, ... , a_{k}}\) i \(\displaystyle{ a_{1}, ... , a_{l}}\)
Zatem suma \(\displaystyle{ a_{1}+a_{2}+... +a_{k}-(a_{1}+a_{2}+... +a_{l})=a_{k}+... +a_{l+1}}\) jest podzielna przez n.
i odpowiadający jej podzbiór to\(\displaystyle{ a_{l+1}, ... , a_{k}}\) c.n.u.