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

[Zadatak]: Pokrivanje kvadratne mreže tačaka u jednom potezu

[es] :: Matematika :: [Zadatak]: Pokrivanje kvadratne mreže tačaka u jednom potezu

[ Pregleda: 9582 | Odgovora: 17 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Bojan Basic
Novi Sad

SuperModerator
Član broj: 6578
Poruke: 3996
*.smin.sezampro.yu.

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253


+605 Profil

icon [Zadatak]: Pokrivanje kvadratne mreže tačaka u jednom potezu26.10.2005. u 23:08 - pre 224 meseci
Dato je parče celobrojne mreže oblika kvadrata sa ukupno tačaka (dakle, dužine stranica kvadrata su ). Potrebno je nacrtati izlomljenu liniju koja pokriva sve ove tačke. Od koliko najmanje duži mora biti sačinjena ta izlomljena linija?
Ljubičice crvena, što si plava kô zelena trava.
 
Odgovor na temu

noviKorisnik
Dejan Katašić
Novi Sad

Član broj: 13216
Poruke: 4533
*.dialup.neobee.net.

Sajt: www.novikorisnik.net


+5 Profil

icon Re: [Zadatak]: Pokrivanje kvadratne mreže tačaka u jednom potezu26.10.2005. u 23:36 - pre 224 meseci
Da krenem pešački, indukcijom :-)

n = 1 -- izem ga, ovo je 0 ili 1, pre će biti 1, verovatno nije bitno

n = 2 -- 3 linije

n = 3 -- 5 linija (baš neka indukcija, crtam spirale u glavi :-)

n = 4 -- 7 linija ...

recimo... 2n - 1
Prikačeni fajlovi
 
Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953


+5 Profil

icon Re: [Zadatak]: Pokrivanje kvadratne mreže tačaka u jednom potezu26.10.2005. u 23:40 - pre 224 meseci
Samo da proverim da li sam dobro shvatio:
ako dobijenu strukturu (posle povlačenja svih duži) shvatimo kao graf, da li je onda dozvoljeno da neki od čvorova ima stepen veći od 2?
I da li će se pod duži, podrazumevati grana grafa ili klasična geometrijska duž?

[Ovu poruku je menjao uranium dana 27.10.2005. u 02:21 GMT+1]
Attempt all the problems. Those you can do, don't do. Do the ones you cannot.
 
Odgovor na temu

Bojan Basic
Novi Sad

SuperModerator
Član broj: 6578
Poruke: 3996
*.smin.sezampro.yu.

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253


+605 Profil

icon Re: [Zadatak]: Pokrivanje kvadratne mreže tačaka u jednom potezu27.10.2005. u 11:30 - pre 224 meseci
Citat:
noviKorisnik:
recimo... 2n - 1

Nije baš toliko jednostavno - može to još manje :)
Citat:
uranium:
Samo da proverim da li sam dobro shvatio:
ako dobijenu strukturu (posle povlačenja svih duži) shvatimo kao graf, da li je onda dozvoljeno da neki od čvorova ima stepen veći od 2?

Nisam siguran da li pod čvorom podrazumevaš date početne tačke ili čvorom nazivaš i svaki presek te izlomljene linije sa samom sobom, ali i u jednom i u drugom slučaju je dozvoljeno. S druge strane, jedna duž može da pokrije i više tačaka, odnosno date tačke ne moraju da predstavljaju krajeve duži već mogu i da leže na njoj.
Citat:
uranium:
I da li će se pod duži, podrazumevati grana grafa ili klasična geometrijska duž?

Klasična geometrijska duž. Znači, ako se dve duži koje su deo te izlomljene linije preseku, njih i dalje brojimo kao dve duži (a ne tri ili četiri).
Ljubičice crvena, što si plava kô zelena trava.
 
Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953


+5 Profil

