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

Kombinatorni zadataka sa pravama

[es] :: Matematika :: Kombinatorni zadataka sa pravama

[ Pregleda: 5172 | Odgovora: 16 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

gpreda
Goran Predovic
Kragujevac

Član broj: 19087
Poruke: 74
195.252.81.*

Sajt: alas.matf.bg.ac.yu/~mr990..


Profil

icon Kombinatorni zadataka sa pravama13.07.2004. u 14:35 - pre 240 meseci
U ravni su zadate n > 2 prave u opstem polozaju (nijedne dve nisu paralelne i nijedne tri se ne seku).

Dokazati da one formiraju bar n - 2 trouglova.
 
Odgovor na temu

Hypatia
bgd

Član broj: 25844
Poruke: 17
*.vdial.verat.net



Profil

icon Re: Kombinatorni zadataka sa pravama14.07.2004. u 13:44 - pre 240 meseci
n>2 pravih u opstem polozaju deli ravan na oblasti od kojih su neke ogranicene, a neke neogranicene. Neka A bude ukupan broj oblasti, a B broj ogranicenih oblasti (trouglovi+cetvorouglovi). Ne bih da ti kvarim uzivanje u otkrivanju...pocni od n-1 prave i vidi sta se dobija crtanjem n-te, tj. kako se broj oblasti povecava. U svakom slucaju ukupno je A=n^2+n+2/2 oblasti , od toga B=n^2-3n+2 ogranicenih
od ogranicenih oduzmemo n-2 nad 2 cetvorougla i dobijamo bar n-2 trougla.
 
Odgovor na temu

gpreda
Goran Predovic
Kragujevac

Član broj: 19087
Poruke: 74
195.252.81.*

Sajt: alas.matf.bg.ac.yu/~mr990..


Profil

icon Re: Kombinatorni zadataka sa pravama15.07.2004. u 14:12 - pre 240 meseci
Ogranicene oblasti ne moraju biti samo trouglovi i cetvrorouglovi, formule za oblasti su pogresno napisane (treba A=(n^2+n+2) / 2 i B=(n^2-3n+2) / 2) i na kraju, najkriticniji deo - zasto oduzimas n-2 nad 2 cetvorougla?
 
Odgovor na temu

PeraT

Član broj: 3403
Poruke: 43
*.ptt.yu



Profil

icon Re: Kombinatorni zadataka sa pravama19.07.2004. u 01:50 - pre 240 meseci
Ja bi to indukcijom po broju pravih, pocevsi od n=3?
'El treba da se tera dokaz?

Zdr.
 
Odgovor na temu

gpreda
Goran Predovic
Kragujevac

Član broj: 19087
Poruke: 74
195.252.81.*

Sajt: alas.matf.bg.ac.yu/~mr990..


Profil

icon Re: Kombinatorni zadataka sa pravama19.07.2004. u 13:16 - pre 240 meseci
Zadatak je verovatno dosta tezak (ne znam resenje) iako po formulaciji deluje jednostavan. Ponadao sam se da ce neko da ga resi.

Nalazi se u cuvenoj knjizi "Introduction to Alghoritms" Udija Manbera.
 
Odgovor na temu

PeraT

Član broj: 3403
Poruke: 43
*.ptt.yu



Profil

icon Re: Kombinatorni zadataka sa pravama19.07.2004. u 19:58 - pre 240 meseci
Citat:
gpreda: (ne znam resenje)


De, de.
n=3
Neka su date prave a0,a1,a2. Njima je odredjen
trougao sa temenima a0xa1, a0xa2, a1xa2.
n->n+1
Prave a1,...,an odredjuju bar n-2 trougla po
induktivnoj pretpostavci. Dodavanjem nove prave
an+1 odredjen je barem jos jedan nov trougao npr.
onaj sa temenima a1xa2,a2xan+1,an+1xa1. Ovaj trougao
nije odredjen pravama a1,...,an jer su prave a1, ...
, an+1 u "opstem polozaju".

Zdr.
 
Odgovor na temu

Hypatia
bgd

Član broj: 25844
Poruke: 17
*.vdial.verat.net



Profil

icon Re: Kombinatorni zadataka sa pravama20.07.2004. u 13:11 - pre 240 meseci
Ili da ne bi isao n=3,n=4.....pretpostavi da imas n-1 pravu u opstem polozaju, nacrtaj n-tu dobija se n-1 tacka preseka sa prethodno nacrtanim pravama. Te tacke dele poslednju nacrtanu pravu na n-2 duzi i 2 poluprave. Svaki taj deo deli jednu od ranije dobijenih oblasti na dva dela tj. ukupan broj oblasti se posle crtanja n-te prave povecava za n, dok se broj ogranicenih oblasti povecava za n-2. Znaci imamo (n nad 2)-(n nad 1)+(n nad 0) ogranicenih oblasti, do ove formule pretpostavljam da znas doci, a to je dalje jednako primenom jednog od svojstva za binomne koeficijente (n-1 nad 2)+(n-1 nad 1)-(n-1 nad 1)-(n-1 nad 0)+1=
=(n-1 nad 2)=primeni jos jednom svojstvo=
=(n-2 nad 2)+ (n-2 nad 1)
a to su cetvorouglovi + trouglovi = broj ogranicenih oblasti. Mislim da sam sada sve napisala kako treba, pozdrav.
 
Odgovor na temu

gpreda
Goran Predovic
Kragujevac

Član broj: 19087
Poruke: 74
195.252.81.*

Sajt: alas.matf.bg.ac.yu/~mr990..


Profil

icon Re: Kombinatorni zadataka sa pravama21.07.2004. u 08:09 - pre 240 meseci
Citat:
PeraT: ... Dodavanjem nove prave
an+1 odredjen je barem jos jedan nov trougao npr.
onaj sa temenima a1xa2,a2xan+1,an+1xa1. Ovaj trougao
nije odredjen pravama a1,...,an jer su prave a1, ...
, an+1 u "opstem polozaju".


Izgleda da nisam bio jasan u postavci zadatka, misli se na trouglove koji nisu preseceni nijednom drugom pravom iz skupa.
 
Odgovor na temu

gpreda
Goran Predovic
Kragujevac

Član broj: 19087
Poruke: 74
195.252.81.*

Sajt: alas.matf.bg.ac.yu/~mr990..


Profil

icon Re: Kombinatorni zadataka sa pravama21.07.2004. u 08:14 - pre 240 meseci
Citat:
Hypatia
a to su cetvorouglovi + trouglovi = broj ogranicenih oblasti. Mislim da sam sada sve napisala kako treba, pozdrav.


Formule za broj ogranicenih i otvorenih oblasti se lako dobijaju, one uopste nisu sporne. Ali ne mora zatvorena oblast da bude iskljucivo trougao ili cetvorougao.
Ni ostalo zakljucivanje nije tacno. Na jednom mestu kazes oduzmes toliko cetvorouglova i dobijas 'bar' n-2 trougla. Ako bi oduzela od one forume n-2 nad 2 cetvorougla, dobila bi tacno n-2 trougla, a moguci su slucajevi i sa vise trouglova.
 
Odgovor na temu

neor
Nenad Orlovic

Član broj: 26828
Poruke: 74
*.panline.net



Profil

icon Re: Kombinatorni zadataka sa pravama23.07.2004. u 09:42 - pre 240 meseci
Za n=3 postoji tacno jedan trougao.

Neka vazi za K pravih da postoji bar K-2 trougla.

Neka je p nova prava.
(1) Ako p sece neki od postojecih trouglova onda ce opet nastati jedan trougao i jedan cetvorougao. Znaci broj trouglova se nece smanjiti.
Treba jos pokazati da je dodavanjem prave p nastao bar jedan novi trougao.

Neka je A presecna tacka najbliza pravoj p.
Ako transliramo pravu p u pravcu tacke A broj trouglova se nece promeniti sve dok p ne prodje kroz tacku A.
Ako je A bilo teme jednog trougla on ce nestati kad A bude na p. Medjutim cim prodje tacku A pojavice se novi mali trougao sa druge strane kome je A jedno teme. Znaci broj trouglova se nije promenio.
Nastavimo da pomeramo p dok sve tacke ne budu u istoj poluravni u odnosu na p.
Onog trenutka kada p prodje najdalju tacku B pojavice se jedan mali trougao cije je teme B.
To je potpuno novi trougao jer pre dodavanja prave p to je bio deo otvorene oblasti.
Sada vracamo pravu p nazad na pocetnu poziciju i isto zakljucujemo da se broj trouglova translacijom ne moze promeniti.
Znaci imamo bar jedan novi trougao a svi postojeci su sacuvani (1).


 
Odgovor na temu

gpreda
Goran Predovic
Kragujevac

Član broj: 19087
Poruke: 74
195.252.81.*

Sajt: alas.matf.bg.ac.yu/~mr990..


Profil

icon Re: Kombinatorni zadataka sa pravama23.07.2004. u 14:56 - pre 240 meseci
Citat:
neor
Onog trenutka kada p prodje najdalju tacku B pojavice se jedan mali trougao cije je teme B.
To je potpuno novi trougao jer pre dodavanja prave p to je bio deo otvorene oblasti.
Sada vracamo pravu p nazad na pocetnu poziciju i isto zakljucujemo da se broj trouglova translacijom ne moze promeniti.
Znaci imamo bar jedan novi trougao a svi postojeci su sacuvani (1).


Da, a ako nastavimo postupak dobicemo jos beskonacno mnogo trouglova :) To ti je kao dokaz da u autobus moze da se smesti beskonacno ljudi - jedan moze da stane sigurno, a ako pretpostavimo da je stalo n, uvek moze da se ugura jos jedan :)


 
Odgovor na temu

