Line splitting

[bonanova]

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.

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.

[superprismatic]

AGICEJFBHD

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

[CaptainEd]

It's been a long time. Here's a recharacterization that recognizes a much smaller search space:

Overview

 

I think we all believe that there is no sequence A1-A18 that satisfies the conditions of the challenge.
Bonanova has produced a sequence up to A17. I'll start backward from that solution, demonstrating why it didn't work, and backing up in hopes of demonstrating that there cannot be any solution. I hope that this will answer Bonanova's concern that it isn't clear why a solution can't be found. A complete backtracking solution may be convincing, but it won't feel like it explains "why not".I hope this analysis will give sufficient insight to give a good feeling of "why not". Actually, at the tinme of this writing, I haven't even backtracked all the way, so I haven't yet proved there is no solution.  Still, with the help of the M matrix described below, a person or robot may be able to find a solution or exhaust the search space.

Definitions and additional constraint

 

First, define the ith j-bin as the range from 
 ( (i-1)/j to i/j ]
the endpoint is included, not the beginning point. Note that i is 1-origin. That is, the first j-bin is the "1" j-bin, the last j-bin is the "j" j-bin.

Next, list all the bin endpoints for all divisors from 1 to 18, sort the list in increasing order, and then coalesce identical values (e.g. 1/4 = 2/8 = 3/12 all become one item)
Define this list as M, the list of "mini-bins" endpoints. The i-th minibin is the range (M(i-1),M(i)], once again including the endpoint, but not the starting point. 

Each bin is an equivalence class: two numbers in the same mini-bin are in the same bin as each other for every divisor; but two numbers in different mini-bins are in a different bin for at least one divisor.

So our task in choosing numbers is reduced to identifying minibins. There are only 101 of them to choose from. We'll identify each mini-bin with its endpoint.

Next, we can recognize additional constraints posed by the problem conditions. We know that the goal is to identify a sequence A of numbers (selected from M) where the first j numbers must each lie in different j-bins, for 1 <= j <= 18.

An additional constraint is a consequence of this: if i<j, the i-th and j-th elements of A must be in different k-bins for all k >= j. So, when we're picking the j-th item of A, we have to look backward (to make sure all past items are in different j-bins), and we have to look forward as well (to make sure these j numbers wind up in different k-bins for all higher k).

This observation greatly reduces the search space in practical terms.

 

LineSplittingMValues.xlsx

BonanovaSequence.xlsx

Edited January 3, 2018 by CaptainEd
messed up spoilers again

[curr3nt]

DHAFBEGC

-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 August 17, 2012 by curr3nt

[bonanova]

DHAFBEGC

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

[bonanova]

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?

[phil1882]

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.

[phil1882]

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.

[bonanova]

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.

[bonanova]

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.

[CaptainEd]

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

[CaptainEd]

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

[CaptainEd]

It's been a while, and I have no more clue, but...I'm guessing that when we want to make an 18th number, there must already be an 18th that contains two numbers. I can't prove that, but I'm wondering whether the overall problem is experienced in this version:

( a ) pick 9 numbers, so that each 9th is populated

( b ) pick 7 more numbers, so that each 16th is populated

( c ) pick 1 more number, so that each 17th is populated

( d ) pick 1 more number, so that each 18th is populated--can we experience the same apparent impossibility as before?