BMAD Posted January 28, 2015 Report Share Posted January 28, 2015 Given a finite set of polygons in the plane. Every two of them have a common point. Prove that there exists a straight line, that crosses all the polygons. 2 1 Quote Link to comment Share on other sites More sharing options...
0 k-man Posted January 30, 2015 Report Share Posted January 30, 2015 Using the interpretation of "crossing" as "having a common point with"... More specifically, at least one straight line in every direction. Let's draw a random straight line on the plane containing the polygons. Every one of the polygons with respect to that line is either 1) crossed by the line 2) lays entirely in one of the half-planes formed by the line - i.e. not crossed by the line. Since every pair of polygons has at least one common point, all polygons that are not crossed by the line must be in the same half-plane. Find the polygon that is the farthest away from the line (call it P) and find the point on P that is the closest to the line (call it A). Draw another straight line through point A parallel to the first line. This new line crosses every polygon. By construction, the line "touches" polygon P, so aside from the point A (and potentially other common points), P lays entirely in one half-plane formed by the line. There cannot be any polygons that lay entirely in the same half-plane as P and not cross the line because any such polygon would be further away from the original line, but P was picked as the farthest polygon. There cannot be any polygons that lay entirely in the other half-plane either because they would not have any common points with P. 1 Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted January 28, 2015 Report Share Posted January 28, 2015 Even though the four quadrants of Cartesian space have the origin in common, that is, every pair has the origin in common, no line passes through them all. If they must be finite in size, truncate them with |x|<1 and |y|<1. Quote Link to comment Share on other sites More sharing options...
0 Perhaps check it again Posted January 28, 2015 Report Share Posted January 28, 2015 I claim it's not true, and I show it with a counterexample. In the xy-plane, let the following points be labelled as such: A = (0, 1) B = (1, 1) C = (-1, 0) D = (0, 0) E = (1, 0) F = (0, -1) Triangle ABE shares point A with triangle ACD. Triangle ACD shares point D with triangle EDF. Triangle ABE shares point E with triangle EDF. No line can pass through all the interiors of the three triangles. 1 1 Quote Link to comment Share on other sites More sharing options...
0 BMAD Posted January 30, 2015 Author Report Share Posted January 30, 2015 (edited) Why cant a line pass through ABE and the common point of ACD and EDF? Edited January 30, 2015 by BMAD 1 1 Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted January 30, 2015 Report Share Posted January 30, 2015 Probably there are different interpretation of "crossing." In particular, when the endpoint of one line segment belongs to the other line segment. For example, does the line segment {(0,0), (1,0)} "cross" or "intersect" the y-axis? I looked at a number of sites by Googling "line segments that intersect." The consensus seems to be: yes, they do intersect. Given that interpretation my post, at least, does not provide a counterexample, and BMAD's question remains unanswered. Quote Link to comment Share on other sites More sharing options...
0 Perhaps check it again Posted January 30, 2015 Report Share Posted January 30, 2015 I stated "No line can pass through all the interiors of the the three triangles." BMD, you stated "Why cant [sic] a line pass through [triangle] ABE and the common point of [triangles] ACD and EDF?" In my attempt to work on the problem, I misunderstood "crossing a polygon" from the original post and changed the subject. But, with you asking me that question (in the quotes just above), you changed the subject. I never addressed/denied that situation. It's not a line passing through the interiors of three triangles anyway. 2 Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted January 31, 2015 Report Share Posted January 31, 2015 @Perhaps check it again I thought of that distinction as well, and it led me back to the OP, where I found that the word "interior" is not mentioned. It has been agreed that a line cannot always pass through the interior of polygons so described. It has been clarified that BMAD asks something different. Not all Denizens share English as their primary language, so discussions like this one are generally helpful if taken in that regard. 1 Quote Link to comment Share on other sites More sharing options...
0 BMAD Posted February 1, 2015 Author Report Share Posted February 1, 2015 thank you bonanova 1 1 Quote Link to comment Share on other sites More sharing options...
0 gavinksong Posted February 9, 2015 Report Share Posted February 9, 2015 BMAD, I like this series of puzzles you've posted. Do you come up with them yourself, or did you get them from somewhere? Quote Link to comment Share on other sites More sharing options...
0 BMAD Posted February 10, 2015 Author Report Share Posted February 10, 2015 BMAD, I like this series of puzzles you've posted. Do you come up with them yourself, or did you get them from somewhere? Both. This one though is from the former Soviet union puzzle challenges. Quote Link to comment Share on other sites More sharing options...
0 gavinksong Posted February 10, 2015 Report Share Posted February 10, 2015 Using the interpretation of "crossing" as "having a common point with"... More specifically, at least one straight line in every direction. Let's draw a random straight line on the plane containing the polygons. Every one of the polygons with respect to that line is either 1) crossed by the line 2) lays entirely in one of the half-planes formed by the line - i.e. not crossed by the line. Since every pair of polygons has at least one common point, all polygons that are not crossed by the line must be in the same half-plane. Find the polygon that is the farthest away from the line (call it P) and find the point on P that is the closest to the line (call it A). Draw another straight line through point A parallel to the first line. This new line crosses every polygon. By construction, the line "touches" polygon P, so aside from the point A (and potentially other common points), P lays entirely in one half-plane formed by the line. There cannot be any polygons that lay entirely in the same half-plane as P and not cross the line because any such polygon would be further away from the original line, but P was picked as the farthest polygon. There cannot be any polygons that lay entirely in the other half-plane either because they would not have any common points with P. k-man always has such elegant solutions to these problems. I'm sorry but I couldn't contain myself. Quote Link to comment Share on other sites More sharing options...
0 k-man Posted February 10, 2015 Report Share Posted February 10, 2015 Using the interpretation of "crossing" as "having a common point with"... More specifically, at least one straight line in every direction. Let's draw a random straight line on the plane containing the polygons. Every one of the polygons with respect to that line is either 1) crossed by the line 2) lays entirely in one of the half-planes formed by the line - i.e. not crossed by the line. Since every pair of polygons has at least one common point, all polygons that are not crossed by the line must be in the same half-plane. Find the polygon that is the farthest away from the line (call it P) and find the point on P that is the closest to the line (call it A). Draw another straight line through point A parallel to the first line. This new line crosses every polygon. By construction, the line "touches" polygon P, so aside from the point A (and potentially other common points), P lays entirely in one half-plane formed by the line. There cannot be any polygons that lay entirely in the same half-plane as P and not cross the line because any such polygon would be further away from the original line, but P was picked as the farthest polygon. There cannot be any polygons that lay entirely in the other half-plane either because they would not have any common points with P. k-man always has such elegant solutions to these problems. I'm sorry but I couldn't contain myself. Thanks, gavinksong, but the real credit should be given to BMAD for posting these great puzzles. 1 Quote Link to comment Share on other sites More sharing options...
Question
BMAD
Link to comment
Share on other sites
12 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.