02. Dirichletov Princip I Ramseyev Teorem
-
Upload
fantisimus -
Category
Documents
-
view
296 -
download
1
Transcript of 02. Dirichletov Princip I Ramseyev Teorem
-
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
1/36
DIRICHLETOV PRINCIP I RAMSEYEV TEOREM
() 21. listopada 2011. 1 / 16
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
2/36
DIRICHLETOV PRINCIP
-jedan od najjednostavnijih kombinatornih principa
() 21. listopada 2011. 2 / 16
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
3/36
DIRICHLETOV PRINCIP
-jedan od najjednostavnijih kombinatornih principa
-naziva se jos princip pretinaca, princip kutija ili princip golubinjaka
() 21. listopada 2011. 2 / 16
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
4/36
DIRICHLETOV PRINCIP
-jedan od najjednostavnijih kombinatornih principa
-naziva se jos princip pretinaca, princip kutija ili princip golubinjaka
Dirichletov princip - slaba forma
Akon+ 1 predmet proizvoljno rasporedimo u n kutija (pretinaca), tada barem jednakutija sadrzi barem 2 predmeta.
() 21. listopada 2011. 2 / 16
http://find/http://goback/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
5/36
DIRICHLETOV PRINCIP
-jedan od najjednostavnijih kombinatornih principa
-naziva se jos princip pretinaca, princip kutija ili princip golubinjaka
Dirichletov princip - slaba forma
Akon+ 1 predmet proizvoljno rasporedimo u n kutija (pretinaca), tada barem jednakutija sadrzi barem 2 predmeta.
-dokaz gotovo nepotreban, ide kontradikcijom:
pretpostavimo da svaka kutija sadrzi najvise jedan predmet. Tada bi bilo najvise npredmeta.
() 21. listopada 2011. 2 / 16
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
6/36
DIRICHLETOV PRINCIP
-jedan od najjednostavnijih kombinatornih principa
-naziva se jos princip pretinaca, princip kutija ili princip golubinjaka
Dirichletov princip - slaba forma
Akon+ 1 predmet proizvoljno rasporedimo u n kutija (pretinaca), tada barem jednakutija sadrzi barem 2 predmeta.
-dokaz gotovo nepotreban, ide kontradikcijom:
pretpostavimo da svaka kutija sadrzi najvise jedan predmet. Tada bi bilo najvise npredmeta.
-drugi nacin iskaza slabe forme Dirichletovog principa:
Dirichletov princip-slaba forma
Neka je S neprazan skup kardinalnosti n+ 1. Pretpostavimo da smo rastavili S u kdisjunktnih podskupova A1, . . . , Ak, kn. Tada postoji skup Ai za koji je |Ai| 2.
() 21. listopada 2011. 2 / 16
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
7/36
DIRICHLETOV PRINCIP
-jedan od najjednostavnijih kombinatornih principa
-naziva se jos princip pretinaca, princip kutija ili princip golubinjaka
Dirichletov princip - slaba forma
Akon+ 1 predmet proizvoljno rasporedimo u n kutija (pretinaca), tada barem jednakutija sadrzi barem 2 predmeta.
-dokaz gotovo nepotreban, ide kontradikcijom:
pretpostavimo da svaka kutija sadrzi najvise jedan predmet. Tada bi bilo najvise npredmeta.
-drugi nacin iskaza slabe forme Dirichletovog principa:
Dirichletov princip-slaba forma
Neka je S neprazan skup kardinalnosti n+ 1. Pretpostavimo da smo rastavili S u kdisjunktnih podskupova A1, . . . , Ak, kn. Tada postoji skup Ai za koji je |Ai| 2.
() 21. listopada 2011. 2 / 16
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
8/36
DIRICHLETOV PRINCIP
Teorem 1
Neka su S i T konacni skupovi takvi da |S| >|T|, a f :S Tneko preslikavanje.Tada f nije injekcija, tj. postoje x, x S, x=x tako da je f(x) =f(x).
() 21. listopada 2011. 3 / 16
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
9/36
DIRICHLETOV PRINCIP
Teorem 1
Neka su S i T konacni skupovi takvi da |S| >|T|, a f :S Tneko preslikavanje.Tada f nije injekcija, tj. postoje x, x S, x=x tako da je f(x) =f(x).
Teorem 2
Neka su S i T konacni skupovi takvi da |S|= |T|=n, a f :STneko preslikavanje.Tada je f injekcija ako i samo ako je f surjekcija.
() 21. listopada 2011. 3 / 16
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
10/36
DIRICHLETOV PRINCIP
Teorem 1
Neka su S i T konacni skupovi takvi da |S| >|T|, a f :S Tneko preslikavanje.Tada f nije injekcija, tj. postoje x, x S, x=x tako da je f(x) =f(x).
Teorem 2
Neka su S i T konacni skupovi takvi da |S|= |T|=n, a f :STneko preslikavanje.Tada je f injekcija ako i samo ako je f surjekcija.
() 21. listopada 2011. 3 / 16
http://find/http://goback/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
11/36
DIRICHLETOV PRINCIP
Primjer 1
Medu 13 ljudi uvijek postoje dvoje rodenih u istom mjesecu.
() 21. listopada 2011. 4 / 16
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
12/36
DIRICHLETOV PRINCIP
Primjer 1
Medu 13 ljudi uvijek postoje dvoje rodenih u istom mjesecu.
Dokaz:
Direktnom primjenom Teorema 1. S=skup ljudi |S|= 13, T=skup mjeseci |T|= 12.
f :S T svakom od 13 ljudi pridruzuje mjesec rodenja. Ocito f nije injekcija papostoje najmanje 2 ljudi rodenih u istom mjesecu.
() 21. listopada 2011. 4 / 16
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
13/36
DIRICHLETOV PRINCIP
Primjer 2
Pet razlicitih pari rukavica nalaze se u jednom pretincu. Izvlacimo nasumce po jednurukavicu i ne vracamo ih nazad. Koliko je najmanje izvlacenja potrebno da bismo bilisigurni da imamo obje rukavice istog para?
() 21. listopada 2011. 5 / 16
http://find/http://goback/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
14/36
DIRICHLETOV PRINCIP
Primjer 2
Pet razlicitih pari rukavica nalaze se u jednom pretincu. Izvlacimo nasumce po jednurukavicu i ne vracamo ih nazad. Koliko je najmanje izvlacenja potrebno da bismo bilisigurni da imamo obje rukavice istog para?
Rjesenje:
S=skup rukavica koje smo izvukli, T=skup parova rukavica, f :ST pridruzujesvakoj rukavici njen par. Da bismo primijenili Teorem 1, mora vrijediti |S| >|T|= 5.
Odgovor je |S|= 6.
() 21. listopada 2011. 5 / 16
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
15/36
DIRICHLETOV PRINCIP
Poopcenje Dirichletovog principa: ako je n(r 1) + 1 predmeta razmjesteno u n kutija,tada ce barem u jednoj kutiji biti barenr predmeta.
() 21. listopada 2011. 6 / 16
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
16/36
DIRICHLETOV PRINCIP
Poopcenje Dirichletovog principa: ako je n(r 1) + 1 predmeta razmjesteno u n kutija,tada ce barem u jednoj kutiji biti barenr predmeta.
Dirichletov princip - jaka formaAko je m predmeta razmjesteno u n kutija, onda barem jedna kutija sadrzi baremm 1
n
+ 1 predmet.
() 21. listopada 2011. 6 / 16
DIRICHLETOV PRINCIP
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
17/36
DIRICHLETOV PRINCIP
Poopcenje Dirichletovog principa: ako je n(r 1) + 1 predmeta razmjesteno u n kutija,tada ce barem u jednoj kutiji biti barenr predmeta.
Dirichletov princip - jaka formaAko je m predmeta razmjesteno u n kutija, onda barem jedna kutija sadrzi baremm 1
n
+ 1 predmet.
-komentar
x - pod od xx- strop od x
1.5= 1
1.5= 22= 2= 2
() 21. listopada 2011. 6 / 16
UVOD
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
18/36
UVOD
Dokaz jake forme Dirichletovog principa:
Najveci visekratnik od n
-
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
19/36
UVOD
Dokaz jake forme Dirichletovog principa:
Najveci visekratnik od n
-
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
20/36
UVOD
Dokaz jake forme Dirichletovog principa:
Najveci visekratnik od n
-
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
21/36
DIRICHLETOV PRINCIP
Dirichletov princip - opca formaNeka je n N i r1, r2, . . . , rn N. Ako je r1+ r2+ . . . + rn n + 1 predmeta razmjestenou n kutija K1,K2, . . . , Kn, onda barem jedna kutija Ki sadrzi najmanje ri predmeta, tj. iliK1 sadrzi najmanje r1 predmeta ili K2 sadrzi najmanje r2 predmeta...ili Kn sadrzinajmanje rn predmeta.
() 21. listopada 2011. 8 / 16
DIRICHLETOV PRINCIP
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
22/36
DIRICHLETOV PRINCIP
Dirichletov princip - opca formaNeka je n N i r1, r2, . . . , rn N. Ako je r1+ r2+ . . . + rn n + 1 predmeta razmjestenou n kutija K1,K2, . . . , Kn, onda barem jedna kutija Ki sadrzi najmanje ri predmeta, tj. iliK1 sadrzi najmanje r1 predmeta ili K2 sadrzi najmanje r2 predmeta...ili Kn sadrzinajmanje rn predmeta.
Dokaz: kontradikcijom
-kada bi svaka kutija Ki sadrzavala manje od ripredmeta, tada bi ukupan broj predmetabio najvise (r1 1) + (r2 1) + . . .+ (rn 1) =r1+ . . .+rn n sto ne moze biti.
() 21. listopada 2011. 8 / 16
DIRICHLETOV PRINCIP
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
23/36
DIRICHLETOV PRINCIP
Teorem 4
Neka vrijedi r, n, a1, . . . , an N. Ako je aritmeticka sredina a1+ . . . an
n >r 1, onda je
barem jedan od brojeva a1, . . . , an r.
() 21. listopada 2011. 9 / 16
DIRICHLETOV PRINCIP
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
24/36
DIRICHLETOV PRINCIP
Teorem 4
Neka vrijedi r, n, a1, . . . , an N. Ako je aritmeticka sredina a1+ . . . an
n >r 1, onda je
barem jedan od brojeva a1, . . . , an r.
Dokaz:
Uzmimo n(r 1) + 1 predmeta i rasporedimo ih u n kutija K1, . . . , Kn.Za i= 1, . . . , n neka je aibroj predmeta u kutiji Ki. Tada je prosjek
a1+ . . . an
n
= n(r 1) + 1
n
=r 1 +1
n
.
Kako je prosjek veci od r 1, barem jedan clan mora biti veci od r 1, a kako jeaiN, slijedi air.
() 21. listopada 2011. 9 / 16
RAMSEYEV TEOREM
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
25/36
RAMSEYEV TEOREM
1930. engleski matematicar F.P. Ramsey dokazao je teorem takav da je Dirichletovprincip samo jedan njegov specijalan slucaj.
Tipican problem is Ramseyeve teorije
Zadan je k N. Koliko brojna skupina ljudi je potrebna da bi se sigurno moglo reci da utoj skupini postoji ili k-torka ljudi koji se svi medusobno poznaju ili k-torka ljudi od kojihse nikoja dva covjeka medusobno ne poznaju?
() 21. listopada 2011. 10 / 16
RAMSEYEV TEOREM
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
26/36
RAMSEYEV TEOREM
1930. engleski matematicar F.P. Ramsey dokazao je teorem takav da je Dirichletovprincip samo jedan njegov specijalan slucaj.
Tipican problem is Ramseyeve teorije
Zadan je k N. Koliko brojna skupina ljudi je potrebna da bi se sigurno moglo reci da utoj skupini postoji ili k-torka ljudi koji se svi medusobno poznaju ili k-torka ljudi od kojihse nikoja dva covjeka medusobno ne poznaju?
Ramseyev teorem tvrdi da postoji borj rktako da svaka skupina od barem rk ljudi imagornje svojstvo.
Teorem ne daje rkeksplicitno. Danas se i ne zna rk, osim za neke specijalne k.
() 21. listopada 2011. 10 / 16
RAMSEYEV TEOREM
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
27/36
RAMSEYEV TEOREM
Teorem
U skupini od 6 ljudi postoje ili tri medusobna poznanika ili postoji trojka ljudi od kojih se
nikoja dvojica ne poznaju.
() 21. listopada 2011. 11 / 16
RAMSEYEV TEOREM
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
28/36
RAMSEYEV TEOREM
Teorem
U skupini od 6 ljudi postoje ili tri medusobna poznanika ili postoji trojka ljudi od kojih se
nikoja dvojica ne poznaju.
Dokaz:
- oznacimo ljude brojevima od 1-6.- obzirom na covjeka oznacenog sa 1, ostala podijelimo u dvije skupine: P=poznanici od1, N=nepoznanici od 1.
P N={2, 3, 4, 5, 6}.
Tih 5 osoba rasporedeno je u 2 skupine pa po Dirichletovom principu (jaka forma)
barem jedna skupina sadrzi 5 1
2+ 1 = 3 ljudi.
AkoPsadrzi 3 covjeka, onda su oni medusobni neznanci ili medu njima postoji parpoznanika.Ako postoji par poznanika, njih dvoje zajedno sa osobom 1 daju trojku poznanika.AkoN sadrzi troje ljudi, onda su oni ili poznanici ili medu njima postoji par neznanaca.No, u tom slucaju njih dvoje sa osobom 1 daju 3 neznanca.
() 21. listopada 2011. 11 / 16
RAMSEYEV TEOREM
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
29/36
RAMSEYEV TEOREM
Graficki iskaz prethodnog teorema
Sest tocaka u ravnini medusobno su spojene duzinama. Svaka duzina je obojena jednom
od dviju boja: crvenom ili plavom.Tada medu svim trokutima odredenim sa tim spojnicama postoji jednobojni trokut.
() 21. listopada 2011. 12 / 16
RAMSEYEV TEOREM
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
30/36
RAMSEYEV TEOREM
Graficki iskaz prethodnog teorema
Sest tocaka u ravnini medusobno su spojene duzinama. Svaka duzina je obojena jednom
od dviju boja: crvenom ili plavom.Tada medu svim trokutima odredenim sa tim spojnicama postoji jednobojni trokut.
Ovo je najbolji moguci rezultat jer se na 5 vrhova ne mora uvijek moci dobiti jednobojnitrokut.
() 21. listopada 2011. 12 / 16
RAMSEYEV TEOREM
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
31/36
S O
Pitanje: Koliko vrhova grafa trebamo da nakon proizvoljnog spajanja svih vrhova sasvim ostalima mozemo biti sigurni da imamo cisti cetverokut?
Lema 1U skupini od desetero ljudi postoji ili trojka medusobnih neznanaca ili cetvorkamedusobnih poznanika.
() 21. listopada 2011. 13 / 16
RAMSEYEV TEOREM
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
32/36
Pitanje: Koliko vrhova grafa trebamo da nakon proizvoljnog spajanja svih vrhova sasvim ostalima mozemo biti sigurni da imamo cisti cetverokut?
Lema 1U skupini od desetero ljudi postoji ili trojka medusobnih neznanaca ili cetvorkamedusobnih poznanika.
Dokaz:
Opet numeriramo ljude s 1, 2, . . . , 10. S obzirom na osobu 1, ostalih 9 mozemorazvrstati u 2 skupa:
P=poznanici osobe 1, N=neznanci osobe 1Ako je |N| 4, onda u Npostoje ili 4 medusobna poznanika ili postoji par neznanaca.Ako postoji par neznanaca u N, onda dodajuci osobu 1 dobivamo trojku neznanaca.
Ako i |N| 3, onda je |P| 6. Prema prethodnom teoremu postoji cista trojka.Ako su u toj trojci sami neznanci, gotovi smo! Ako se radi o 3 poznanika, dodamo
osobu 1 i imamo 4 poznanika.() 21. listopada 2011. 13 / 16
RAMSEYEV TEOREM
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
33/36
Ako napravimo zamjenu: POZNANIK NEZNANAC u Lemi 1, dobivamo:
Lema 2
U skupini od desetero ljudi postoji ili trojka medusobnih poznanika ili cetvorkamedusobnih neznanaca.
() 21. listopada 2011. 14 / 16
RAMSEYEV TEOREM
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
34/36
Teorem
U skupini od 20 ljudi uvijek postoji cista cetvorka, tj. ili cetvorka medusobnih poznanikaili cetvorka medusobnih neznanaca.
() 21. listopada 2011. 15 / 16
RAMSEYEV TEOREM
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
35/36
Teorem
U skupini od 20 ljudi uvijek postoji cista cetvorka, tj. ili cetvorka medusobnih poznanikaili cetvorka medusobnih neznanaca.
Dokaz:
Oznacimo ljude s 1, 2, . . . , 20. S obzirom na osobu 1, ostalih 19 razvrstamo u 2 skupa:P=poznanici osobe 1, N=neznanci osobe 1
Jedan od njih sadrzi barem
m 1
n
+ 1 = 10 elemenata.
Ako je |P| 10, onda prema Lemi 2 u skupu Ppostoji ili trojka znanaca ili cetvorkaneznanaca.Ako sadrzi cetvorku neznanaca, gotovi smo. Ako sadrzi trojku znanaca, dodamo imosobu 1 i dobijemo 4 znanca.
Slicno postupamo ako je |N| 10 koristeci se Lemom 1.
() 21. listopada 2011. 15 / 16
RAMSEYEV TEOREM
http://find/ -
8/14/2019 02. Dirichletov Princip I Ramseyev Teorem
36/36
Neka su p, q N, p, q2.
N(p, q; 2) - najmanji broj ljudi takav da medu njima postoji ili pmedusobnih poznanikaili qmedusobnih neznanaca.
Ramseyev teorem
Za svake r, m N i sve prirodne brojeve r1, . . . , rm rpostoji najmanji prirodni brojN
= (r
1, . . . , rm
;r
) tako velik da ako imamo skup odn
elemenata,n
N
, i ako u tomskupu razvrstamo sve r-podskupove u m klasa K1, . . . , Km, tada postoji ili r1 elemenataciji su svi r-podskupovi u klasi K1 ili r2 elemenata ciji su svi r-podskupovi u klasi K2 . . .ili rm elemenata ciji su svi r-podskupovi u klasi Km.Slucaj r= 1 je Dirichletov pricip.
() 21. listopada 2011. 16 / 16
http://find/