Sta je sad?Ajmo probati.Bas sam zapazio da ovdje ima dobrih matematicara;
FILMIL,KOLUNDZIJA,T0VK,DARKOSOS,JA,I JIOS NEKI....
Ma nece nam se oteti ova moja zapetljancija ja mislim?
Cim rijesimo ide jos gora budalestina!

Probao sam, ali ne ide. :)

Pronašao sam da je donja granica za broj preseka koji se traži gde je broj pravih ali manje-više to je sve (procena nije što bi se reklo tight).

Ideja mi je bila da predstavim prave i tačke kao bipartitan graf (jer se tako lakše konstruiše, problem je kad treba crtati te silne prave, pa još i preseci itd.): nodovi s leve strane predstavljaju prave a nodovi s desne strane predstavljaju preseke.

Prema ograničenju koje si dao, stepeni desnih čvorova mogu biti ili 2 ili 3 i postoji ograničenje da u grafu ne sme postojati ciklus dužine 4 (to bi značilo da postoje dva leva noda koja imaju dva ista desna susedna noda, tj. da se neke dve prave seku u dve tačke, što nije dozvoljeno). Sa ovim ograničenjima možete da krenete u konstrukciju grafa koji odgovara polaznom problemu i to odlično ( :)))) ) radi dok se ne stigne do 6 pravih... ko bude probao, videće.

Nadam se da ovo može da bude od pomoći nekome ko ume da gleda dalje.

f

Da nije resenje ?
Znaci za primer sa 9 pravih resenje je 30?

Evo moje 2 banke na 18.
Isprva nisam hteo ni da pokušavam, iz dva razloga : prvo, niti geometrija niti kombinatorika mi nisu jače strane; drugo, pošto su se ovde neki pokazali da im to leži, mislio sam, šta da se petljam.
Elem, pošto sam već prozvan...:)

Ovaj rezultat sam dobio malte ne peške, ali sam ipak uočio par 'pravila'.
Naravno, prve 3 prave stavimo da prolaze kroz jednu tačku. Četvrta nema gde nego da seče sve tri, i time dobijamo 4 presečne tačke. U sledećem koraku se već može uočiti neka sistematika.

Naime, kako ćemo postaviti sledeću pravu, zavisi od 'topologije' prethodne slike. Idući za uslovom minimalnog broja preseka, biramo tačke u kojima se seku samo po dve prave, jer je dozvoljeno da ubudžimo treću (ovakve tačke sam, za sebe, nazvao 'slobodne'). Ako imamo bar dve takve tačke i one nisu već spojene pravom, onda možemo postaviti novu pravu kroz njih, itd...

Dakle, ako smo iskoristili 1 slobodnu tačku, broj novih preseka je za dva manji od prethodnog broja pravih. Npr. n=4, imamo 3 slobodne tačke i ukupno 4 presečne, koristimo jednu slobodnu i pravimo novih 4-2=2 preseka. Posle ovog poteza, imamo 3-1+2=4 slobodne tačke i ukupno 6 preseka.

Ako već imamo n pravih i iskoristimo dve slobodne tačke, broj novih preseka je n-4 a od broja slobodnih tačaka oduzimamo 2 i dodajemo n-4 tj. dodajemo n-6 (svi preseci van slobodnih tačaka su nove slobodne tačke).

Idući ovim sistemom do 9 pravih, nisam naišao na slučaj sa 3 kolinearne slobodne tačke, što ne znači da se ne može kasnije desiti. Svakako bi pomoglo kada bi znali šta možemo da očekujemo.

Takođe, ako sam i ovo dobro uradio, nisam našao način da generalizujem algoritam. Tu bi već trebala neka jača geometrijska tvrđenja, jer moramo predvideti, na osnovu prethodnog stanja, kakva će biti topologija narednog. Ako neko zna više, nek pomogne ovde.

Srki, cini mi se da to nije resenje, posto sam za n=6 nasao da moze biti 7 tacaka (nacrtas trougao, i povuces tezisne linije), sto opet ne znaci da je to minimum. (pretpostavljam da je ono najblizi (manji?) ceo broj broju )

Mozda je resenje , gde je ovo x broj troclanih podskupova od n elemenata takvih da presek svaka dva ima najvise jedan element. Ako neko zna formulu za takvo x, neka mi kaze. Recimo, za n=6, nasao sam 4 takva podskupa ({1, 2, 3}, {1, 4, 5}, {2, 4, 6}, {3, 5, 6}), i u tom slucaju se dobije 7 tacaka. Za n=9 sam nasao 12 podskupova, pa bi resenje moglo da bude 12 (mada jos nisam uspeo da ga "konstruisem").
Naravno, moguce je da sam se grdno presao, al' 'ajd' kad vec navaljujes...

