Wednesday, December 20, 2006

Strikethrough. Topic: Geometry/NT. Level: AIME.

Problem: (Stanford Putnam Practice) Let $ P_1, P_2, \ldots , P_{2007} $ be distinct points in the plane. Connect the points with the line segments $ P_1P_2, P_2P_3, \ldots, P_{2006}P_{2007}, P_{2007}P_1 $. Can one draw a line that passes through the interior of every one of these segments?

Solution: Playing around with pictures for a while, our intuition says that since $ 2007 $ is odd, this is impossible. Now let's try to prove it. Suppose there exists such a line $ l $. Then we know that the endpoints of each line segment lie on opposite sides of the line. So

$ P_1 $ and $ P_2 $ lie on opposite sides of $ l $;

$ P_2 $ and $ P_3 $ lie on opposite sides of $ l $;

$ \cdots $

$ P_{2007} $ and $ P_1 $ lie on opposite sides of $ l $.

But wait, by a simple induction we know that $ P_1, P_3, P_5, \ldots, P_{2007} $ lie on the same side. That gives us the contradiction we seek. Thus $ l $ does not exist, as desired. QED.


Comment: Not a bad problem, though pretty simple after you realized that you could fix the line before the points. It's easy to see that this generalizes to any set of an odd number of points (try the sides of a triangle, for example), so we have proven in fact a decently strong result.


Practice Problem: (Stanford Putnam Practice) Show that if every room in a house has an even number of doors, then the number of outside entrance doors must be even as well.


  1. WOW,
    so, i was looking at stanford's putnam problems,
    take a look problem # 6 on November 15. Handout of problems.
    it is really suprising!

    oh, and by the way, Sirjani told me today, you guys need to send your registration stuff to her for the eastlake contest (cause she's ordering trophies).

  2. oh that is putnam04 handouts btw.

  3. The registration should have been mailed about a week ago.