## 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?

Share:

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.

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:

Explanation??

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