Pod pretpostavkom da nema kolinearnih slobodnih tačaka, i za broj pravih n ne manji od 5 imamo da je broj preseka manji ili jednak od . Ovo se dobije iz Darkove konstrukcije pod pretpostavkom da ne postoje tri kolinearne slobodne tačke: u svakom koraku se broj preseka ne poveća za broj prava koji je već postavljen (neka je taj broj n) već za n-4.

Ubr, Za 6 pravih 7 presečnih tačaka jeste minimum, ako vam nešto pomaže, to je jedino mesto gde gornja i donja granica daju upotrebljiv rezultat.

f

p.s. Ovo je jedna od najboljih diskusija na forumu od ko zna otkad! Keep up the good work.

Evo, ako je od pomoci, u pokusaju da konstruisem sliku sa 12 presecnih tacaka, uspeo sam da dobijem sliku sa 16 presecnih tacaka, sto se uklapa u Filipovu formulu (koja ocigledno daje i tacan rezultat za n=6).

Ovo sto je Kolundzija napravio sa 9 pravaca je dobro.Za ostale cu objasniti:

Iz komada papira isjecite istostranican trokut.Previjte ga po jednoj tezisnici
a zatim jos jednom (kao sto se pravi raketa).Ponovite to i za preostale dvije
tezisnice.Ovih 9 pregiba su pravci.

Ono x kod Kolundzije je

Treba zapaziti iz one slike 9 pravaca da imamo 2 skupa od po 3 slobodne
tacke ali im kruta ravan neda da se skupe iako lijepo kombinacijski ulaze u onaj
broj x tj. da sa sesnaest presjeka sadjemo na 12.

Moram priznati da mi nije jasno.
Prvo, za 9 : da li je rešenje 12 ili 16.
Drugo, da li je Mihailova formula za n dobra ili ne?
I treće, nisam uspeo da nacrtam to rešenje, bez obzira na uputstvo sa avionom :)
Ako nije problem, voleo bih to da vidim. Da li si siguran da nema paralelnih pravih?

p.s. Ako ovako nastavim, ima sve pare da izgubim na ovom forumu :)

Malo drukciji opis one konstrukcije:
Na sredini papira postavi tacku i kroz nju povuci 3 pravca
koji medjusobno prave ugao 120 stepeni.Odaberi 3 tacke na onim
pravcima tako da su jednako udaljene od sredisnje i da su medjusobno
jednako udaljene.kroz svaku od tih tacaka povuci 2 pravca tako da im onaj
ranije nacrtani bude simetrala.(Odaberi ugao 20 stepeni lijevo i desno da budes siguran da nista nuje paralelno).Dobices 10 "punih" i 6 "slobodnih" tacaka.
To je za 9 pravaca 16 presjeka.

Mihailo je oznacio pravce brojevima i izracunao da ima 12 skupova
od po 3 broja,ali tako da se ni jedan par brojeva ne smije pojaviti
vise od jednom.(Ako naprimjer imamo {1;2;3 }onda se vise ne smije
pojaviti 1;2 1;3 2;3 u sastavu nekog drugog skupa.
Ona formula je za izracunavanje broja skupova samo sam ja dodao
racun za x=.Problem je sto se neda napraviti konstrukcija gdje bi broj presjeka odgovarao onom broju skupova.Sto se broj pravaca povecava broj
"slobodnih" tacaka raste.Moze li se pronaci neka zakonitost?

Hm, znači ovako :

Lepo...

"Ko radi taj i gresi,ali nisam ja bre slepac",rece komentator nase reprezentacije u vaterpolu kada Sapic pocepa mrezicu.
Ne znam da li ja gresim ili svi vi:),ali vidim bolje resenje(ili se bar meni tako cini).Ako mislite da ovo ima smisla,naci cu knjigu iz mat1,podsetiti se grafova,pa da resimo(ali samo ako i za ovo ne gresim nesto,kasno je ipak)
Za 9 pravih imam 13 tacaka...

I meni se juče učinilo da je (a samim tim da sam u stvari našao samo formulu za donju granicu), ali za n=6 sam uspeo da nadjem samo četiri takva podskupa (a po toj formuli bi ih bilo 5). (možda je , ali i to treba proveriti)
Naravno, ovim ne pokušavam da kažem da je moje rešenje tačno (naprotiv, čini mi se da nije).

Rekao bih da su tri seta od po tri prave paralelne na tvojoj slici, što nije dozvoljeno, jer svaka prava mora da seče svaku. Ako namestiš tri seta po tri malko ukoso tako da se seku (i to u po jednoj tački), imaš 16 preseka.