icon Re: [Zadatak]: Pokrivanje kvadratne mreže tačaka u jednom potezu28.10.2005. u 14:30 - pre 224 meseci
Verovatno nije u redu, ali makar da krenemo sa mrtve tačke

Ako je dozvoljeno proći jednom istom granom po jednom u svakom smeru, onda je minimalan broj duži , za .

Jer, budući da jedna duž može da sadrži najviše tačaka, ako bi bilo , onda bi bilo , pa nebismo pokrili sve tačke, znači mora biti . Međutim, ne može biti , jer to bi značilo da svaka duž mora imati po različitih tačaka pa bismo onda imali komponenata povezanosti, a nama treba jedna komponenta povezanosti.
Dakle, .
E sad, da vidimo da je uvek moguće napraviti put dužine .

Pošto me mrzi da crtam, evo primera za , a ostali slučajevi se rešavaju potpuno analogno.

Označimo čvorove kao: , onda je traženi put: .

Ukratko, crtež nastaje tako što povučemo po jednu duž po svim: ili kolonama ili vrstama, a zatim i jednu duž po: ili sporednoj ili glavnoj dijagonali.

[Ovu poruku je menjao uranium dana 28.10.2005. u 15:38 GMT+1]
Attempt all the problems. Those you can do, don't do. Do the ones you cannot.
 
Odgovor na temu

Bojan Basic
Novi Sad

SuperModerator
Član broj: 6578
Poruke: 3996
*.smin.sezampro.yu.

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253


+605 Profil

icon Re: [Zadatak]: Pokrivanje kvadratne mreže tačaka u jednom potezu28.10.2005. u 21:41 - pre 224 meseci
Citat:
uranium:
Ako je dozvoljeno proći jednom istom granom po jednom u svakom smeru, onda je minimalan broj duži , za .

Jednom granom je dozvoljeno proći samo jednom bez obzira na smer. Znači, stavimo olovku na jedno mesto i, ne podižući je, povlačimo je po papiru pri čemu ne smemo istu liniju crtati dva puta (ali smemo da sečemo). NoviKorisnik je, čini mi se, dobro shvatio šta se traži u zadatku, ali mu rezultat nije dobar.
Ljubičice crvena, što si plava kô zelena trava.
 
Odgovor na temu

Shadowed
Vojvodina

Član broj: 649
Poruke: 12846



+4783 Profil

icon Re: [Zadatak]: Pokrivanje kvadratne mreže tačaka u jednom potezu29.10.2005. u 06:41 - pre 224 meseci
Hmm, ja znam kako da uradim za n=3 sa 4 duzi ali nikako da to primenim na n>3...
 
Odgovor na temu

Leftist
Luka Stojanovic
Bg

Član broj: 21766
Poruke: 401
*.drenik.net.

Jabber: slartibartfast@jabber.cc
Sajt: www.reggae.rs


+5 Profil

icon Re: [Zadatak]: Pokrivanje kvadratne mreže tačaka u jednom potezu29.10.2005. u 12:50 - pre 224 meseci
ja sam n=3, 4, 5 resio sa 4, 6 i 8 duzi, sto je za 1 bolje od novoKorisnikovog resenja, znam kako sam dosao do toga, ali ne znam kako da resenje uopstim za bilo koje n...


(hint: duz ne mora da se zavrsi sa ivicom kvadrata)
 
Odgovor na temu

noviKorisnik
Dejan Katašić
Novi Sad

Član broj: 13216
Poruke: 4533
*.dialup.neobee.net.

Sajt: www.novikorisnik.net


+5 Profil

icon Re: [Zadatak]: Pokrivanje kvadratne mreže tačaka u jednom potezu29.10.2005. u 17:01 - pre 224 meseci
Ja baš nisam uspeo da nađem rešenje od 4 poteza za n=3. Okačite sliku, please...
 
Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953


+5 Profil

icon Re: [Zadatak]: Pokrivanje kvadratne mreže tačaka u jednom potezu29.10.2005. u 18:59 - pre 224 meseci
Valjda može ovako:




