Here is a puzzle I found in Mitteilungen der DMV (roughly, "Letters of the German Society of Mathematicians"), issue 19/2011. It was posed by Alfred Schreiber in "Wie man Hasen fangt" (How to catch rabbits), and he claims that less than 5% of his subjects could solve it in under 1 hour. He tested it on students of mathematics and professors of mathematics, computer science, and engineering.
See if you have more luck. The problem is deceptively simple:
Suppose that you have a triangle $ABC$ and a point $D$ inside the triangle. Prove that the perimeter of $ABC$ is larger than the perimeter of $ABD$.
I am currently working on a generalization: Given two convex shapes $S$ and $T$, where $T$ totally encloses $S$. Prove that the perimeter of $S$ is no bigger than the perimeter of $T$.
Alternatively, for a shapes with straight edges: Prove that the perimeter of the convex hull of a set of points increases monotonically (but not strictly monotonically) as points are added to the set.
Please try to find an elementary proof for the special case of the triangle.
Edit: Thanks for all the nice answers. By now, I have found a really elementary proof on my own that just uses the triangle inequality twice.