MathDB

Partitioning squares and an Erdos-type problem

Source: Romanian TST 5 2008, Problem 3

June 13, 2008

geometrysearchinductioncombinatorics proposedcombinatorics

Problem Statement

Let

\mathcal{P}

be a square and let

n

be a nonzero positive integer for which we denote by

f(n)

the maximum number of elements of a partition of

\mathcal{P}

into rectangles such that each line which is parallel to some side of

\mathcal{P}

intersects at most

n

interiors (of rectangles). Prove that 3 \cdot 2^{n\minus{}1} \minus{} 2 \le f(n) \le 3^n \minus{} 2.