neor
Nenad Orlovic

Član broj: 26828
Poruke: 74
*.panline.net



Profil

icon Re: Kombinatorni zadataka sa pravama23.07.2004. u 15:20 - pre 240 meseci
Citat:
gpreda: Da, a ako nastavimo postupak dobicemo jos beskonacno mnogo trouglova :)


Ne moze to da se dokaze ovim postupkom. On samo govori o broju trouglova a ne i o njihovom polozaju tako da nikad ne bi mogao da pokazes da to nije jedan te isti trougao.
Mozda mi izbor reci nije bas najbolji u dokazu ali razmisli jos malo i videces da je u redu.
 
Odgovor na temu

zzzz
milan kecman
bluka

Član broj: 11810
Poruke: 2154
*.dialup.blic.net



+196 Profil

icon Re: Kombinatorni zadataka sa pravama23.07.2004. u 18:48 - pre 240 meseci
Citat:
neor: Za n=3 postoji tacno jedan trougao.

Neka vazi za K pravih da postoji bar K-2 trougla.

Neka je p nova prava.
(1) Ako p sece neki od postojecih trouglova onda ce opet nastati jedan trougao i jedan cetvorougao. Znaci broj trouglova se nece smanjiti.
Treba jos pokazati da je dodavanjem prave p nastao bar jedan novi trougao.