[Ovu poruku je menjao uranium dana 30.10.2005. u 01:05 GMT+1]
Attempt all the problems. Those you can do, don't do. Do the ones you cannot.
Prikačeni fajlovi
 
Odgovor na temu

Leftist
Luka Stojanovic
Bg

Član broj: 21766
Poruke: 401
*.drenik.net.

Jabber: slartibartfast@jabber.cc
Sajt: www.reggae.rs


+5 Profil

icon Re: [Zadatak]: Pokrivanje kvadratne mreže tačaka u jednom potezu29.10.2005. u 23:21 - pre 224 meseci
Hoces reci ovako:


[Ovu poruku je menjao Leftist dana 30.10.2005. u 00:23 GMT+1]
Prikačeni fajlovi
 
Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953


+5 Profil

icon Re: [Zadatak]: Pokrivanje kvadratne mreže tačaka u jednom potezu30.10.2005. u 00:30 - pre 224 meseci
Naravno, može i tako

[Ovu poruku je menjao uranium dana 30.10.2005. u 01:41 GMT+1]
Attempt all the problems. Those you can do, don't do. Do the ones you cannot.
 
Odgovor na temu

Bojan Basic
Novi Sad

SuperModerator
Član broj: 6578
Poruke: 3996
*.smin.sezampro.yu.

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253


+605 Profil

icon Re: [Zadatak]: Pokrivanje kvadratne mreže tačaka u jednom potezu30.10.2005. u 00:54 - pre 224 meseci
Što nekad mrzim sebe kad loše napišem postavku pa posle moram da se ispravljam/dopunjujem :)

Sličica koju je uranium ostavio nije korektna jer svaku duž moramo nacrtati odjednom, ne može prvo pola, pa onda nacrtamo nešto drugo, i onda druga polovina (kao što su na njegovom crtežu duži 1-7 i 3-5). U ovom slučaju to se računa kao 6 duži (mada priznajem da u postavci nisam precizno razjasnio taj deo). Možda je najjednostavnije reći da brojimo koliko načinimo skretanja olovkom (pri čemu postavljanje olovke na papir brojimo kao prvo skretanje, čisto radi konzistentnosti sa ovom prethodnom definicijom). Bilo kako bilo, nadam se da je konačno jasno kako linija treba da izgleda i šta se od svega toga broji.

Ono što sam zaista imao u vidu za je rešenje koje je Leftist dao (mogu da kažem da se ovaj slučaj već pojavljivao na ES-u, videti http://www.elitesecurity.org/tema/125614, ali nisam hteo odmah da ostavljam link da ne upropastim zabavu). Rešenje ovog slučaja je korak unapred, preostaju nam još dve stvari: da nađemo konstrukcije za i da dokažemo da ne možemo bolje od toga :)
Ljubičice crvena, što si plava kô zelena trava.
 
Odgovor na temu

noviKorisnik
Dejan Katašić
Novi Sad

Član broj: 13216
Poruke: 4533
*.dialup.neobee.net.

Sajt: www.novikorisnik.net


+5 Profil

icon Re: [Zadatak]: Pokrivanje kvadratne mreže tačaka u jednom potezu30.10.2005. u 10:59 - pre 224 meseci


Evo konstrukcije za n > 2 i 2(n - 1) poteza . . . Dalje se samo nastavlja po spoljnoj spirali, za svaku sledeću brojku dimenzije doda se po još 2 duži.

Eto, dokazano je da može bolje od onoga što sam prvo rekao, sad još da se dokaže da ne može bolje od ovoga (ili opet da može :-)))
 
Odgovor na temu

noviKorisnik
Dejan Katašić
Novi Sad

Član broj: 13216
Poruke: 4533
195.178.55.*

Sajt: www.novikorisnik.net


+5 Profil

