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, professors of mathematics, computer science and engineering.
See if you have more luck. The problem is deceptively simple:
Suppose you have a triangle ABC and a point D inside the triangle. Prove: The perimeter of ABC is smaller than the circumference of ABD.
I am currently working on a generalization: Given two convex shapes s and S, where S totally encloses s. Proof that the perimeter of s is no bigger than the perimeter of S.
(Or alternatively, for a shapes with straight edges: Proof that the perimeter of the convex hull of a set of points increases monotonically (but not strictly monotonically) when adding points 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 found a really elementary proof on my own that just uses the triangle inequality twice.