BMAD 64 Report post 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 Share this post Link to post Share on other sites
0 k-man 26 Report post 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 Share this post Link to post Share on other sites
0 bonanova 83 Report post 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 Share this post Link to post Share on other sites
0 Perhaps check it again 22 Report post 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 Share this post Link to post Share on other sites
0 BMAD 64 Report post 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 Share this post Link to post Share on other sites
0 bonanova 83 Report post 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 Share this post Link to post Share on other sites
0 Perhaps check it again 22 Report post 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 Share this post Link to post Share on other sites
0 bonanova 83 Report post 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 Share this post Link to post Share on other sites
0 BMAD 64 Report post Posted February 1, 2015 thank you bonanova 1 1 Quote Share this post Link to post Share on other sites
0 gavinksong 11 Report post 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 Share this post Link to post Share on other sites
0 BMAD 64 Report post 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 Share this post Link to post Share on other sites
0 gavinksong 11 Report post 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 Share this post Link to post Share on other sites
0 k-man 26 Report post 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 Share this post Link to post Share on other sites
Share this post
Link to post
Share on other sites