Srodne teme
Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Kombinatorna geometrija

[es] :: Matematika :: Kombinatorna geometrija

[ Pregleda: 3589 | Odgovora: 11 ] > FB > Twit

Postavi temu Odgovori

Autor
Pretraga teme: Traži
Markiranje Štampanje RSS

qzqzqz

Član broj: 66936
Poruke: 219
*.ptt.yu.



Profil

icon Kombinatorna geometrija16.09.2006. u 08:40 - pre 226 meseci
Neka je prirodan broj takav da je . Koliko najvise tacaka u ravni moze da obrazuje ukupno pravih?

Ko ima neku ideju neka napise... Ja imam jedno malo slozenije resenje, pa cu da ga okacim ako bude potrebe?
 
Odgovor na temu

Farenhajt
Goran Kapetanović
Beograd

Član broj: 78132
Poruke: 449
62.193.129.*



+6 Profil

icon Re: Kombinatorna geometrija16.09.2006. u 08:56 - pre 226 meseci
Hm... Dve prave se seku pa određuju jednu tačku, onda dodaš treću pravu tako da seče obe a da nisu konkurentne, pa tako dobijaš dve nove tačke, pa onda dodaš četvrtu pravu na isti način i dobijaš još tri nove tačke, itd, dodaš k-tu pravu da bi dobio k-1 novu tačku, i ukupno ih imaš 1+2+...+(k-1)=k(k-1)/2. (Alternativno obrazloženje: Ako se svaka sa svakom seče, onda imaš tačaka.)

(Naravno, k pravih koje se poklapaju određuju beskonačno mnogo tačaka...)
 
Odgovor na temu

qzqzqz

Član broj: 66936
Poruke: 219
*.ptt.yu.



Profil

icon Re: Kombinatorna geometrija16.09.2006. u 09:53 - pre 226 meseci
Jel mozes da navedes primer (sliku) kada dostizes taj broj tacaka, za neki slucaj npr. za , jer mislim da si zaboravio neke prave?

[Ovu poruku je menjao qzqzqz dana 16.09.2006. u 11:07 GMT+1]
 
Odgovor na temu

Bojan Basic
Novi Sad

SuperModerator
Član broj: 6578
Poruke: 3996
*.ADSL.neobee.net.

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253


+621 Profil

icon Re: Kombinatorna geometrija16.09.2006. u 11:51 - pre 226 meseci
Kako god da imaš već nacrtanih pravih (u opštem položaju), uvek možeš da povučeš još jednu koja je sa ostalima u opštem položaju (nikoje dve nisu paralelne, nikoje tri ne seku se u istoj tački). To je suština Farenhajtovog dokaza.

Sliku za imaš ovde, crtao sam je za drugi zadatak ali može da posluži i za ovaj — i ono plavo brojiš kao jednu pravu.

[Ovu poruku je menjao Bojan Basic dana 16.09.2006. u 15:27 GMT+1]
Ljubičice crvena, što si plava kô zelena trava.
 
Odgovor na temu

qzqzqz

Član broj: 66936
Poruke: 219
*.ptt.yu.



Profil

icon Re: Kombinatorna geometrija16.09.2006. u 13:05 - pre 226 meseci
Ako sam dobro razumeo sta hoces da kazes onda na toj slici date tacke obrazuju jos neke prave (neke od takvih su nacrtane isprekidanim linijama).

Prikačeni fajlovi
Image0001.JPG Image0001.JPG - 80.46k
 
Odgovor na temu

Bojan Basic
Novi Sad

SuperModerator
Član broj: 6578
Poruke: 3996
*.ADSL.neobee.net.

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253


+621 Profil

icon Re: Kombinatorna geometrija16.09.2006. u 13:13 - pre 226 meseci
Mislim da sam tek sad shvatio šta hoćeš da kažeš.

1) Dato je pravih. Koliko najviše tačaka one mogu da obrazuju?
2) Dato je pravih. Koliko najviše tačaka može njih da obrazuje (stičem utisak da treba dodati i samo njih)?

Farenhajt (očigledno) i ja smo mislili da pokušavaš da pitaš ovo prvo. Tebe zapravo zanima drugo pitanje?
Ljubičice crvena, što si plava kô zelena trava.
 
Odgovor na temu

qzqzqz

Član broj: 66936
Poruke: 219
*.ptt.yu.



Profil

icon Re: Kombinatorna geometrija16.09.2006. u 13:24 - pre 226 meseci
Citat:
Bojan Basic: Mislim da sam tek sad shvatio šta hoćeš da kažeš.

1) Dato je pravih. Koliko najviše tačaka one mogu da obrazuju?
2) Dato je pravih. Koliko najviše tačaka može njih da obrazuje (stičem utisak da treba dodati i samo njih)?

Farenhajt (očigledno) i ja smo mislili da pokušavaš da pitaš ovo prvo. Tebe zapravo zanima drugo pitanje?


Da, hocu ovo pod (i samo njih~ukupno, kao sto sam ja i napisao u prvom postu).
 
