SON OF SUN

로 둔다.

기록 집합별 상한. 양의 방향을 먼저 보자. 음의 기운을 가진 기록 정점의 인덱스 집합을 $\mathcal R=\{b_1<\cdots<b_t\}$로 고정한다. 기록이 아닌 음의 정점은 깊이 $1$, 기록이 아닌 양의 정점은 당시 최대 깊이에 두는 것이 최적이다. 이 상태에서 양의 정점 $i$를 기록으로 바꾸는 이득은

이다. $i\in\mathcal R$이면 같은 쌍의 음의 기록 정점도 한 칸 깊어져 자기 항 $i$가 상쇄된다. 따라서 모든 양의 정점이 기록인 최적 구성이 존재한다. 그 값은

이다. $b_r\geq r$이고 $f_r(x)-f_r(x+1)=3x+r+1>0$이므로, 이 값은 $\mathcal R=\{1,\ldots,t\}$에서의 $F_N(t)$ 이하이다. 초기 구간이 아닌 집합이면 $b_t\geq t+1$이므로 $F_N(t)$보다 적어도 $4t+1$ 작다.

초기 구간이고 $t<N$일 때, 양의 정점의 기록을 하나라도 생략하면 손실은 적어도 $t+1$이다. $i>t$이면 자기 항 $i\geq t+1$이 남고, $i\leq t$이면 위 합에 $j=N\notin\mathcal R$이 포함되기 때문이다. 기록이 아닌 음의 정점의 깊이를 $1$보다 늘리는 손실도 그 인덱스가 $t$보다 크므로 적어도 $t+1$이다. 따라서 이 기록 집합에서 최댓값과 다른 값은 모두 $F_N(t)-t-1$ 이하이다.

음의 방향은 전체 값의 부호를 바꾸어 분석한다. 이번에는 원래 양의 정점 중 기록인 집합을 고정한다. 기록이 아닌 양의 정점은 깊이 $1$로 두고, 모든 음의 정점이 기록인 구성이 최적이다. 음의 정점 $i$를 기록으로 바꾸는 이득은 $i+\sum_{j>i,\,j\notin\mathcal R}j>0$이고, 최댓값은

이다. $g_r(x)-g_r(x+1)=3x+r-1>0$이므로 초기 구간에서 $B_N(t)$를 얻고, 초기 구간이 아니면 적어도 $4t-1$의 손실이 생긴다. 초기 구간이며 $t<N$일 때, 기록을 생략하거나 비기록 정점의 깊이를 최적값에서 바꾸는 손실은 적어도 $t+1$이다. 첫 양의 정점은 반드시 기록이지만 $B_N(1)>B_N(0)$이므로 극값 계산에는 $t=0$도 포함해도 된다. 이것으로 두 극값 공식이 증명된다.

두 가지 직접 구성. 처음 $t$쌍의 깊이를 $2i-1,2i$로 정한다. 이후 $i>t$에 대해 양의 정점의 깊이를 $i+t$로 고정하고 음의 정점의 깊이를 $1+b_i$로 정하면

를 만든다. 반대로 음의 정점의 깊이를 $i+t$, 양의 정점의 깊이를 $1+b_i$로 정하면

를 만든다. 후자에서 양의 정점이 먼저 깊이 $i+t$에 도달하더라도, 음의 정점은 이미 존재하는 깊이 $i+t-1$의 정점을 부모로 골라 같은 깊이에 둘 수 있다. 따라서 모든 $b_i$ 선택이 유효하다.

동전 합의 구간. $t\geq1$, $N\geq2t+1$이라 하자. 값 $i$인 동전을 $i+t-1$개씩 가지며, $a=t+1$, 전체 동전 수를 $C$, 전체 합을 $W$라고 하자. 이 동전들의 부분집합 합은 정확히

