第6問

2025\times2025

の単位正方形からなる格子を考える。マティルダはこの格子の上にいくつかの長方形のタイルを置きたい(大きさは異なってもよい);各タイルの各辺は格子線上にあり、各単位正方形は高々1枚のタイルで覆われるものとする。格子のすべての行とすべての列がタイルで覆われていない単位正方形をちょうど1つ持つようにするために、マティルダが置く必要のあるタイルの最小枚数を求めよ。

ステップ 3/6: 覆われていないマスを置換とみなす

前のステップ次のステップ

\text{LIS length }a,\ \text{LDS length }b\ \text{of the uncovered permutation}\ \Longrightarrow\ ab\ge n

詳しい解説

覆われていない $n$ 個のマスを $U$ とする。行の順に並べると列の置換をなす。2つのマス $u=(u_1,u_2)$ 、 $v=(v_1,v_2)$ に対し、 $u_1<v_1$ かつ $u_2<v_2$ のとき $u<v$ と定めると、これは北東方向の半順序である。最大反鎖 $A$ （減少部分列）を選び、Dilworth の定理で $U$ を $|A|$ 本の鎖に分割する。各鎖は $A$ とちょうど1点で交わる。ここでこの分割中で最長の鎖を $C$ とし、 $a=|C|$ 、 $b=|A|$ とおく。各鎖の長さは高々 $a$ なので $ab\ge n$ である。 $C$ は増加部分列、 $A$ は減少部分列であり、各鎖が $A$ と1点で交わるので、両者はちょうど1つのマス $c$ で交わる。この $A$ , $C$ の選び方が積の評価と、後の数え上げに必要な共通の交点を同時に与える。