A Math Puzzle that Sounds like a Computer Science Puzzle

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?



  1. Misha:

    Let’s see, n lines with no pair of parallels among them divides the plane into 2^n parts. It looks like no line can hit the interiors of more than n+1 parts.

  2. Aaditya:

    n lines with no parallels divide the plane into some (n^2 + n + 2) parts, and any newer line will hit n+1 regions at max. I don’t see a better solution. (2^n is wrong, misha)

  3. Pratik Poddar:


  4. dEmigOd:

    | | | | |
    | | |—–|
    | | | |
    | |———–|
    | | |
    | | |
    | | |
    | | |

Leave a comment