Suppose $n$ items are in a circle. What is the maximal cycle length that goes through all of the items. Length between 2 points is measured according to the shorter arc on the circle.
I solved the problem for odd $n$ (it's $\frac{n(n-1)}{2}$). For even $n$ I proved lower bound of $\frac{n^2}{2}-n+2$.
here's an example for $n=12$ (this construction generalized is how I showed the bound):
In other words I ask why I can't build a better example.
Let $C$ be a valid cycle. We're going to find an upper bound to $length(C)$.
Cycle $C'$ is formed by visiting every 2nd vertex of $C$.
Now consider the $\frac{n}{2}$ triangles formed by each edge of $C'$ and the corresponding skipped point.
The edges of edges of $C$ and $C'$ are exactly covered by the $\frac{n}{2}$ triangles. So, $$ length(C) + length(C') = \sum{\text{triangle perimeter}}\tag{1} $$ A triangle has a maximum perimeter of $n$. So, $$ \sum{\text{triangle perimeter}}\le\frac{n}{2}\cdot n\tag{2} $$ $C'$ has $\frac{n}{2}$ vertices, so two of those vertices must be at least $\frac{n}{2}-1$ apart. So, $$ length(C')\ge (\frac{n}{2}-1)\cdot 2\tag{3} $$ Combining these formulas gives $$ length(C)\le\frac{n^2}{2}-n+2\tag{4} $$
My thought process
I worked with $n=12$, like in the example. I found it easier to grasp the problem by changing edge costs to $\frac{n}{2}-distance$ and then minimizing the total cost.
Now, moving to the opposite vertex costs $0$, and we want to prove the total cost will be at least $10$.
In the example, the path $0$-$6$-$1$-$7$-$2$-$8$...$5$-$11$-$0$ has costs $0$, $1$, $0$, $1$, ..., $0$, $5$. At some point I drew a line from $0$ to $1$ to visualize the $1$ cost of $0$-$6$-$1$. Then a line from $1$ to $2$ to visualize the $1$ cost of $1$-$7$-$2$. I repeated this, and happily the drawing the line from $5$ to $0$ also made sense to show the $5$ cost of $5$-$11$-$0$. So, basically, I stumbled into drawing $C'$ and realized that it neatly ties everything together.