3
$\begingroup$

I know I am missing something in this problem, but I don't know what:

Let $P_1, P_2, ..., P_{1997}$ be distinct points in the plane. Connect the points with the line segments $P_1P_2, P_2P_3, P_3P_4, ..., P_{1996}P_{1997}, P_{1997}P_{1}$. Can one draw a line that passes through the interior of every one of these segments?

According to how I understand the problem, the solution is easy. It's clearly not possible to have one line pass through every line segment in this picture.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ So you have shown that it is not always possible. could it be sometimes possible? $\endgroup$ – Hagen von Eitzen Jul 6 '17 at 18:51
  • $\begingroup$ Are you interpreting the question incorrectly or am I? 'Can one draw a line that passes through the interior of every one of these segments?' - I'd take that to mean the area inside. $\endgroup$ – Shuri2060 Jul 6 '17 at 18:55
  • 1
    $\begingroup$ @Shuri2060 I think I was wrong. Possibility should depend on the parity of the number of points, and i don't think it works for an odd number... $\endgroup$ – Frpzzd Jul 6 '17 at 19:02
  • 1
    $\begingroup$ @HagenvonEitzen Ah okay, so I guess the problem could be reformulated as "find neccesary and sufficient (or at least sufficient) conditions such that it is possible"? $\endgroup$ – Ovi Jul 6 '17 at 19:13
  • 1
    $\begingroup$ @Ovi the better statement of the problem would be: Can you distribute 1997 points on the plane such that if one connects $P_iP_{i+1}$ and $P_{1997}P_1$ then there exists a line crossing each open (meaning the points excluded) segment. I suggest you start with three points instead of 1997... $\endgroup$ – Hamed Jul 6 '17 at 20:50
5
$\begingroup$

Consider such a collection of points ${<}P_i{>}$ as described with $N$ points.

Now let us assume that a line can be drawn crossing each of the line segments ${<}L_i{>}$ where $L_N$ connects $P_N$ and $P_{1}$ and all other $L_i$ connect $P_i$ and $P_{i+1}$.

Now we know that if $P_i$ is one one side of the line, $P_{i+1}$ is on the other side of the line, and $P_1$ and $P_N$ are on opposite sides of the line. We can thus infer that $N$ is even, since all odd points are on the same side of the line as $P_1$.

Thus when such a line can be drawn, $N$ must be even, and by contrapositive, if $N$ is odd, such a line cannot be drawn.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.