A solitaire game is played with the following rules:
________________

On a line segment (of arbitrary length, set it as long as you wish, but for convenience/reference sake, let's say it extends from 0 to 1 on the number line), you place a point anywhere you like on it.

Now place a second point, such that either of the two points is within a different half of the line segment. (The halves are taken to be "open intervals", which means that the end points are not considered "inside" the interval.)

Place a third point so that each of the three is in a different third of the line.

At this point, you may notice that the first two points can't be just anywhere. They cannot, for example, be close together in the middle of the line or close together at one end. They must be carefully placed so that when the third point is added, each will be in a different third of the line.

You proceed in this way, placing every nth point so that the first n points always occupy different 1/nth parts of the line.
_________________

If you choose locations carefully, how many points can you put on the line?

(In reply to re: Solution by SilverKnight)

Ok, here is the program I used. It is written in Ruby (www.ruby-lang.org).
It doesn't print out the solution as points but rather as ranges in which to place the points.

To answer you second questions: Either the algorithm I used is flawed or there simply isn't any solution with more than 17 points. I'm personally in favour of the latter hypothesis, but feel free to prove me wrong ;)


require 'rational'

class Rational
  def inspect
    "%d/%d" % [@numerator, @denominator]
  end
end

def rec(ranges, solution)
  level = ranges.size
  
  if level == 1
    p ranges + solution
    throw :found
  end
  
  step = Rational(1, level)
  right = 0
  ranges.map! do |range|
    left = right
    right += step
    return if left >= range.end || right <= range.begin
    ([left, range.begin].max)..([right, range.end].min)
  end
  
  next_ranges = []
  until ranges.empty?
    cur_range = ranges.shift
    rec(next_ranges + ranges, [cur_range] + solution)
    next_ranges << cur_range
  end
end

for level in 2..18
  printf \"Level: %d\n\", level
  catch :found do
    rec([Rational(0, 1)..Rational(1, 1)] * level, [])
  end
end

Posted by exoticorn on 2004-01-18 06:36:27