Odgovor na temu

Bojan Basic
Novi Sad

SuperModerator
Član broj: 6578
Poruke: 3996
*.ADSL.neobee.net.

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253


+621 Profil

icon Re: Kombinatorna geometrija16.09.2006. u 14:23 - pre 226 meseci
Da probam ja.

Pitanje je očigledno ekvivalentno sledećem pitanju: kako poređati tačaka u ravni koje nisu sve kolinearne tako da obrazuju što manje pravih? Teorema Erdeša i De Brojna kaže da tačaka u ravni koje nisu sve kolinearne formiraju najviše pravih. Preostaje da nađemo jednu konfiguraciju koja obrazuje baš pravih. Dovoljno je uzeti kolinearnu tačku, a preostalu staviti negde sa strane.

Dakle, odgovor na pitanje je: tačaka.
Ljubičice crvena, što si plava kô zelena trava.
 
Odgovor na temu

qzqzqz

Član broj: 66936
Poruke: 219
*.ptt.yu.



Profil

icon Re: Kombinatorna geometrija16.09.2006. u 14:27 - pre 226 meseci
Citat:
Bojan Basic: Da probam ja.

Teorema Erdeša i De Bruijna kaže da tačaka u ravni koje nisu sve kolinearne formiraju najviše pravih.


Verovatno mislis najmanje. Slicno resenje sam i ja smislio, samo bez ove teoreme. :)
 
Odgovor na temu

useer
beograd

Član broj: 98019
Poruke: 38
*.adsl.sezampro.yu.



Profil

icon Re: Kombinatorna geometrija16.09.2006. u 14:48 - pre 226 meseci
Kad je meni rekao zadatak(idemo u isto odeljenje) i ja sam mu rekao da zadatak nije precizan...odnosno nije precizno naglaseno sta se trazi, ovo vase, 1. ili 2. tvrdjenje.Nije mi verovao ...CCC:)))
 
Odgovor na temu

Bojan Basic
Novi Sad

SuperModerator
Član broj: 6578
Poruke: 3996
*.ADSL.neobee.net.

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253


+621 Profil

icon Re: Kombinatorna geometrija16.09.2006. u 14:54 - pre 226 meseci
Citat:
qzqzqz:
Verovatno mislis najmanje.

U pravu si, lapsus.
Citat:
qzqzqz:
Slicno resenje sam i ja smislio, samo bez ove teoreme. :)

Dobro, ali ako se ne pozoveš na teoremu onda moraš da je dokažeš. Ako hoćeš možeš da napišeš dokaz.
Ljubičice crvena, što si plava kô zelena trava.
 
Odgovor na temu

qzqzqz

Član broj: 66936
Poruke: 219
*.ptt.yu.



Profil

icon Re: Kombinatorna geometrija16.09.2006. u 15:35 - pre 226 meseci
Ok, ide ovako:

Mozemo se ograniciti na konacne skupove tacaka. :)

Prvo neka je , neki skup razlicitih tacaka () i skup svih pravih koje su odredjenje elementima skupa (jel ovako ok? :)). Skup ima svojstvo , ako nisu sve tacke iz tog skupa kolinearne.


Dokazac1emo obicnom indukcijom po da je , za svaki skup koji poseduje svojstvo (izostavicemo slucajeve , jer su trivijalni).



baza indukcije: Za . Prostom analizom slucajeva vidimo da vazi data nejednakost. :)


ind. pretpostavka: Neka za svaki skup tacaka koji ima elemenata i poseduje svojstvo vazhi data nejednakost.

ind. korak: Dokazimo da sada za svaki skup tacaka koji ima element i poseduje svojstvo vazi data nejednakost.

U tom slucaju mozemo iz skupa mozemo izdvojiti podskup koji ima elemenata i poseduje svojstvo (u suprotnom bi svakih tacaka iz toga skupa lezale na jednoj pravoj, pa bi i sve tacke skupa lezale na jednoj pravoj zbog , sto bi bila kontradikcija). Neka je ostala tacka posle izdvajanja skupa od tacaka sa svojstvom iz skupa . Po induktivnoj pretpostavci je . Sada je dovoljno dokazati da tacka sa nekom od preostalih tacaka obrazuje pravu koja nije element . Pretpostavimo suportno tj. da svaki element skupa sadrzhi tacku . Kako je to je , pa postoje tri nekolinearne tacke iz skupa . Neka su to . Po pretpostavci vazhi da prave sadrze tacku , pa se one seku u jednoj tacki. Ovo je kontradikcija jer te prave sadrze stranice trougla (svojstvo ).

Znaci bar jedan od elemenata skupa ne sadrzi , pa vazhi .


Ovim je dato tvrdjenje dokazano.
 
Odgovor na temu

[es] :: Matematika :: Kombinatorna geometrija

[ Pregleda: 3589 | Odgovora: 11 ] > FB > Twit

Postavi temu Odgovori

Srodne teme
Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.