From:matthew@lynn.cs.ucla.eduNewsgroups:rec.puzzlesSubject:splitting the hairDate:11 Sep 90 20:02:01 GMTReply-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