BTW, jedini način da se uštedi na presecima jeste da imaš bar tri prave koje prolaze kroz po tri slobodne tačke. Ako neko uspe da pokaže da to nije moguće onda je stvar rešena.

f

Evo jos malo razmisljanja na istu temu.

Pretpostavimo da u nasoj konstrukciji postoji prva prava koja se postavlja preko tri kolinearne slobodne tacke. Tri kolinearne slobodne tacke napravljene su uz pomoc sest pravih. Neka su tih 6 pravih prvih 6 koje ce ucestvovati u presecima. Nijedna od ostalih pravih nema tu osobinu.

Neka su ovih 6 pravih postavljene optimalno (prema nasoj konstrukciji to znaci da je svaka postavljena kroz 2 vec postojece slobodne tacke). Medjutim, kada postavimo nasu prvu pravu koja ide kroz tri, ispada da su sve prave koje cine slobodne tacke koje su bile potrebne da se postavi ovih 6 prava -- zapravo prve prave sa osobinom da ucestvuju u obrazovanju tri kolinearne slobodne tacke, sto nije moguce -- osim u slucaju da je svaka od 6 pravih po optimalnoj konstrukciji prosla kroz manje od 2 tacke [ili da je postavljena kroz tacke koje cine ostalih 5 pravih] -- u svakom slucaju broj ostalih pravih je nula, a nasih 7 pravih su prvih 7 koje smo postavili. Posto znamo(?) koliki je broj preseka za 7 pravih mozemo proveriti(?) da ovako nesto nije moguce(??).

Da li se iz ovoga moze nesto izvuci? Naravno pod uslovom da nisam nesto zestoko lupio. :)

f

Mislim da si zaboravio postojanje skupova sa 2 preostala elementa koji se medju sobom ne preklapaju, a u isto vreme tacno nasao 4 podskupa od tri elementa. Ako imas vremena, molio bih da probas konstrukciju sa bipartitnim grafom, trebalo bi da upravo dobijes 4 podskupa sa osobinama koje si naveo i tri podskupa od po dva elementa.

Da objasnim detaljnije. Pretpostavi da postoji konstrukcija o kojoj govorimo. Ona ce imati preseka u kojem ucestvuju dve prave i preseka u kojem ucestvuju tri prave. Neka je ukupan broj preseka, a broj pravih koje smo postavili. (Izvinjavam se za zbrku u notaciji). Svaki trostruki presek vredi 3 obicna dvostruka. Zbir vrednosti svih preseka naravno mora biti koliki je maksimalan broj preseka pravih.

Dakle:

Ako se ovo resi po i uvidi da je pa zatim minimizuje n pod uslovom da mora biti vece i od i od dobije se donja granica. Za 6 pravih dobija se da je donja granica 5, sto pretpostavlja da smo uspeli da spakujemo sve preseke u cvorove po 3 elementa jer je tada . Ali ako dozvolimo da , vidimo da se moze povecavati samo u koracima po 3. Otud neslagane sa donjom granicom.

f

Onda se izvinjavam ako sam pogresno razumeo (a izgleda jesam :) ).


A da li moze da se iskoristi jednakos izmedju donje granice i tvoje formule kako bi se izracunalo x?


Probacu popodne da objasnim malo bolje, mozda bi najbolje bilo dati sliku.


Tako je. Sesta prava je prva koja moze da ide kroz dve slobodne tacke. Sve ostale prave generisu vise novih slobodnih tacaka nego sto oduzmu, tako da ih kasnije imamo sasvim dovoljno na lageru da bi konstrukcija bila moguca.

f


[Ovu poruku je menjao tOwk dana 26.07.2003. u 13:20 GMT]

Hm, moja poruka je izgleda poprimila "malo drugojaciji oblik".
Sto se tice one formule, ne verujem da bi mogla da se iskoristi jednakost, posto ona daje 7 za n=6, dok je donja granica valjda , sto daje 5 za n=6.

Au, al sam je „izmoderisao“! Izgleda da sam kliknuo na izmenu poruke umesto na reply. A jos sam se i cudio kad se nije pojavio citat...

U nadi da cu malo da ispravim stvar evo kako je poruka glasila:

Sorry.

Evo, ako nije bilo dovoljno zabune :

Ako sam dobro izbrojao, 12 pravih sa 19 punih i samo 5 slobodnih!

