• 0
Sign in to follow this  
Followers 0

Line splitting

Question

Posted · Report post

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.

post-1048-0-31377300-1345174158_thumb.gi

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

Share this post


Link to post
Share on other sites

10 answers to this question

  • 0

Posted (edited) · Report post

DHAFBEGC

post-39441-0-94867300-1345209945_thumb.j

-edit-

Haha... I really should read the entire post before trying to solve.

Using 1 to 840 range:

1 - 355

2 - 835

3 - 5

4 - 565

5 - 175

6 - 425

7 - 675

8 - 245

Edited by curr3nt
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

DHAFBEGC

post-39441-0-94867300-1345209945_thumb.j

-edit-

Haha... I really should read the entire post before trying to solve.

Using 1 to 840 range:

1 - 355

2 - 835

3 - 5

4 - 565

5 - 175

6 - 425

7 - 675

8 - 245

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

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

AGICEJFBHD

0.08904, 0.63791, 0.82876, 0.28520, 0.42099, 0.93505, 0.50702, 0.13581, 0.71495, 0.38213

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

AGICEJFBHD

0.08904, 0.63791, 0.82876, 0.28520, 0.42099, 0.93505, 0.50702, 0.13581, 0.71495, 0.38213

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

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

i think it is actually easier to work backward rather than forward.

so let's say there are 18 points along the unit line. to get to 17 we need to eliminate 1 point such that the remaining 17 points lie in each of the 17 sections. the most logical point to eliminate would be one of the two middle most points, out of

ABCDEFGHIJKLMNOPQR

either I or J . let's try I.

this eliminates the range of points between 9/18 and 10/18.

thus for 17, H needs to be between 8/17 and 9/18, and J needs to be between 10/18 and 10/17. however, there's now no way to place a point between 9/17 and 10/17, a requirement for the puzzle.

if we try J instead, this eliminates the range of points between 10/18 and 11/18.

I - 9/17 to 10/18; K - 11/18 to 11/17

and again, we reach a result that is not feasible. for completeness we should try every point, but I'll leave that exercise to the reader.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

i think it is actually easier to work backward rather than forward.

so let's say there are 18 points along the unit line. to get to 17 we need to eliminate 1 point such that the remaining 17 points lie in each of the 17 sections. the most logical point to eliminate would be one of the two middle most points, out of

ABCDEFGHIJKLMNOPQR

either I or J . let's try I.

this eliminates the range of points between 9/18 and 10/18.

thus for 17, H needs to be between 8/17 and 9/18, and J needs to be between 10/18 and 10/17. however, there's now no way to place a point between 9/17 and 10/17, a requirement for the puzzle.

if we try J instead, this eliminates the range of points between 10/18 and 11/18.

I - 9/17 to 10/18; K - 11/18 to 11/17

and again, we reach a result that is not feasible. for completeness we should try every point, but I'll leave that exercise to the reader.

Nice approach.

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

I do not have a good understanding of why there is an upper limit.

Expressed as percentages of a unit line segment:

71 9 42 85 27 54 92.5 17 62 35.5 78 3 48 97 22 66 32.

Follow the yellow lines down from the top.

As far the lines extend, they are in different divisions.

The top line has 17 divisions.

post-1048-0-85877600-1345452623_thumb.gi

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

False alarm, sorry. It's easy to do what I suggested. There is no light shed on the overall problem. Move along, folks, there's nothing to see here...

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0

  • Recently Browsing   0 members

    No registered users viewing this page.