Jump to content
BrainDen.com - Brain Teasers
  • 0

points in a plane


Go to solution Solved by BMAD,

Question

7 answers to this question

Recommended Posts

  • 0

Here's a quick response, that may be way off
 

Spoiler

Make a convex polygon out of (n-1) of the points, and put the nth point inside.

The perimeter comprises (n-1) edges. The "spokes" comprise another (n-1) edges.

So 2(n-1) is a lower bound.

Now modify the polygon, making it star-like and connect every other point, adding Floor [(n-1)/2] edges.

Final answer: Floor [5(n-1)/2] edges.

 

Link to post
Share on other sites
  • 0
On 3/16/2016 at 5:32 PM, bonanova said:

Here's a quick response, that may be way off
 

  Reveal hidden contents

Make a convex polygon out of (n-1) of the points, and put the nth point inside.

The perimeter comprises (n-1) edges. The "spokes" comprise another (n-1) edges.

So 2(n-1) is a lower bound.

Now modify the polygon, making it star-like and connect every other point, adding Floor [(n-1)/2] edges.

Final answer: Floor [5(n-1)/2] edges.

I played with your solution.  Is there a condition missing?  It doesn't seem to hold for small n.

 

Link to post
Share on other sites
  • 0

I think your formula is correct.

Spoiler

My formula is correct for 6 and 7 points, but is low for 8 and 9 points.
For 9 points, my formula says 20, but I get 21 edges.
For 8 points, my formula says 17 but I get 18.
Your formula correctly gives 21 and 18.

Do you have a proof?

Spoiler

A simple construction shows that adding a point to an already optimal layout always permits 3 additional edges.

 

Link to post
Share on other sites
  • 0
1 hour ago, bonanova said:
  Hide contents

 

Do you have a proof?

  Hide contents

A simple construction shows that adding a point to an already optimal layout always permits 3 additional edges.

In optimal (most edges being used) form, every new point after the fourth one will only add three edges. Making a chart of vertices to edges, one can see a linear relationship of vertices to edges (if you exclude the 1 & 2 vertices options).

 

Edited by BMAD
Grammar
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...