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
![](https://static.elitesecurity.org/tex/f56b8f2571f990f108688a1f6a57b201.png)
, za
![](https://static.elitesecurity.org/tex/a4740b0385dddda09fffd625569b62a4.png)
.
Jer, budući da jedna duž može da sadrži najviše
![](https://static.elitesecurity.org/tex/bd2b320696c94ea17dd122cd137b965c.png)
tačaka, ako bi bilo
![](https://static.elitesecurity.org/tex/24613655562ddf23b826bc9c9244779d.png)
, onda bi bilo
![](https://static.elitesecurity.org/tex/3d481489dc9321a14d2cd6dfa401c5ce.png)
, pa nebismo pokrili sve tačke, znači mora biti
![](https://static.elitesecurity.org/tex/d91aa7e2a08a96ef962cc491973e4e9d.png)
. Međutim, ne može biti
![](https://static.elitesecurity.org/tex/90fd5e017b59630416935ea65eb60a4f.png)
, jer to bi značilo da svaka duž mora imati po
različitih tačaka pa bismo onda imali
![](https://static.elitesecurity.org/tex/bd2b320696c94ea17dd122cd137b965c.png)
komponenata povezanosti, a nama treba
jedna komponenta povezanosti.
Dakle,
![](https://static.elitesecurity.org/tex/5fa2a4d31a2ec94ac5106d48dea0fa07.png)
.
E sad, da vidimo da je uvek moguće napraviti put dužine
![](https://static.elitesecurity.org/tex/d280d8a07c22ccbc61ff0582d970b34f.png)
.
Pošto me mrzi da crtam, evo primera za
![](https://static.elitesecurity.org/tex/ad4dd664172b6d6bb2c3128253ab776c.png)
, a ostali slučajevi se rešavaju
potpuno analogno.
Označimo čvorove kao:
![](https://static.elitesecurity.org/tex/4d3cd05284ba56f081c95fb81b018979.png)
, onda je traženi put:
![](https://static.elitesecurity.org/tex/5606a1b8f88058c836ab65d987249c43.png)
.
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.