Наследил съм квадратно парче земя със страна 1. За да го предпазя от лошите очи на съседите, аз трябва да го оградя. Целта е:
1. съседски поглед да не може да премине през земята ми и
2. оградата да е с минимална дължина (за по-евтино).
Формата и броя на сегментите на оградата, както и това дали сегментите са свързани един с друг или не, е по мой избор (стига да може да се изчисли дължината на оградата).
Ако искаме да опишем проблема с мастило за втори клас, то можем да сменим "квадрат" с "изпъкнал многоъгълник". Но за момента това не е толкова толкова важно, затова илюстрациите ще са с квадрати.
а) горе вляво: d=4,
б) горе вдясно: d=3,
в) долу вляво: d≈2.73,
г) долу вдясно: d≈2.64.
Решението г) за момента се приема за оптимално, въпреки че това още не е доказано.
Лесно можем да забележим че в някои от решенията, ако се объркаме и останем в имота, то без да разваляме/прескачаме оградата нямаме път за навън (или пък пътят е неприятно дълъг). Затова нека да модифицираме проблема така:
Спазвайки изискванията да не разваляме оградата и да не я прескачаме, коя е минималната сума от дължините на: 1) оградата (черни линии) и 2) пътя от точката, максимално отдалечена от незаградена страна на имота, до същата страна (червени линии)?
Тук нещата са по-различни: сумарната дължина на черни и червени линии при вариант в) е по-къса от тази при вариант г). Съществува ли вариант с още по-малка сумарна дължима?