MathLabs

第1题

设整数 n≥5n\ge5。考虑边长分别为 1,2,…,n1,2,\ldots,n 的 nn 个正方形，将它们放置在平面上，使得各边分别平行于 xx 轴和 yy 轴。假设任意两个正方形至多在顶点处接触。证明可以这样放置这些正方形，使得每个正方形恰好与另外两个正方形接触。
第 1/3 步：将 {1,...,n-4} 划分为和差为1或2的两组
上一步下一步
{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\}
详细分析

先将边长为 n−3,n−2,n−1,nn-3,n-2,n-1,n 的四个最大正方形留出。对余下的 {1,…,n−4}\{1,\ldots,n-4\}，从大到小不断取出四个连续整数 {t,t+1,t+2,t+3}\{t,t+1,t+2,t+3\}，把 t,t+3t,t+3 放入 AA，把 t+1,t+2t+1,t+2 放入 BB（对和之差的贡献为 00），直到剩下最小的 r∈{1,2,3,4}r\in\{1,2,3,4\} 个数。若 r=1r=1 则将 {1}\{1\} 放入 AA（差为 11）；若 r=2r=2 则令 2∈A2\in A、1∈B1\in B（差为 11）；若 r=3r=3 则令 1,3∈A1,3\in A、2∈B2\in B（差为 22）；若 r=4r=4 则令 2,4∈A2,4\in A、1,3∈B1,3\in B（差为 22）。于是 ∑a∈Aa−∑b∈Bb∈{1,2}\sum_{a\in A}a-\sum_{b\in B}b\in\{1,2\}。