Първата задача е класическа, накои от вас сигурно са я решавали. Ще помоля да не давате отговорът директно, за да може повече хора да й се порадват:
Задача 1. Даден е следният квадрат от 9 точки (тук с моя елементарен "ASCII art" не се получава точно квадрат, но...):
. . .
. . .
. . .
Свържете всички точки с точно 4 прави отсечки като използвате молив/химикалка, но без да имате право да си вдигате ръката от листа. Тоест трябва да свържете всички точки с начупена линия съставена от само четири отсечки.
След като се позабавлявате с тази - преминете към малко по-сложната:
Задача 2. Даден е крадрат от 16 точки:
. . . .
. . . .
. . . .
. . . .
Свържете всички точки с начупена линия съставена от точно 6 отсечки.
И след като свършите... преминете към дълбоките води:
Задача 3. Даден е квадрат от n*n на брой точки. Намерете минималният брой отсечки, с който може да свържете всички точки без да си вдигате ръката от листа.
По последната задача съм работил малко, признавам си безуспешно. Досега съм успял да докажа, че всеки квадрат от n*n на брой точки може да бъде покрит от 2*n-2 на брой отсечки. Но дали това е минимума?
Задача 1. Даден е следният квадрат от 9 точки (тук с моя елементарен "ASCII art" не се получава точно квадрат, но...):
. . .
. . .
. . .
Свържете всички точки с точно 4 прави отсечки като използвате молив/химикалка, но без да имате право да си вдигате ръката от листа. Тоест трябва да свържете всички точки с начупена линия съставена от само четири отсечки.
След като се позабавлявате с тази - преминете към малко по-сложната:
Задача 2. Даден е крадрат от 16 точки:
. . . .
. . . .
. . . .
. . . .
Свържете всички точки с начупена линия съставена от точно 6 отсечки.
И след като свършите... преминете към дълбоките води:
Задача 3. Даден е квадрат от n*n на брой точки. Намерете минималният брой отсечки, с който може да свържете всички точки без да си вдигате ръката от листа.
По последната задача съм работил малко, признавам си безуспешно. Досега съм успял да докажа, че всеки квадрат от n*n на брой точки може да бъде покрит от 2*n-2 на брой отсечки. Но дали това е минимума?
Коментар