Neka je A presecna tacka najbliza pravoj p.
Ako transliramo pravu p u pravcu tacke A broj trouglova se nece promeniti sve dok p ne prodje kroz tacku A.
Ako je A bilo teme jednog trougla on ce nestati kad A bude na p. Medjutim cim prodje tacku A pojavice se novi mali trougao sa druge strane kome je A jedno teme. Znaci broj trouglova se nije promenio.
Nastavimo da pomeramo p dok sve tacke ne budu u istoj poluravni u odnosu na p.
Onog trenutka kada p prodje najdalju tacku B pojavice se jedan mali trougao cije je teme B.
To je potpuno novi trougao jer pre dodavanja prave p to je bio deo otvorene oblasti.
Sada vracamo pravu p nazad na pocetnu poziciju i isto zakljucujemo da se broj trouglova translacijom ne moze promeniti.
Znaci imamo bar jedan novi trougao a svi postojeci su sacuvani (1).

Ma u redu je dokaz.Čova se samo šali.
________________________________

Najbolja kritika formule za Sagnac effect:
https://www.omicsonline.org/op...090-0902-1000189.php?aid=78500

OK evo prave formule:P=2wft^2 [period]
 
Odgovor na temu

gpreda
Goran Predovic
Kragujevac

Član broj: 19087
Poruke: 74
195.252.81.*

Sajt: alas.matf.bg.ac.yu/~mr990..


Profil

icon Re: Kombinatorni zadataka sa pravama26.07.2004. u 10:10 - pre 240 meseci
Citat:
neor: Ne moze to da se dokaze ovim postupkom. On samo govori o broju trouglova a ne i o njihovom polozaju tako da nikad ne bi mogao da pokazes da to nije jedan te isti trougao.
Mozda mi izbor reci nije bas najbolji u dokazu ali razmisli jos malo i videces da je u redu.


Razmisli sta se desava kada tvojom translacijom prelazis preko neke tacke. Izgubices sa donje strane jedan trougao (kao sto si zakljucio), a sa gornje strane dobijas trougao. Ali sta je pre toga bilo sa gornje strane? Ako je bio trougao, ti si ga unistio - tako da si izgubio dva trougla a dobio jedan novi. Zakljucak je da pri 'translaciji' preko neke tacke broj trouglova moze i da se smanji (a ti tvrdis da se ne menja).

Da ne govorimo o daljem toku dokaza.
 
Odgovor na temu

neor
Nenad Orlovic

Član broj: 26828
Poruke: 74
*.eutelsat.net



Profil

