Metody dowodzenia twierdzeń

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Kropek999
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 9 paź 2007, o 23:03
Płeć: Mężczyzna
Lokalizacja: Wwa

Metody dowodzenia twierdzeń

Post autor: Kropek999 » 9 paź 2007, o 23:06

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.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
jarekp
Użytkownik
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ń

Post autor: jarekp » 10 paź 2007, o 09:38

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ęć :mrgreen:

[ 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 :D 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.

:mrgreen:

gmpkm
Użytkownik
Użytkownik
Posty: 37
Rejestracja: 22 mar 2009, o 00:10
Płeć: Mężczyzna
Pomógł: 5 razy

Metody dowodzenia twierdzeń

Post autor: gmpkm » 22 mar 2009, o 10:24

A co z zadankiem 1.26?

ODPOWIEDZ