Jump to content
BrainDen.com - Brain Teasers
  • 0
BMAD

Polygons make a line

Question

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.
  • Upvote 2
  • Downvote 1

Share this post


Link to post
Share on other sites

12 answers to this question

Recommended Posts

  • 0

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.

 

  • Upvote 1

Share this post


Link to post
Share on other sites
  • 0

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.

Share this post


Link to post
Share on other sites
  • 0

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.

  • Upvote 1
  • Downvote 1

Share this post


Link to post
Share on other sites
  • 0

Why cant a line pass through ABE and the common point of ACD and EDF?

Edited by BMAD
  • Upvote 1
  • Downvote 1

Share this post


Link to post
Share on other sites
  • 0

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.

Share this post


Link to post
Share on other sites
  • 0

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.
 

  • Downvote 2

Share this post


Link to post
Share on other sites
  • 0

@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.

  • Upvote 1

Share this post


Link to post
Share on other sites
  • 0

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.

Share this post


Link to post
Share on other sites
  • 0

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.

Share this post


Link to post
Share on other sites
  • 0

 

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.

  • Upvote 1

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...