MathLabs

Problem 1

Let n≥5n\ge5 be an integer. Consider nn squares with side lengths 1,2,…,n1,2,\ldots,n, respectively. The squares are arranged in the plane with their sides parallel to the xx and yy axes. Suppose that no two squares touch, except possibly at their vertices. Show that it is possible to arrange these squares in a way such that every square touches exactly two other squares.
Step 1 of 3: Partition {1,...,n-4} with sum difference 1 or 2
Previous stepNext step
{1,…,n−4}=A⊔B,∑a∈Aa−∑b∈Bb∈{1,2}\{1,\ldots,n-4\}=A\sqcup B,\qquad \sum_{a\in A}a-\sum_{b\in B}b\in\{1,2\}
Detailed analysis

Set aside the four largest squares of side lengths n−3,n−2,n−1,nn-3,n-2,n-1,n. From the remaining lengths {1,…,n−4}\{1,\ldots,n-4\}, repeatedly peel off blocks of four consecutive integers {t,t+1,t+2,t+3}\{t,t+1,t+2,t+3\} from the top, placing t,t+3t,t+3 into AA and t+1,t+2t+1,t+2 into BB (contributing 00 to the sum difference), until r∈{1,2,3,4}r\in\{1,2,3,4\} smallest numbers remain. Place {1}\{1\} in AA if r=1r=1 (difference 11); 2∈A2\in A, 1∈B1\in B if r=2r=2 (difference 11); 1,3∈A1,3\in A, 2∈B2\in B if r=3r=3 (difference 22); 2,4∈A2,4\in A, 1,3∈B1,3\in B if r=4r=4 (difference 22). Thus ∑a∈Aa−∑b∈Bb∈{1,2}\sum_{a\in A}a-\sum_{b\in B}b\in\{1,2\}.