The following example is described in The Man Who Loved Only Numbers by Paul Hoffman.
There is a reasonably short proof, found by Esther Klein (later Szekeres) in 1932, that given 5 points in the plane, there exist 4 of them that form a convex quadrilateral. The minimum number of points needed such that there always exists 5-element subset forming a convex pentagon is 9. There is a conjecture that the minimum number of points needed such that there exists an $n$-element subset forming a convex $n$-gon is $2^{n-2} + 1$. It is known it has to be at least that. This is called the "Happy Ending Problem" (apparently because George Szekeres had impressed Esther so much with his proof that there is a minimum finite number for each $n$ that he won her hand in marriage).
For the case $n = 6$, the best that Erdős achieved was 71 points, a somewhat distant cry from the conjectured 17. This was sometime in the 1930's. After the memorial service for Erdős in 1996, Ronald Graham and his wife Fan Chung thought it was high time that someone have another crack at it, after 60 years -- and were very excited that during a long flight to New Zealand, they managed to lower it down by just a single point, to 70. This required introducing new ideas.
(As Graham explains, Kleitman and Pachner soon lowered it further to 65. There were subsequent further improvements until finally George Szekeres and his collaborator Peters reached 17, with the help of computers, in a paper published in 2006.)