Mislim da ti fale 4 preseka. Slika mora da bude centralno simetricna. Dobijas ukupno 6 "dalekih" slobodnih tacaka a izgleda da na njih moze da se primeni isti fazon koji si upotrebio da bi na staru sliku dodao 3 nove prave! Zivo me zanima sta ces dobiti sa 15 pravih. :)

f

U pravu si, zanela sam se :)

Ne znam da li više može da se upotrebi ovaj fazon, jer dobijamo simetrične tačke, koje 'traže' da se spoje, a više ne smemo, jer već imamo 'horizontalnu' pravu.

U svakom slučaju, ja sam odustao da pokušavam sa onom forom kojom sam započeo, jer očigledno veliku ulogu igra specifičan položaj pravih. Rađa se neka nova ideja o formiranju trojki pravih, koje stvaraju kolinearne slobodne tačke...

Da ,onu sliku sto je poslao Branko, Filip je objasnio ,jer je to isto sto je Darko
nacrtao ,samo su ona 3 sjecista jako povucena izvan crteza.

Ovo sto je Darko jos dodao (10;11;12-i )pravac izgleda drzi vodu, ali sta dalje?
Dobro mozemo ovako reci:Ne mora onaj crtez biti bas onako simetrican.Moze se
on linearno preslikati pa da bude "zasukan" po zelji.

Sustina problema je napraviti za dati broj pravaca sto vise onih presjeka sa 3
pravca u tacki.Ajmo racunati taj broj da ne bude zabune N(3).(Ja sam nesto krivo
napisao za ono Mihailovo x).

Nesto zakonitosti sam i ja uhvatio bas do ovog 13-tog pravca ali dalje nisam
znao.Ima onaj problem na sedmom pravcu + ovo 13.Mislim da problem treba
rijesiti tako da se odredi N(3) u nekim granicama.Max. mozemo izracunati, a min.
koja je sigurna , e bogami malo teze ako zelimo biti sto blize minimumu presjeka.

Vjerovali ili ne:Ovaj zadatak je bio na prijemnom ispitu PMF-Zagreb-1970.Ja sam
samo dodao ono sa 9 i onu varijantu tacke-duzi nadajuci se da bi se moglo uci
u neku klasu kombinacija za koje postoji univerzalno objasnjenje.Inace ona vari-
janta sa tackama i duzima potpuno je simetricna ovoj oko koje se raspravlja.

Posle svega, jedino u šta sam siguran je da rešenje postoji.

Obe "škole" koje se ovde prepliću, imaju svoje nedostatke : oni koji pokušavaju da nacrtaju (tj. ja) nemaju dokaz da je to najmanji broj preseka; oni koji prave formule, nemaju dokaz da se to može nacrtati. Kombinatorika jedino čuva aksiomu o postojanju samo jedne prave kroz dve tačke. Da ne kažem da nikako ne može da kalkuliše sa specifičnim položajima.

Moja početna ideja ima sledeći nedostatak : "kumulativna" konstrukcija želi u svakom koraku najmanji broj preseka, ali koristeći prethodnu "topologiju". Ovo ne znači da nije moguće dobiti manje preseka polazeći od topologije koja ima više preseka, tj. koja nije minimalna.

Evo jednog primera : ako nacrtamo konveksni četvorougao čije naspramne stranice nisu paralelne i dodamo dijagonale, dobijamo 6 pravih i 7 presečnih tačaka (3 slobodne) : 4 temena, 1 presek dijagonala i 2 presečne tačke produžetaka stranica. Na pretprethodno priloženoj slici (onoj sa 9 pravih, mada isto važi i za narednu) se ne može naći opisana situacija, niti ima 6 pravih sa <= brojem p.t. Dakle kumuluse - ćao.

Ako je ovo zaista zadatak sa prijemnog, nešto mi tu kandiše. Nije samo zato što ja ne znam da rešim :) Hoću da kažem, ili svi mi ovde ne vidimo nešto relativno prosto, ili su se malo prešli oni koji su dali ovaj zadatak... možda misleći na nešto relativno prosto :)

U svakom slučaju, ima nešto sa ovim rešenjima sa brojem pravih koji je deljiv sa 3. Možda treba probati sa takvima, pa onda dopuniti za ostalo...?

Ja se izvinjavam što šaljem poruku koja nema veze sa temom, ali moram da se požalim da mi u poslednja dva dana svaka poruka sa iste stiže na mejl. Dakle, ako je greška do mene, molim nekoga (na primer, Filipa, kojem sam izgleda bez uspeha pokušao da pošaljem privatnu poruku u par navrata) da mi kaže šta bih trebao da uradim da se to ne dešava.
I da ne bude sve van okvira teme, samo da prokomentarišem da mi se čini da ni formula koju je dao Filip na osnovu Darkove strategije ne daje tačan rezultat u slučaju da je Darkova slika za n=12 dobra.

