Kombinatorna geometrija

Kombinatorna geometrija 16.09.2006. u 09:40 · pre 245 meseci #1

Neka je $k$ prirodan broj takav da je $k \geq 2$ . Koliko najvise tacaka u ravni moze da obrazuje ukupno $k$ pravih?

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

Re: Kombinatorna geometrija 16.09.2006. u 09:56 · pre 245 meseci #2

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š ${k\choose 2}=k(k-1)/2$ tačaka.)

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

Re: Kombinatorna geometrija 16.09.2006. u 10:53 · pre 245 meseci #3

Jel mozes da navedes primer (sliku) kada dostizes taj broj tacaka, za neki slucaj npr. za $k=5$ , jer mislim da si zaboravio neke prave?

Re: Kombinatorna geometrija 16.09.2006. u 12:51 · pre 245 meseci #4

Kako god da imaš već nacrtanih $k$ 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 $k=5$ imaš ovde, crtao sam je za drugi zadatak ali može da posluži i za ovaj — i ono plavo brojiš kao jednu pravu.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: Kombinatorna geometrija 16.09.2006. u 14:05 · pre 245 meseci #5

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).

Image0001.JPG80.46k

Re: Kombinatorna geometrija 16.09.2006. u 14:13 · pre 245 meseci #6

Mislim da sam tek sad shvatio šta hoćeš da kažeš.

1) Dato je $k$ pravih. Koliko najviše tačaka one mogu da obrazuju?
2) Dato je $k$ 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?

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: Kombinatorna geometrija 16.09.2006. u 14:24 · pre 245 meseci #7

Citat:

Bojan Basic: Mislim da sam tek sad shvatio šta hoćeš da kažeš.

1) Dato je $k$ pravih. Koliko najviše tačaka one mogu da obrazuju?
2) Dato je $k$ 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 $\box{2}$ (i samo njih~ukupno, kao sto sam ja i napisao u prvom postu).

Re: Kombinatorna geometrija 16.09.2006. u 15:23 · pre 245 meseci #8

Da probam ja.

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

Dakle, odgovor na pitanje je: $k$ tačaka.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: Kombinatorna geometrija 16.09.2006. u 15:27 · pre 245 meseci #9

Citat:

Bojan Basic: Da probam ja.

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

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

Re: Kombinatorna geometrija 16.09.2006. u 15:48 · pre 245 meseci #10

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:)))

Re: Kombinatorna geometrija 16.09.2006. u 15:54 · pre 245 meseci #11

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.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: Kombinatorna geometrija 16.09.2006. u 16:35 · pre 245 meseci #12

Ok, ide ovako:

Mozemo se ograniciti na konacne skupove tacaka. :)

Prvo neka je $A$ , neki skup razlicitih tacaka ( $|A|\geq 2$ ) i $(A)_p$ skup svih pravih koje su odredjenje elementima skupa $A$ (jel ovako ok? :)). Skup $A$ ima svojstvo $\mathcal{P}$ , ako nisu sve tacke iz tog skupa kolinearne.

Dokazac1emo obicnom indukcijom po $|A|$ da je $|(A)_p|\geq |A|$ , za svaki skup $A$ koji poseduje svojstvo $\mathcal{P}$ (izostavicemo slucajeve $|A|=2,3$ , jer su trivijalni).

baza indukcije: Za $|A|=4$ . Prostom analizom slucajeva vidimo da vazi data nejednakost. :)

ind. pretpostavka: Neka za svaki skup tacaka $A$ koji ima $n\geq 4$ elemenata i poseduje svojstvo $\mathcal{P}$ vazhi data nejednakost.

ind. korak: Dokazimo da sada za svaki skup tacaka $B$ koji ima $n+1$ element i poseduje svojstvo $\mathcal{P}$ vazi data nejednakost.

U tom slucaju mozemo iz skupa $B$ mozemo izdvojiti podskup koji ima $n$ elemenata i poseduje svojstvo $\mathcal{P}$ (u suprotnom bi svakih $n$ tacaka iz toga skupa lezale na jednoj pravoj, pa bi i sve tacke skupa $B$ lezale na jednoj pravoj zbog $n\geq 4$ , sto bi bila kontradikcija). Neka je ostala tacka $d$ posle izdvajanja skupa od $n$ tacaka sa svojstvom $\mathcal{P}$ iz skupa $B$ . Po induktivnoj pretpostavci je $|(B\setminus \{d\})_p|\geq |B\setminus \{d\}|$ . Sada je dovoljno dokazati da tacka $d$ sa nekom od preostalih tacaka obrazuje pravu koja nije element $(B\setminus \{d\})_p$ . Pretpostavimo suportno tj. da svaki element skupa $(B\setminus \{d\})_p$ sadrzhi tacku $d$ . Kako je $n\geq 4$ to je $|B\setminus \{d\}|\geq 3$ , pa postoje tri nekolinearne tacke iz skupa $|B\setminus \{d\}|$ . Neka su to $m,n,p$ . Po pretpostavci vazhi da prave $mn,mp,np$ sadrze tacku $d$ , pa se one seku u jednoj tacki. Ovo je kontradikcija jer te prave sadrze stranice trougla $mnp$ (svojstvo $\mathcal{P}$ ).

Znaci bar jedan od elemenata skupa $|(B\setminus \{d\})_p|$ ne sadrzi $d$ , pa vazhi $|(B)_p|\geq |B\setminus \{d\}|+1=|B|$ .

Ovim je dato tvrdjenje dokazano.

Forum kao aplikacija na telefonu

Srodne teme