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

Bojan Basic
Novi Sad

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

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253

Profil

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

^{26.10.2005. u 23:08}

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.

^{26.10.2005. u 23:08}

noviKorisnik

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

Profil

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

^{26.10.2005. u 23:36}

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

net.png - 4k

^{26.10.2005. u 23:36}

uranium
Beograd

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

Jabber: uranium@elitesecurity.org
ICQ: 324386953

Profil

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

^{26.10.2005. u 23:40}

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

^{26.10.2005. u 23:40}

Bojan Basic
Novi Sad

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

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253

Profil

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

^{27.10.2005. u 11:30}

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.

^{27.10.2005. u 11:30}

uranium
Beograd

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

Jabber: uranium@elitesecurity.org
ICQ: 324386953

Profil

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

^{28.10.2005. u 14:30}

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

^{28.10.2005. u 14:30}

Bojan Basic
Novi Sad

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

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253

Profil

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

^{28.10.2005. u 21:41}

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.

^{28.10.2005. u 21:41}

Shadowed
.NET developer

SuperModerator
Član broj: 649
Poruke: 9016
*.adsl.sezampro.yu.

Sajt: www.diskusije.net

Profil

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

^{29.10.2005. u 06:41}

Hmm, ja znam kako da uradim za n=3 sa 4 duzi ali nikako da to primenim na n>3...

^{29.10.2005. u 06:41}

Leftist
Luka Stojanovic
Bg

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

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

Profil

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

^{29.10.2005. u 12:50}

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)

Go Beograd
Reggae Serbia
Black Ark

^{29.10.2005. u 12:50}

noviKorisnik

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

Profil

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

^{29.10.2005. u 17:01}

Ja baš nisam uspeo da nađem rešenje od 4 poteza za n=3. Okačite sliku, please...

^{29.10.2005. u 17:01}

uranium
Beograd

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

Jabber: uranium@elitesecurity.org
ICQ: 324386953

Profil

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

^{29.10.2005. u 18:59}

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

n3.gif - 8.6k

^{29.10.2005. u 18:59}

Leftist
Luka Stojanovic
Bg

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

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

Profil

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

^{29.10.2005. u 23:21}

Hoces reci ovako:

_{[Ovu poruku je menjao Leftist dana 30.10.2005. u 00:23 GMT+1]}

Go Beograd
Reggae Serbia
Black Ark

Prikačeni fajlovi

mrt.png - 5.76k

^{29.10.2005. u 23:21}

uranium
Beograd

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

Jabber: uranium@elitesecurity.org
ICQ: 324386953

Profil

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

^{30.10.2005. u 00:30}

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

^{30.10.2005. u 00:30}

Bojan Basic
Novi Sad

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

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253

Profil

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

^{30.10.2005. u 00:54}

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

^{30.10.2005. u 00:54}

noviKorisnik

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

Profil

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

^{30.10.2005. u 10:59}

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

^{30.10.2005. u 10:59}