[es] - Kvrgave kombinacije

zzzz
milan kecman
bluka

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

Profil

^{22.07.2003. u 00:33}

Zna li neko ovo: U ravni imamo 9 pravaca koji se medjusobno sijeku.
Ako je dozvoljeno da se u jednoj tacki moze sjeci najvise 3 pravca
koliko najmanje presjecnih tacaka moze biti ?

Zapravo zadatak je jos slozeniji: n pravaca, isti uslovi, koliko najmanje
sjecista?
Ili ko voli tacke:n tacaka u ravnini od kojih max. tri smiju biti na jednoj duzi.
(to se broji kao jedna duz).Svaka tacka spojena je sa svim ostalim.Minimalni
broj duzi je ?

Probajte rijesiti bar ono prvo, nije bas lako.(Vazi i za tacke).

^{22.07.2003. u 00:33}

zzzz
milan kecman
bluka

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

Profil

Re: Kvrgave kombinacije

^{23.07.2003. u 02:10}

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!

^{23.07.2003. u 02:10}

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.adsl.zonnet.nl

Jabber: filmil@jabber.org
ICQ: 36601391

Profil

Re: Kvrgave kombinacije

^{23.07.2003. u 02:30}

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

^{23.07.2003. u 02:30}

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3644
*.ihug.net

Profil

Re: Kvrgave kombinacije

^{23.07.2003. u 13:40}

Da nije resenje

?
Znaci za primer sa 9 pravih resenje je 30?

^{23.07.2003. u 13:40}

darkosos
Darko Šoš
Beograd

Član broj: 5053
Poruke: 616
*.ptt.yu

Profil

Re: Kvrgave kombinacije

^{23.07.2003. u 14:42}

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.

^{23.07.2003. u 14:42}

Mihailo Kolundzija
Novi Sad

Član broj: 11323
Poruke: 100
*.hut.fi

Profil

Re: Kvrgave kombinacije

^{23.07.2003. u 15:13}

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

^{23.07.2003. u 15:13}

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.et.tudelft.nl

Jabber: filmil@jabber.org
ICQ: 36601391

Profil

Re: Kvrgave kombinacije

^{23.07.2003. u 15:30}

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.

^{23.07.2003. u 15:30}

Mihailo Kolundzija
Novi Sad

Član broj: 11323
Poruke: 100
*.hut.fi

Profil

Re: Kvrgave kombinacije

^{23.07.2003. u 15:45}

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

^{23.07.2003. u 15:45}

zzzz
milan kecman
bluka

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

Profil

Re: Kvrgave kombinacije

^{23.07.2003. u 18:35}

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.

^{23.07.2003. u 18:35}

darkosos
Darko Šoš
Beograd

Član broj: 5053
Poruke: 616
*.ptt.yu

Profil

Re: Kvrgave kombinacije

^{23.07.2003. u 21:50}

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

^{23.07.2003. u 21:50}

zzzz
milan kecman
bluka

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

Profil

Re: Kvrgave kombinacije

^{23.07.2003. u 23:48}

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?

^{23.07.2003. u 23:48}

darkosos
Darko Šoš
Beograd

Član broj: 5053
Poruke: 616
*.ptt.yu

Profil

Re: Kvrgave kombinacije

^{24.07.2003. u 01:11}

Hm, znači ovako :

Lepo...

Prikačeni fajlovi

prave_o.GIF - 7.6k

^{24.07.2003. u 01:11}

stalker
Branko Kokanovic
Beograd

Član broj: 11897
Poruke: 601
*.drenik.net

Profil

Re: Kvrgave kombinacije

^{24.07.2003. u 02:13}

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

Prikačeni fajlovi

1.bmp - 1.76k

^{24.07.2003. u 02:13}

Mihailo Kolundzija
Novi Sad

Član broj: 11323
Poruke: 100
130.233.18.*

Profil

Re: Kvrgave kombinacije

^{24.07.2003. u 07:17}

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

^{24.07.2003. u 07:17}

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.adsl.zonnet.nl

Jabber: filmil@jabber.org
ICQ: 36601391

Profil

Re: Kvrgave kombinacije

^{24.07.2003. u 10:04}

Citat:

stalker:
Za 9 pravih imam 13 tacaka...

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

^{24.07.2003. u 10:04}

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
130.161.181.*

Jabber: filmil@jabber.org
ICQ: 36601391

Profil

Re: Kvrgave kombinacije

^{24.07.2003. u 11:01}

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

^{24.07.2003. u 11:01}

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
130.161.181.*

Jabber: filmil@jabber.org
ICQ: 36601391

Profil

Re: Kvrgave kombinacije

^{24.07.2003. u 11:16}

Citat:

Mihailo Kolundzija:
uspeo da nadjem samo četiri takva podskupa (a po toj formuli bi ih bilo 5). (možda

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

^{24.07.2003. u 11:16}

Mihailo Kolundzija
Novi Sad

Član broj: 11323
Poruke: 100
*.hut.fi

Profil

Re: Kvrgave kombinacije

^{24.07.2003. u 12:12}

Citat:

ali to nije ono sto sam ja hteo da kazem.

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

Citat:

U onom odgovoru sam se samo osvrnuo na formulu za to "x"

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

Citat:

objasnjenje iznad sa 6 pravih mi malo deluje nejasno

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

Citat:

taktiku sa postavljanjem pravih kroz dve slobodne tacke mozemo primeniti tak posle postavljanja 5 pravih.

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]

^{24.07.2003. u 12:12}

Mihailo Kolundzija
Novi Sad

Član broj: 11323
Poruke: 100
*.hut.fi

Profil

Re: Kvrgave kombinacije

^{24.07.2003. u 13:55}

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.

^{24.07.2003. u 13:55}

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
130.161.181.*

Jabber: filmil@jabber.org
ICQ: 36601391

Profil

Re: Kvrgave kombinacije

^{24.07.2003. u 17:44}

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.

Citat:

Mihailo Kolundzija:
Filipe, u pravu si, ali to nije ono sto sam ja hteo da kazem. "Moja formula" i
podrazumeva ono sto si ti rekao. Znaci, od maksimalnog broja preseka oduzmem
broj tacaka u kojoj se seku tri prave pomnozen sa dva (jer ta tacka od tri
presecne tacke "napravi" jednu, to jest smanji broj tacaka za dva). Za taj broj
tacaka sam pretpostavio da je jednak broju onih troclanih podskupova koji ne
smeju da imaju presek sa dva ili vise elemenata (jer bi to znacilo da dve prave
ucestvuju u vise od jednog "trilinga", sto naravno nije moguce).
U onom odgovoru sam se samo osvrnuo na formulu za to "x" (broj troclanih
podskupova), jer ona koju je dao Milan ne daje resenje za n=6 (daje 5 umesto
4).
Uzgred, ono objasnjenje iznad sa 6 pravih mi malo deluje nejasno, sto ne znaci
da nije dobro.
Inace, ne znam da li ste primetili, ali onu taktiku sa postavljanjem pravih
kroz dve slobodne tacke mozemo primeniti tak posle postavljanja 5 pravih (ako
se nisam presao).

^{24.07.2003. u 17:44}