Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
* * * * * 1 votes

Line splitting


  • Please log in to reply
10 replies to this topic

#1 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5776 posts
  • Gender:Male
  • Location:New York

Posted 17 August 2012 - 04:47 AM

Draw a line segment, and place a point on it anywhere you like. Now place another point, but be sure the two points are in opposite halves of the line segment. Continue by adding a third point, but make sure they all are in different thirds of the line segment. And so on. After placing eight points you'd have something that looks like this.

steinhaus.gif

Here are eight points, each in a different eighth of the segment. But in what order were they placed, and in what part of the 8 intervals must they lie in order for each successive group of points to have comprised a legal arrangement? It may seem a trivial task: it's certainly trivial to describe.

Have a go at it, with some graph paper or a calculator, and see how many points you can place.

Let's standardize the problem as follows: Define the line segment as the number interval [0, 1000], and give your answers as integers. For example, for the pretty easy case of four points you might get {200, 800, 450, 700}. And so on. Have fun. ;)
  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#2 curr3nt

curr3nt

    The

  • Members
  • PipPipPipPip
  • 2839 posts
  • Gender:Male
  • Location:in a field of spatulas...

Posted 17 August 2012 - 02:26 PM

Spoiler for I think this works...

Edited by curr3nt, 17 August 2012 - 02:33 PM.

  • 0

#3 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5776 posts
  • Gender:Male
  • Location:New York

Posted 17 August 2012 - 06:08 PM

Spoiler for I think this works...


Great!
Curr3nt has solved for 8 points.

The bar is now raised to 10 points.
The interval [0, 2520] gives integer boundaries for 1-10 divisions.
  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#4 superprismatic

superprismatic

    Not just Prismatic

  • Moderator
  • PipPipPipPip
  • 1281 posts
  • Gender:Male

Posted 17 August 2012 - 07:52 PM

Spoiler for The order I get is

Spoiler for My line segment was the unit interval and my picks, in order, were

  • 0

#5 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5776 posts
  • Gender:Male
  • Location:New York

Posted 18 August 2012 - 03:56 AM

Spoiler for The order I get is

Spoiler for My line segment was the unit interval and my picks, in order, were


A new BD record!

The process can continue. For example, fourteen points are possible.
But there is a limit, after which it's not possible to continue.

Is there an intuitive proof/reason why there would be an upper limit?
If you have a program to place N points, can you verify the limit is 17?
  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#6 phil1882

phil1882

    Senior Member

  • Members
  • PipPipPipPip
  • 537 posts

Posted 19 August 2012 - 06:48 PM

Spoiler for 18?

  • 0

#7 phil1882

phil1882

    Senior Member

  • Members
  • PipPipPipPip
  • 537 posts

Posted 19 August 2012 - 08:08 PM

hmm my above logic doesn't seem quite right, i'm sure something is off there; you should need to go at least 2 layers to find a contradiction.
  • 0

#8 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5776 posts
  • Gender:Male
  • Location:New York

Posted 19 August 2012 - 08:13 PM

Spoiler for 18?


Nice approach.
I had thought of constructing a set of stepwise overlapping regions to visually find back paths, but it got complicated.

  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#9 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5776 posts
  • Gender:Male
  • Location:New York

Posted 20 August 2012 - 09:55 AM

Spoiler for Here is the solution for 17 points

  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#10 CaptainEd

CaptainEd

    Senior Member

  • Members
  • PipPipPipPip
  • 1094 posts

Posted 21 August 2012 - 03:47 PM

Here's a slightly reduced form of the problem, does it shed light on the impossibility of 18?

Make the partitions of size 1, 2, 3, 6, 9, 12, and 18.
That is, place the first three points as before; place points 4, 5, and 6 in a way so that the six points are in separate 6ths of the line, place points 7,8,9 so that the 9 points are in separate 9ths; place 10, 11, 12 so that the 12 points are in separate 12ths, and place the last 6 so that the 18 fit into separate 18ths.

In other words, remove the constraints on placements 4,5,7,8,10,11, 13, 14, 15, 16, and 17
  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users