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:
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 amAaditya:
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 pmPratik Poddar:
Explanation??
25 April 2010, 2:12 amdEmigOd:
|———|—–|–|–|
9 April 2014, 5:42 am| | | | |
| | |—–|
| | | |
| |———–|
| | |
| | |
| | |
| | |
———————–