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

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?

Potpis

Ljubičice crvena, što si plava kô zelena trava.

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

Potpis

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

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

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Nije baš toliko jednostavno - može to još manje :)

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.

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

Potpis

Ljubičice crvena, što si plava kô zelena trava.

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

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

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.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

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

Potpis

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

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)

Potpis

Go Beograd
Reggae Serbia
Black Ark

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

Potpis

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

Valjda može ovako:




_{[Ovu poruku je menjao uranium dana 30.10.2005. u 01:05 GMT+1]}

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Hoces reci ovako:


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

Potpis

Go Beograd
Reggae Serbia
Black Ark

Naravno, može i tako

_{[Ovu poruku je menjao uranium dana 30.10.2005. u 01:41 GMT+1]}

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

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

Potpis

Ljubičice crvena, što si plava kô zelena trava.

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

Potpis

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

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.

Potpis

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

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

Potpis

Ljubičice crvena, što si plava kô zelena trava.

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

Potpis

"Ne teče reka, nego voda. Kao što ne prolazi vrijeme, nego mi"

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.

Potpis

Ljubičice crvena, što si plava kô zelena trava.