icon Re: Kombinatorni zadataka sa pravama26.07.2004. u 15:13 - pre 240 meseci
Citat:
gpreda: Razmisli sta se desava kada tvojom translacijom prelazis preko neke tacke. Izgubices sa donje strane jedan trougao (kao sto si zakljucio), a sa gornje strane dobijas trougao. Ali sta je pre toga bilo sa gornje strane? Ako je bio trougao, ti si ga unistio - tako da si izgubio dva trougla a dobio jedan novi. Zakljucak je da pri 'translaciji' preko neke tacke broj trouglova moze i da se smanji (a ti tvrdis da se ne menja).

Za ovo si u pravu ako je vec bio trougao sa druge strane.

Citat:
Da ne govorimo o daljem toku dokaza.

Sta sad fali ostatku ako nekako ipak moze da se dokaze da se translacijom ne menja broj trouglova.
 
Odgovor na temu

Bojan Basic
Novi Sad

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

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253


+605 Profil

icon Re: Kombinatorni zadataka sa pravama05.03.2005. u 15:31 - pre 232 meseci
Ovaj dokaz koji je neor dao nikako nije ispravan, jer osim slučaja koji je gpreda spomenuo "gubljenje" trouglova može da se dogodi i na drugi način, na primer kao na slici (obratite pažnju šta se dešava kad prava obeležena plavom bojom pređe preko tačke P).


"Zvanični" dokaz, ako se ne varam, se svodi na to da svakoj pravoj pridružimo brzinu na takav način da kad prave počnu da se "kreću" površine trouglova koje one obrazuju ostaju konstantne, ali nažalost ne znam više detalja o ovakvom rešenju (ujedno bih zamolio da ako neko zna napiše tačno kako to ide). Ono što ću sada pokušati da prezentujem je jedan drugačiji dokaz, ako neko eventualno nađe grešku u njemu neka slobodno to napiše, ja mislim da je korektan.

Posmatrajmo proizvoljnu duž iz date podele i neka su njeni krajevi tačke i . Ta duž je zajednička za dve oblasti (od kojih jedna može biti i beskonačna). Posmatrajmo jednu od te dve oblasti. Neka je u njoj . U tom slučaju "stranu" duži koja se nalazi unutar te oblasti obojimo crveno, u suprotnom plavo (analogija bi bila recimo sledeća: neka su pomenute oblasti "sobe" a duži "zidovi", tako da bojimo onu stranu zida koja se nalazi u posmatranoj sobi). Istu uradimo i za drugu oblast koja sadrži tu duž, i ceo postupak ponovimo za sve duži. Očigledno je da sada svaka duž ima jednu crvenu i jednu plavu stranu (jer ukoliko je za jednu figuru neke duži onda za drugu figuru te duži zbir uglova u tačkama i iznosi ), pa je broj duži upravo jednak broju crveno obojenih strana. Takođe se lako zapaža da su u svakom trouglu sve tri strane njegovih duži obojene crveno. Posmatrajmo neku figuru iz date podele koja ima 4 ili više ivica. Dokazaćemo da ako u toj figuri postoje neke dve crvene duži u tom slučaju one moraju biti susedne. Pretpostavimo suprotno - neka su u figuri duži i obojene crvenom bojom, za ostale nije bitno kako. Tada je i , odnosno što je očigledna kontradikcija. Iz ovoga neposredno sledi da je u svakoj figuri sa 4 ili više stranica najviše 2 duži obojeno crvenom bojom. Neka je ukupan broj duži i ukupan broj konačnih figura u datoj oblasti. Ako sa obeležimo broj trouglova u datoj podeli prebrojavanjem crvenih strana (podsetimo se da je njihov broj jednak broju duži) dobijamo:

Znajući da je i (obe stvari su poznate iz kombinatorike, prva je očigledna a druga se lako dokazuje indukcijom) uvrštavanjem ovoga u poslednju formulu imamo:
, odnosno , što je i trebalo dokazati.
Ljubičice crvena, što si plava kô zelena trava.
Prikačeni fajlovi
 
Odgovor na temu

gpreda
Goran Predovic
Kragujevac

Član broj: 19087
Poruke: 74
212.200.23.*

Sajt: alas.matf.bg.ac.yu/~mr990..


Profil

icon Re: Kombinatorni zadataka sa pravama18.03.2005. u 07:42 - pre 232 meseci
Odlicno resenje!

Cuo sam da postoji i resenje sa kretanjem pravih (zvanicno resenje), ali ovo je sigurno dosta elegantnije.
 
Odgovor na temu

[es] :: Matematika :: Kombinatorni zadataka sa pravama

[ Pregleda: 5172 | Odgovora: 16 ] > FB > Twit

Postavi temu Odgovori

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