PUMaC 2014 · 组合（A 组） · 第 1 题

PUMaC 2014 — Combinatorics (Division A) — Problem 1

[ 3 ] What is the largest n such that a square cannot be partitioned into n smaller, non- overlapping squares?

解析

[ 3 ] What is the largest n such that a square cannot be partitioned into n smaller, non- overlapping squares? Solution: We see that we can partion n = 6 , 7 , 8 as follow: For n = 5, we note that there needs to be a different square in every corner. (If one square is th in two corners, it will be the size of the original square). Since the 5 square can touch only 1 side without being in a corner, there can be at most 1 side with 3 squares touching it. Let this side be AB . Without loss of generality, let the corner square of D be larger than that of C . As can be seen, since there are only 2 squares on sides AD , DC , the configuration must be as such. However, we realise it is impossible for the corner square of B to be placed in any way such that the line BC is entirely contained. When the corner square of D and C are the same size, we see that their sides are half of the original square and for sides AD and BC to be covered completely, the corner squares of A, B also needs to be half of the original square. Hence there are only 4 squares. Thus we conclude that it is impossible for n = 5 .