icon Re: [Zadatak]: Pokrivanje kvadratne mreže tačaka u jednom potezu16.09.2011. u 11:42 - pre 152 meseci
Ova tema još uvek stoji izlistana među nerešenim zadacima :-)

Potražio sam ima li odgovora na mreži... Evo jedne stranice koja obrađuje temu: Most Wanted Puzzle Solutions - The Nine Dot Puzzle. Pored nekoliko zanimljivih razmatranja, na kraju se dotiče i generalizacije problema, gde se navodi da se minimalno rešenje poklapa s prethodnom pretpostavkom, iako ne vidim formalni dokaz tvrdnje.
 
Odgovor na temu

Bojan Basic
Novi Sad

SuperModerator
Član broj: 6578
Poruke: 3996
*.dynamic.sbb.rs.

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253


+605 Profil

icon Re: [Zadatak]: Pokrivanje kvadratne mreže tačaka u jednom potezu16.09.2011. u 11:53 - pre 152 meseci
Citat:
noviKorisnik:
...gde se navodi da se minimalno rešenje poklapa s prethodnom pretpostavkom, iako ne vidim formalni dokaz tvrdnje.

Dokaz optimalnosti rešenja i jeste ono što nedostaje u ovoj temi, i zbog čega ona i dalje stoji na listi nerešenih zadataka. Eto prilike, kad si reaktivirao temu, da zainteresovani još jednom pokušaju. Ako ne bude uspeha, objaviću rešenje za tri-četiri dana (zapravo je iznenađujuće jednostavno).
Ljubičice crvena, što si plava kô zelena trava.
 
Odgovor na temu

kaćunčica

Član broj: 271602
Poruke: 31
*.mynsn.net.



+2323 Profil

icon Re: [Zadatak]: Pokrivanje kvadratne mreže tačaka u jednom potezu20.09.2011. u 14:28 - pre 152 meseci
Padalo mi je na pamet da polazne tačke posmatram kao kvadratnu matricu, pa onda donosim zaključke o indeksima koji su na istoj duži... Sreća da je danas četvrti dan, pa ćemo videti rešenje :)
"Ne teče reka, nego voda. Kao što ne prolazi vrijeme, nego mi"
 
Odgovor na temu

Bojan Basic
Novi Sad

SuperModerator
Član broj: 6578
Poruke: 3996
*.dynamic.sbb.rs.

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253


+605 Profil

icon Re: [Zadatak]: Pokrivanje kvadratne mreže tačaka u jednom potezu21.09.2011. u 20:44 - pre 152 meseci
Evo dokaza. Izvinjavam se zbog kašnjenja od celog jednog dana, kako je kaćunčica to strogo izbrojala.

Pretpostavimo da postoji redova kolona na kojima ne leži nijedno parče uočene putanje. Ako je , mreža veličine koju oni formiraju ima rubne tačke. Svaka koso parče putanje pokriva najviše dve od ovih tačaka. Dakle, putanja ukupno mora imati bar kosih parčića, horizontalnih i vertikalnih, što čini ukupno bar parčeta. Ako je ili jednako ili , tada se lako proterava da putanja mora imati bar čak parče.

To je sve. Meni se ovo dopalo zato što je stvarno neočekivano jednostavno, a i pomalo čudno deluje da se posle tako galantnih aproksimacija u gornjem pasusu (primetiti, na primer, da su sasvim ignorisane tačke mreže koje nisu na rubu) na kraju ipak ispostavi da nismo preterali s aproksimacijama.

Dakle, zahvaljujući inicijativi novogKorisnika, zadatak je najzad skinut s liste nerešenih.
Ljubičice crvena, što si plava kô zelena trava.
 
Odgovor na temu

[es] :: Matematika :: [Zadatak]: Pokrivanje kvadratne mreže tačaka u jednom potezu

[ Pregleda: 9582 | Odgovora: 17 ] > FB > Twit

Postavi temu Odgovori

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