Bojim se da sam za to kriv upravo ja sa svojim „genijalnim“ ispadom. Naime umesto da napisem odgovor, iskasapio sam tvoju poruku a to mi onda nije bilo dosta vec sam trazio obavestenja mejlom o prispelim odgovorima. Posto je poruka bila tvoja, vrlo je lako zamislivo da su ogovori poceli da se prosledjuju tebi. Da bi se otarasio ovih poruka, treba da je dovoljno da u istoj temi napises jos jednu u kojoj neces traziti obavestavanje. Sadrzaj same poruke nije bitan, kasnije je mozes i obrisati.

Jos jednom se izvinjavam na zbrci.



To vec ne bi smelo da se desava. Mozda bi mogao da se oglasis u forumu Predlozi i pitanja i opises sta se desilo.


Na zalost, u pravu si. Formula je data pod pretpostavkom da se moze napraviti konstrukcija crteza u kome se u svakom koraku ustedi na (bar) 4 preseka.

f

Što se tiče ovog obaveštavanja... ja mislim da je neophodno da izmeni poruku u kojoj je potvrdio da želi obaveštavanje na mail (ili u kojoj si ti to uradio za njega, svejedno) i skine potvrdu sa tog polja.

Filimilova formula ne daje minimum, ali je ipak neka vrsta aproksimacije. Za 12 ona daje 34, a ako je moja slika za 12 dobra, tu ima 28 presečnih tačaka. Da li može manje, to je drugo pitanje.

Usput, može se uočiti i sledeća pravilnost :
za 3 prave imamo 1 presečnu tačku
za 6 pravih, 1 + 6 = 7
za 9 pravih, 7 + 9 = 16
za 12 pravih, 16 + 12 = 28.

Što se tiče rezultata za 6 pravih, takvu konstrukciju je predočio Mihailo (trougao i tri težišne duži), a moja skica sa četvorouglom iz prethodnog posta je ekvivalentna. Za 9 i 12 pravih imamo sliku. Treba naravno dokazati da ne može manje... (eventualno dati dokaz da je ona slika sa 12 pravih moguća, tj. da nema optičke varke, čisto da ne bi morali svaki put da pišemo "ako je ona slika dobra" :).

Evo i nekog mog(nazovite) resenja(kad svi mogu,'ocu i ja da lupam)
BrojPresecnih=(1/9)(n nad 3)+(3n/27)+ceodeo(n/2)
n=3k,keN
(Jako se izvinjavam sto nije preko tex-a,ali lose se snalazim,tutorial da skinem ne mogu...)
I slucaj:Ovo je tacno resenje.Onda se ovi ogromni koeficijenti mogu objasniti zato sto je ovo samo poseban slucaj kada je n deljivo sa 3.Protpostavljam da se i ostala dva slucaja mogu ugurati pod ovaj i da ce se nesto pokratiti,pa da ispadne onako nekako kompaktno
II slucaj-Ovo nije tacno resenje.Kad vec ovo nije tacno resenje,da dam neka moja opsta razmisljanja do kojih sam dosao bez teorije,cisto zadravim razumom(a i svako drugi bi)
Verujem da ako imamo n pravih,one moraju biti simetricno rasporedjene,tj. prava k gradi ugao sa x-osom od (pi/n)*k (k=0...n-1).Takodje mislim da se nadogradjivanjem postojece slike sa minimalno tacaka(sa n pravih),dodavanjem jedne prave dobija opet minimalno resenje sa n+1 pravom.Prave bi se dodavale tako da "popunjavaju rupe" u uglovima.
P.S.A mozda smo mi samo malo "pametniji" od srednjoskolaca,ne verujem da srednjoskolci,pa nek su i iz gimnazije,upotrebljavaju funkciju ceo deo.Mozda su je pominjali,ali verujem da se na tome i zavrsava.Mislim,ocigledno je da ako se zadatak pojavljivao za prijemni,da je resiv itekako.Sansa da su se profesori prevarili ili da milan ima knjigu u kojoj je lose prenet zadatak su 1% max.Zato,keep on tryin'
P.S.S.Ako imas taj "rok",da nema mozda ono a),b),c),d)...To bi mnogo pomoglo:)

To sigurno ne. Pogledaj neki od mojih prethodnih postova. Ili pokušaj ovo : sa one slike sa 9 pravih, skini 3 prave i probaj da dobiješ 7 preseka; ovaj broj preseka sa 6 pravih može lako da se dobije, već je ovde diskutovano.