MathLabs

第6题

考虑一个 2025×20252025\times2025 的单位正方形网格。玛蒂尔达希望在网格上放置若干矩形瓷砖(大小可以不同)，使得每块瓷砖的每条边都在网格线上，且每个单位正方形至多被一块瓷砖覆盖。求玛蒂尔达需要放置的最少瓷砖数，使得网格的每一行和每一列都恰好有一个单位正方形未被任何瓷砖覆盖。
第 2/6 步：n = k² 时的构造
上一步下一步
(k−1)2 square tiles of size k×k + 4(k−1) boundary tiles = k2+2k−3 tiles(k-1)^2\ \text{square tiles of size }k\times k\ +\ 4(k-1)\ \text{boundary tiles}\ =\ k^2+2k-3\ \text{tiles}
详细分析

下面给出不依赖图形的明确构造。将行、列编号为 11 到 nn，令 n=k2n=k^2；对每个 1≤r≤n1\le r\le n，把 Br=(r,  k((r−1) mod k)+k−⌊(r−1)/k⌋)B_r=(r,\;k((r-1)\bmod k)+k-\lfloor(r-1)/k\rfloor) 留作黑色未覆盖格。对每个 0≤p,q≤k−20\le p,q\le k-2，放置一块 k×kk\times k 方形瓷砖 Tp,qT_{p,q}，其行区间为 [2+kp+q, 1+k+kp+q][2+kp+q,\,1+k+kp+q]，列区间为 [k−p+kq, 2k−1−p+kq][k-p+kq,\,2k-1-p+kq]。其余边界矩形如下：当 1≤q≤k−11\le q\le k-1 时，取行 [1,q][1,q]、列 [kq+1,k(q+1)][kq+1,k(q+1)]；当 0≤p≤k−20\le p\le k-2 时，取行 [kp+1,k(p+1)][kp+1,k(p+1)]、列 [1,k−1−p][1,k-1-p]；当 1≤p≤k−11\le p\le k-1 时，取行 [kp+1,k(p+1)][kp+1,k(p+1)]、列 [k2−p+1,k2][k^2-p+1,k^2]；当 0≤q≤k−30\le q\le k-3 时，取行 [k2−k+2+q,k2−1][k^2-k+2+q,k^2-1]、列 [kq+1,k(q+1)][kq+1,k(q+1)]；最后再取位于第 k2k^2 行、列区间 [1,k2−k][1,k^2-k] 的一个矩形。上述范围内每个区间都非空。黑格公式保证每行每列恰有一个黑格。直接检查这些区间可知，k×kk\times k 方砖与边界矩形两两不交，不覆盖任何 BrB_r，并覆盖所有其他格子：四族边界矩形分别填满 (k−1)×(k−1)(k-1)\times(k-1) 个方砖阵列上、左、右、下的空隙。共有 (k−1)2(k-1)^2 块方砖和 (k−1)+(k−1)+(k−1)+(k−2+1)=4(k−1)(k-1)+(k-1)+(k-1)+(k-2+1)=4(k-1) 块边界砖，所以总数为 (k−1)2+4(k−1)=k2+2k−3(k-1)^2+4(k-1)=k^2+2k-3 块。