MathLabs

第6問

2025×20252025\times2025 の単位正方形からなる格子を考える。マティルダはこの格子の上にいくつかの長方形のタイルを置きたい(大きさは異なってもよい);各タイルの各辺は格子線上にあり、各単位正方形は高々1枚のタイルで覆われるものとする。格子のすべての行とすべての列がタイルで覆われていない単位正方形をちょうど1つ持つようにするために、マティルダが置く必要のあるタイルの最小枚数を求めよ。
ステップ 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 に対し、行区間 [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] をもつ k×kk\times k の正方形タイル Tp,qT_{p,q} を1枚置く。残りの境界長方形は次の通りである。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] の長方形を1枚置く。指定した範囲では各区間は空でない。黒マスの式は各行・各列にちょうど1マスを与える。区間を直接確認すれば、k×kk\times k タイルと境界長方形は互いに素で、どの BrB_r も覆わず、他の全マスを覆うことが分かる。4つの族はそれぞれ、(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 枚である。