BOJ 10803 — 正方形を作る：漸化式境界の証明

目次

BOJ 10803 — 正方形を作る

問題モデルと主張

有効な切断計画はギロチンカットによる分割とする。つまり、各切断で一つの長方形を二つの長方形に分け、最後の各ピースは辺の長さが正の整数である正方形とする。$f(n,m)$ を $n\times m$ の長方形を分割するために必要な正方形の最小個数とする。回転できるので $f(n,m)=f(m,n)$ である。

原文は $m\ge n^2/3$ のとき $f(n,m)=f(n,m-n)+1$ と主張している。しかし原文の証明は、$m$ と $n+m$ の間で変数を置き換える際に条件を正しく移していない。以下では、より保守的な十分条件を証明する。

$m-n\ge \frac{n^2}{3}\quad\Longrightarrow\quad f(n,m)=f(n,m-n)+1,$

ただし $n,m$ は正の整数で $n\le m$ とする。この書き換えでは、原文のより弱い閾値を主張しない。

余りの長方形に対する上界

正の整数 $a,b$ に対して

$f(a,b)\le \max(a,b)$

である。対称性により $a\le b$ とする。$a=1$ なら単位正方形 $b$ 個で分割できる。$a\ge2$ では $b=qa+s$、$q\ge1$、$0\le s<a$ と書く。$s=0$ なら $a\times a$ の正方形 $q$ 個でよい。$s>0$ なら、まず $a\times a$ の正方形を $q$ 個置き、残りの $a\times s$ の長方形を分割する。長い辺に関する強い帰納法と対称性により $f(s,a)\le a$ だから、

$f(a,b)\le q+a\le qa+s=b.$

最後の不等式は $b-(q+a)=(q-1)(a-1)+(s-1)\ge0$ から従う。この構成はすべてギロチンカットで実現できる。

漸化式境界の証明

$r=m-n$ とし、$r\ge n^2/3$ と仮定する。$n\times(n+r)$ の長方形は、$n\times n$ の正方形一つと $n\times r$ の長方形に分割できるので、

$$f(n,n+r)\le f(n,r)+1. \tag{1}$$

逆向きの厳密な不等式を示す。$F=f(n,n+r)$ とし、最適なギロチン分割を一つ選ぶ。

分割に $n\times n$ の正方形が含まれていれば、その正方形は長方形全体の高さを占める。それを取り除くと、左右にギロチン分割された長方形が残り、その幅の合計は $r$ である。二つの分割を並べれば、$F-1$ 個の正方形で $n\times r$ を分割できる。したがって $f(n,r)\le F-1$ である。

次に、最適分割に $n\times n$ の正方形がないと仮定する。

$q=\left\lfloor\frac n3\right\rfloor+1$

とおくと、$q>n/3$ かつ $nq\le n+n^2/3\le n+r$ である。左端から幅 $nq$ の領域 $W$ を取る。整数辺の正方形からなる整数長方形のギロチン分割では境界座標は整数なので、$W$ は幅 1 の列 $nq$ 本に分けられる。

各列を横切る正方形の辺の長さを $s_1,\ldots,s_c<n$ とする。それらの縦区間は高さ $n$ 全体を分割し、$n\times n$ の正方形はないので $c\ge2$ である。コーシー・シュワルツの不等式から

$\sum_{i=1}^c\frac1{s_i}\ge \frac{c^2}{\sum_i s_i}=\frac{c^2}{n}\ge\frac4n.$

辺の長さが $s$ の正方形が横切る単位列ごとに $1/s$ 個として数えると、全体の寄与は少なくとも $4q$ になる。一つの正方形が $W$ 内で横切る単位列は最大 $s$ 本なので、その寄与は $s/s=1$ 以下である。したがって、$W$ と交差する元の正方形は少なくとも $4q$ 個ある。その個数を $D$ とすると $D\ge4q$ である。

$W$ と交差する正方形 $D$ 個を取り除き、$W$ を $n\times n$ の正方形 $q$ 個で埋める。$W$ の右側は、その垂直境界で元のギロチン分割を切り取って得る。分割木に関する帰納法により、切り取った後もギロチン分割を保てる。境界線より完全に左にある部分木は捨て、完全に右にある部分木はそのまま残す。交差する垂直分割ノードでは、境界線が分割線より左にあれば左の子を切り取り右の子を残す。境界線が分割線以降にあれば左の子を捨て、右の子を切り取る。水平分割ノードでは両方の子を切り取り、水平分割を保つ。したがって、境界線を横切る正方形だけが長方形の断片になる。各断片の高さは $s$、幅は $s$ 以下である。断片の縦区間は互いに重ならないため、高さの合計は $n$ 以下となる。前述の上界により、これらの断片を埋める正方形は合計で最大 $n$ 個でよい。それ以外の右側の正方形はそのまま残す。

得られた全体の分割に使う正方形は最大 $F-D+q+n$ 個である。新しく置いた正方形のうち左端の一つを取り除くと、幅 $r$ の長方形が残り、正方形の個数は最大

$F-D+q+n-1\le F-3q+n-1<F$

となる。$D\ge4q$ かつ $q>n/3$ だからである。よってこの場合も $f(n,r)<F$ である。

したがって $f(n,n+r)>f(n,r)$ である。両辺は整数なので、(1) と合わせると

$f(n,n+r)=f(n,r)+1$

を得る。$r=m-n$ を代入すれば、主張した境界が証明される。

適用範囲

この閾値は十分条件であり、必要条件ではない。原文の閾値より保守的であり、この証明を根拠に原文のより強い条件を使ってはならない。証明は長方形を再帰的に切るギロチンモデルを前提とする。

出典

2022-05-31 に 0archlinux0 / MINJUN PARK が公開し、CC BY 4.0 と表示した Tistory ID 52 をもとにした。変数と閾値のずれを修正し、タイル数の議論を明示したうえで、この版で証明できる十分条件のみを述べる。

参考

• BOJ 10803 — 正方形を作る
• Tistory 原文、ID 52