Задача: Група програмисти се събират и решават да се напият възможно най-бързо. Как да свърши наздравицата най-бързо, като се „чукнат“ всеки с всеки от присъстващите, със следните уточнения:
– всички порции наздравици се извършват едновременно;
– масата е окръжност, а феновете са точки по нея;
– наздравицата е отсечка между две точки, като по същото време не може да има друга такава отсечка, която да я пресича: няма преплитане на ръце;
– броя на точките (фенове) е n.
Всъщност, това е сериозен проблем, примерно при дизайн на платки, когато без късо съединение (нежелано пресичане) трябва да се определят броя нива на платката. Важно е да споменем, че един програмист може да извършва само една наздравица в даден момент (иначе задачата е тривиална, защото на първи етап всички програмисти се чукват с No. 1, после с No. 2 и така виждаме, че броят е n; ако свързваме всеки път съседните, т.е. при връзки 1-2, 1-3, 1-4, …, 1-n можем да създадем и връзки 2-3, 3-4, 4-5, 5-6, … ще си спестим една наздравица, така че броят е де факто n-1, което е оптималното решение).
И тъй, за другия случай:
Разцъках си решенията за n=4, 6, 8 (после ще обясня защо само на четните).
n=4
n=6
От тук нататък правим следният анализ…
За всяко четно n е достатъчно да направим връзки без свободни елементи (всички възли са свързани) и по главния диагонал (остават по 2 несвързани възела).
Общият брой е винаги n и това решение е оптимално.
Когато имаме нечетен брой елементи, обаче, един елемент винаги остава свободен, за който трябва да изпълним тези комбинации. Тогава ще имаме n.(n-1) етапа на наздравица.
Накратко:
- ако програмист може да вдигне наздравица с няколко програмиста едновременно: n-1
- ако програмист може да вдигне наздравица само с един човек при четно n: n
- ако програмист може да вдигне наздравица само с един човек при нечетно n: n.(n-1)