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

Nconvex 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 *2*log_{2}*N* intersections?

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

19 October 2008, 8:27 am## 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)

10 March 2010, 6:20 pm## Pratik Poddar:

Explanation??

25 April 2010, 2:12 am## dEmigOd:

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

9 April 2014, 5:42 am| | | | |

| | |—–|

| | | |

| |———–|

| | |

| | |

| | |

| | |

———————–