문제 모델과 주장
유효한 절단 계획은 길로틴 방식 분할이다. 즉, 절단할 때마다 직사각형 하나를 두 직사각형으로 나누고, 마지막 조각은 변의 길이가 양의 정수인 정사각형이어야 한다. $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$이다. 변이 $s$인 정사각형은 $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 52번 글을 바탕으로 한다. 이 버전은 변수와 임계값의 이동을 바로잡고 타일 수 계산을 명시하며, 여기서 증명한 충분조건만 제시한다.