See here for an easier right bound : http://www.mathlinks.ro/viewtopic.php?search_id=373672023&t=26382

A sketch for a solution: The lower bound is trivial, we can easily construct an example(see here). Now, observing the upper bound, we know trivially that $ f(1)=1$, so the upper bound holds for $ n=1$. We prove the proposition for $ P$ a rectangle (rather than a square), and we say that a partition of $ P$ has property $ n$ if it satisfies the conditions given in the problem. Claim. $ f(n+1) \leq 3f(n) + 2$ (If this is proven, the original problem becomes trivial due to mathematical induction) Proof. Assume a rectangle has property $ n+1$, and has $ f(n+1)$ rectangles. Observe the figure below. Select a rectangle each from the top/left side, which 'stretches out the most from the side'. (The red rectangles) In other words, any rectangle that is attached to the two sides cannot intersect the respective bold line Denote area 1 = blue area area 2 = green area area 3 = orange area For $ i<=j$, if a rectangle is both on area $ i$ and area $ j$, we consider the rectangle to be within area $ i$. Subclaim. Each of area 1, area 2, area 3 contains rectangles of maximum $ f(n)$. Proof. We will prove that each of area 1, 2, 3 have property $ n$, then the subclaim follows. [1] Area 1 has property $ n$ Proof] Assume that it doesn't. Since the figure as a whole has property $ n+1$, area 1 must have property $ n+1$. This, and the fact that it doesn't have property $ n$ lead to the conclusion that there exists a rectangle on a side of the rectangle, and both in area 1. But this contradicts the definition of the red rectangles chosen! [2] Area 2 has property $ n$ Proof] This is trivial. Since the intersection between area 1 and 2 is all considered to be in area 1, it definitely has the horizontal property $ n$. Vertical property $ n$ is trivial. [3] Area 3 has property $ n$ Proof] Look at the diagram, it's obvious. Due to the subclaim, there are at most $ 3f(n) + 2$ rectangles in the figure, and therefore, $ f(n+1) \leq 3f(n) + 2$, as desired by the claim.[/url]

Attachments:

qwerty414 wrote: Area 2 has property n Proof] This is trivial. Since the intersection between area 1 and 2 is all considered to be in area 1, it definitely has the horizontal property n. Vertical property n is trivial. Could you explain this more? I don't see why Area 2 has to have horizontal property $n$.

A similar problem is mentioned in Titu Andreescu's book PFTB under the chapter Geometry and Numbers . Thank You!