David Bernstein gave me this puzzle. He says that the puzzle was given at a Moscow math Olympiad a long time ago. At that time there were no computer science olympiads yet. I do not know why this puzzle feels to me like computer science. Maybe because the trivial solution is of order N, the easy solution is of order square root of N and the requested solution is of order logarithm of N:
Can you cut a square into N convex pieces minimizing the number of possible intersections of any straight line with your pieces?
It is easy to maximize the number of intersections. If you cut your square with N-1 parallel cuts into N equal thin rectangles, then there exists a line with N intersections.
It is easy to cut a square to guarantee no more than 2√N intersections. Can you cut your square so that any line makes no more than 2log2N intersections?Share: