IMO 1981 SL 10

Origin: FRA

Problem

Determine the smallest natural number n having the following property: For every integer p, p \geqn, it is possible to subdivide (partition) a given square into p squares (not necessarily equal).

Solution

It is easy to see that partitioning into p = 2k squares is possible for k \geq2 (Fig. 1). Furthermore, whenever it is possible to partition the square into p squares, there is a partition of the square into p + 3 squares: namely, in the partition into p squares, divide one of them into four new squares. p = 8 x y y y x-y Fig. 1 Fig. 2 This implies that both p = 2k and p = 2k + 3 are possible if k \geq2, and therefore all p \geq6 are possible.

On the other hand, partitioning the square into 5 squares is not possible. Assuming it is possible, one of its sides would be covered by exactly two squares, which cannot be of the same size (Fig. 2). The rest of the big square cannot be partitioned into three squares. Hence, the answer is n = 6.