From:           matthew@lynn.cs.ucla.edu
Newsgroups:     rec.puzzles
Subject:        splitting the hair
Date:           11 Sep 90 20:02:01 GMT
Reply-To:       matthew@CS.UCLA.EDU (Matthew Merzbacher)
Organization:   UCLA

I was looking through the "puzzles" section of a used bookstore and
I found a book that looked kind of interesting.  Sure, it had the usual
suspects (e.g. Towers of Hanoi), but it also had one puzzle which I'd never
seen before.  I bought the book (for a buck) and read it through.  As it
turns out, it's an awful book, but this one puzzle intrigues me.

The book is awful because the puzzles are poorly described (as if someone had
taken a month worth of the net and published it without editorial change)
and the answers aren't always the clearest or most elegant solutions.

I would cite the book, but I don't have it here.  Nonetheless, here's the puzzle
(hopefully described more clearly than in the book):

Suppose you have a line segment (it can be of unit length, if you want - that
doesn't really matter).  Now you are going to play a little game:

1. Place a point (anywhere) on the segment and mark it #1
2. Divide the segment into two even pieces (at 1/2).  Now, unless you've chosen
   0.5 for your first point, that point is in one of the two sides of the
   segment.  Put another point (let's call it #2) anywhere in the other side.
3. Now, divide the original segment into three equal pieces.   If you're lucky, 
   #1 and #2 are in different sub-segments.  Add a third point (#3) anywhere in 
   the third segment.
4. Now, divide the segment into 4 equal sub-segments...

Once a point has been placed, you can't move it.
Repeat this exercise until two points end up in the same sub-segment.  That's
when you lose.  What is the maximum number of points you can put on the line?

Example:

|--1--------------------|

|--1--------.---------2-|

|--1----.--3----.-----2-|

|--1--.----3.----4.---2-|

|--1-.---5.3---.-4--.-2-|  (OK, it's hard to divide 24/5 in ASCII)

|--1.---.5-3.---.4---.2-|

Now we're stuck because #5 and #3 are in the same sub-segment and there are
two empty sub-segments where #6 needs to go.

The book claims that 17 (I think) is THOUGHT to be the highest attainable 
number of points.  This seems to be imminently discernable using standard
search techniques (and a fast machine).  Am I right?

What's the poop?  Any pointers.
 -- MM

Matthew Merzbacher	ARPA:	matthew@CS.UCLA.EDU
Moo - Moo Moo  		UUCP:	...!{uunet|rutgers|ucbvax}!cs.ucla.edu!matthew
               		BONENET:	...!tibia%pelvis!matthew@jawbone