C, PHP, VB, .NET

Помните ли задачата за 9-те точки? Ето ви същата задача, но направена с 16 точки:

 
. . . .

. . . .

. . . .

. . . .
 

Свържете всички точки с шест прави отсечки без да си вдигате ръката и без да повтаряте. Предполагам, че този път няма да има проблем да се справите, но на тези, които не са решавали задачата с 9-те точки, препоръчвам да потърсят решението сами преди да гледат отговорите в предишната задача.

Решенията можете да ги дадете като картинки и да ги качите на някой хостинг за картинки. Предполагам, че рисуването с ASCII код (както обичам да „рисувам“ аз) няма да излезе добре в коментарите. Коментарите ще бъдат модерирани за определено време, за да може всички желаещи да решат задачата (не, че ще са много де) да се опитат без да гледат готови решения.

За най-напредналите измислих нещо по-интересно, което признавам си просто ми хрумна и още не съм му намерил решение (ако има такова де, но има всички предпоставки да има). В задачата за 9-те точки имахме квадрат с размери 3×3. В тази задача имаме квадрат с размери 4×4. Нека числото „n“ е размерността страната на квадрата. Знаем, че при n=3 минималният брой отсечки, с които можем да свържем точките е k=4. От тази задача пък вече знаем, че при n=4 минималният брой отсечки, които свързват точките е k=6.

Новата задача е: можем ли да открием формула, която за всяко n>2 намира минималният брой отсечки k, които свързват всички точки в такъв квадрат със страна от n точки (без да си вдигаме ръката и да повтаряме)? С други думи ако знаем, че F(n) = k, то намерете F=?