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

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

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

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

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.

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

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)

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

Valjda može ovako:




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

Hoces reci ovako:


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

Naravno, može i tako

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

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

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

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.

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

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

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.