MathDB

3

Part of 2008 USAMO

Problems(1)

Partitioning Region into Paths

Source: USAMO 2008 Problem 3

5/1/2008
Let nn be a positive integer. Denote by SnS_n the set of points (x,y)(x, y) with integer coordinates such that ∣x∣+∣y+12∣<n. \left\lvert x\right\rvert + \left\lvert y + \frac{1}{2} \right\rvert < n. A path is a sequence of distinct points (x1,y1),(x2,y2),…,(xℓ,yℓ)(x_1 , y_1), (x_2, y_2), \ldots, (x_\ell, y_\ell) in SnS_n such that, for i=2,…,ℓi = 2, \ldots, \ell, the distance between (xi,yi)(x_i , y_i) and (xi−1,yi−1)(x_{i-1} , y_{i-1} ) is 11 (in other words, the points (xi,yi)(x_i, y_i) and (xi−1,yi−1)(x_{i-1} , y_{i-1} ) are neighbors in the lattice of points with integer coordinates). Prove that the points in SnS_n cannot be partitioned into fewer than nn paths (a partition of SnS_n into mm paths is a set P\mathcal{P} of mm nonempty paths such that each point in SnS_n appears in exactly one of the mm paths in P\mathcal{P}).
algorithmreflectionsymmetryAMC