이다. 정확히 $q$개를 고른 합은 가장 작은 $q$개의 합 $A_q$부터 가장 큰 $q$개의 합 $Z_q$까지의 모든 정수를 채운다. 정렬된 동전에서 선택한 인덱스를 한 칸씩 옮겨 가장 작은 선택을 가장 큰 선택으로 바꿀 수 있고, 인접한 동전 값의 차이가 $0$ 또는 $1$이기 때문이다.

$q=1,\ldots,C-2$에서 이웃한 두 구간이 이어짐을 보이면 된다. $Z_q=W-A_{C-q}$이므로 그 사이의 차이는

이다. 정렬된 동전을 $c_1\leq\cdots\leq c_C$라 하면 $D_{q+1}-D_q=c_{q+2}-c_{C-q}$이므로 $D_q$는 가운데까지 감소하고 이후 증가한다. 최댓값은 양 끝에서 나오며, 최소 동전 $a$가 적어도 두 개 있으므로 그 값은 $2a-N\leq1$이다. 따라서 $q=1,\ldots,C-1$의 구간은 $[a,W-a]$ 전체를 채운다. 나머지 두 합은 아무것도 고르지 않거나 모두 고르면 되고, 최소 동전이 $a$이므로 다른 바깥 합은 불가능하다.

큰 $N$에서 내부 구간의 완전성. 차분은

이고 감소한다. $N\geq13$이면 첫 최대 인덱스 $p,q$는 $p,q\geq2$ 및 $N\geq2p+1,2q+1$을 만족한다. 실제로 $N=2s$에서 $\Delta B_{s-1}=s(7-s)/2\leq0$이고, $N=2s+1$에서 $\Delta B_s=-(s-2)(s+1)/2\leq0$이다. 또한 $\Delta F_t<\Delta B_t$이다.

첫 구성에서 $t=p$에 동전 보조정리를 적용하면

을 채운다. 왼쪽 끝은 $1$ 이하이므로 양의 내부 구간이 모두 가능하다. 둘째 구성의 $t=q$는

을 채운다. 한편 모든 양의 정점을 깊이 $1$에 두고 음의 정점을 각각 깊이 $1$ 또는 $2$에 두면 $[-S(N),0]$의 모든 정수를 만든다. 두 구간은 서로 겹치므로 음의 내부 구간도 모두 가능하다. 따라서

의 모든 정수가 가능하다.

양 끝에서 남는 세 후보. 위쪽 경계 $[R_N-p,R_N]$를 보자. 인접 차분의 차이는 $\Delta F_t-\Delta F_{t-1}=-(5t+2)$이다. $p$가 첫 최대 인덱스이므로 $\Delta F_{p-1}>0$, $\Delta F_p\leq0$이고, 따라서

기록 정점 수 $t$가 $p-1,p,p+1$ 밖에 있으면 그 기록 수의 상한부터 경계 밖이다. 이 세 경우에도 초기 구간이 아닌 기록 집합은 적어도 $4t+1>p$를 잃어 경계에 들어오지 못한다. 초기 구간의 다른 구성은 $t+1$ 이상을 잃는다. $t=p-1$이면 $F_N(t)<R_N$이므로 남은 손실 여유는 $p-1=t$ 이하이고, 나머지 두 경우에도 여유는 $t$ 이하이다. 따라서 경계에서 가능한 값은 세 최적값 $F_N(p-1),F_N(p),F_N(p+1)$뿐이며, 앞의 직접 구성으로 실제로 만들 수 있다.

아래쪽도 $\Delta B_t-\Delta B_{t-1}=-5t$와 $p$ 대신 $q$를 써서 같다. 이때 두 칸 떨어진 값의 손해는 각각 $5(q-1)$보다 크거나 $5(q+1)$ 이상이며, 모두 $q$보다 크다. 초기 구간이 아닌 집합의 손해도 $4t-1>q$이므로, 경계에서 가능한 값은 $-B_N(q-1),-B_N(q),-B_N(q+1)$뿐이다. 이것으로 $N\geq13$의 판정 분류가 완전히 증명된다.