423

Izlomljena linija od $n-1$ duži ima $n$ temena, a ona su različite tačke od datih $n$; dakle, linija prolazi kroz sve date tačke. Neka su temena redom $A_1,A_2,\ldots,A_n .$ Posmatramo $n\ge3$ (za $n=2$ postoji samo jedna duž).

Ključno zapažanje: posle svakog koraka obiđene tačke čine jedan neprekidan luk kruga, a linija se nalazi na jednom kraju tog luka. Kada bi linija iz $A_k$ otišla u tačku $X$ koja nije susedna obiđenom luku, sa obe strane tetive $A_kX$ ostale bi neobiđene tačke. Linija bi kasnije morala da pređe sa jedne strane te tetive na drugu nekom duži čiji su krajevi sa raznih strana, a takva duž seče tetivu $A_kX$ – to je samopresek.

Obrnuto, ako svaki put idemo u jednu od dve neobiđene tačke susedne luku (sa jednog ili drugog kraja), nova duž ostavlja sve obiđene tačke sa jedne, a sve neobiđene sa druge strane, pa ne seče ni prethodne ni kasnije duži. Primer za $n=4$ i tačke $1,2,3,4$ redom po krugu, sa početkom u $1 :$ dozvoljene su $1\text{-}2\text{-}3\text{-}4 ,$ $1\text{-}2\text{-}4\text{-}3 ,$ $1\text{-}4\text{-}3\text{-}2$ i $1\text{-}4\text{-}2\text{-}3 ,$ a npr. $1\text{-}3\text{-}2\text{-}4$ nije, jer se $13$ i $24$ seku.

Provera: za $n=3$ dobijamo $3$ linije (svaka izostavlja jednu stranicu trougla), a za $n=4$ dobijamo $4\cdot2=8$ linija.

Prema tome, takvih izlomljenih linija ima $n\cdot2^{n-3} .$