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

Bojan Basic
Novi Sad

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

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253

+621 Profil

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

^{26.10.2005. u 23:08 - pre 237 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

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

^{26.10.2005. u 23:36 - pre 237 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

BoxUp
interesantna logička igra
Monty Hall paradoks - interaktivni demo

Prikačeni fajlovi

net.png - 4k

Odgovor na temu

uranium
Beograd

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

Jabber: uranium@elitesecurity.org
ICQ: 324386953

+5 Profil

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

^{26.10.2005. u 23:40 - pre 237 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

+621 Profil

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

^{27.10.2005. u 11:30 - pre 237 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

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

^{28.10.2005. u 14:30 - pre 237 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

+621 Profil

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

^{28.10.2005. u 21:41 - pre 237 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: 12881

+4827 Profil

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

^{29.10.2005. u 06:41 - pre 237 meseci}

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

Nebojsa Milanovic:
-Trumpa smatram vrhunskim predsednikom i voleo bih da živim u državi na čijem je on čelu
-Rusija ne laže, ne vodi osvajačke ratove
-Trump je svetla tačka u USA blatu
-Elon Musk, možda najpametniji i najtrezveniji Amerikanac

Odgovor na temu

Leftist
Luka Stojanovic
Bg

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

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

+5 Profil

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

^{29.10.2005. u 12:50 - pre 237 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)

Go Beograd
Reggae Serbia
Black Ark

Odgovor na temu

noviKorisnik
Dejan Katašić
Novi Sad

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

Sajt: www.novikorisnik.net

+5 Profil

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

^{29.10.2005. u 17:01 - pre 237 meseci}

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

BoxUp
interesantna logička igra
Monty Hall paradoks - interaktivni demo

Odgovor na temu

uranium
Beograd

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

Jabber: uranium@elitesecurity.org
ICQ: 324386953

+5 Profil

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

^{29.10.2005. u 18:59 - pre 237 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

n3.gif - 8.6k

Odgovor na temu

Leftist
Luka Stojanovic
Bg

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

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

+5 Profil

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

^{29.10.2005. u 23:21 - pre 237 meseci}

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

Odgovor na temu

uranium
Beograd

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

Jabber: uranium@elitesecurity.org
ICQ: 324386953

+5 Profil

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

^{30.10.2005. u 00:30 - pre 237 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

+621 Profil

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

^{30.10.2005. u 00:54 - pre 237 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

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

^{30.10.2005. u 10:59 - pre 237 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 :-)))

BoxUp
interesantna logička igra
Monty Hall paradoks - interaktivni demo

Odgovor na temu

noviKorisnik
Dejan Katašić
Novi Sad

Član broj: 13216
Poruke: 4533
195.178.55.*

Sajt: www.novikorisnik.net

+5 Profil

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

^{16.09.2011. u 11:42 - pre 165 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.

BoxUp
interesantna logička igra
Monty Hall paradoks - interaktivni demo

Odgovor na temu

Bojan Basic
Novi Sad

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

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253

+621 Profil

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

^{16.09.2011. u 11:53 - pre 165 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

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

^{20.09.2011. u 14:28 - pre 165 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

+621 Profil

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

^{21.09.2011. u 20:44 - pre 165 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