BOJ 30513번: 하이퍼 삼각형 자르기

  SASA Programming Contest 2023 Div. 1 (Arena #11)을 쳤다. 원래는 학교 작은 실험실 일정과 겹치고 아레나가 참가 범위가 아니어서 치지 않으려고 했다. 그러나 작은 실험실 행사가 예상보다 일찍 끝났는데 백준을 열어보니 대회창에 진행중인 대회가 보여서 갑자기 치고 싶어져서 쳤다. 15시~18시에 한 대회인데, 사실상 15시 20분에 문제풀이를 시작했다. 늦게 시작했고 아레나 참가범위가 아니어서 성적이 아무 의미 없으니, 재미로 어려운 문제들부터, 즉 H번(A번에서 N, Q 제한이 바뀐 조건)부터 B번까지의 역순으로 풀기로 했다. E번까지 풀고 나니 17시 25분 정도였고, 부모님께 전달받을 물건이 있어서 빨리 내려갔다 오니 17시 35분이었다. B, C, D는 쉬우므로 올솔브 욕심이 나서 저녁을 거르고 대회를 치기로 했다. 그런데 그만 C번에서 마지막 출력 형식에 !를 앞에 출력해야 하는 것을 보지 못하는 바람에, 이걸 디버깅하는데 3~4분이 소요되어, 17시 59분 45초에 C번을 맞고 엄청 쉬운 B번을 결국 못 풀었다. C번에서 2분만 빨리 풀었어도 올솔브를 하는 거였는데 아쉬움이 남지만, 레이팅에 반영되지도 않으며 늦게 시작한 대회니 아무 의미 없다고 생각한다.

7솔로 10등이다. B번의 빈칸이 눈에 띤다. 스코어보드를 쭉 내리면 176등까지 B번이 초록색이 아닌 사람이 단 한 명도 없음을 확인할 수 있어서 너무 웃긴다.

  스코어보드에서 B번의 빈칸이 가장 눈에 띤다면 F번의 초록색 역시 두 번째로 눈에 띤다. F번이 상당히 추상적인 문제여서 일반적인 PS에서 전형적이지 않다고 생각한다. 실제로 F번을 푼 사람이 나를 포함하여 단 4명으로, 유일하게 올솔브한 사람, 5솔한 사람, 1솔한 사람(F번이 재미있어 보여서 그냥 대회 신경 안쓰고 그것만 푼 것 같음)이다. 하지만 F번이 나에게는 정말 재미있었고, 1년 전으로 거슬러 올라가면 나에게 무척 의미 있는 문제이다. 그래서 F번에 대해 간단히 설명하고자 한다.

여러 가지 도형수와 도형수의 고차원으로의 확장에 관한 연구

  작년 8월 초부터 10월 초까지 '여러 가지 도형수와 도형수의 고차원으로의 확장에 관한 연구'를 주제로 수학 영재교육원에서 팀 연구를 진행하였다. 지금 생각해도 이 연구는 너무나도 행복한 경험이었다. 연구의 수준은 높지 않았지만, 내용을 Definition, Theorem, Lemma, Corollary와 같은 수학적 구조를 가지고 체계적으로 서술한 것이 너무나도 뿌듯했기 때문이다. 이 연구의 발표를 한 것이 2022년 11월 12일인데, 오늘은 이 날로부터 정확하게 52주가 지난 날이다. 실제로 고등학교 와서도 물리학이나 응용수학을 하다보니, 작년의 연구처럼 완벽한 수학적 체계로 서술할 수 있는 순수수학 연구를 하지는 않는 것 같다. 2학년 때는 자율연구로 순수수학을 해서, 작년보다 훨씬 높은 수준으로 하면서도 완벽한 엄밀성을 갖춘 연구를 진행해보고 싶다.

  문제 statement는 간단하다. 유클리드 공간 $R^M$ 상에 M+1개의 점이 일정하게 배치되어 정삼각형이나 정사면체 같은 도형을 형성한다.(아직 위상수학을 공부하지 않아 이걸 어떻게 수학적으로 표현해야 할지는 모르겠다.) 이 도형의 각 모서리를 N등분한 뒤 이어 여러 개의 M차원 도형을 형성한다. 이때 이들로 나누어진 영역 중 원래 도형과 닮음인 것의 개수를 구하는 것이다. M=2인 경우는 초등학교 때부터 흔히 보던, '그림 상에서 크고 작은 정삼각형의 개수 찾기' 문제가 된다. 이 문제를 보고 M=2, 3인 경우에 몇 개를 구해보다 보니, 작년에 진행한 연구의 내용이 무척 도움이 될 것이라는 생각이 들었다. 그래서 작년 연구의 포스터를 열고 수식을 보면서 문제를 풀기 시작했다. 작년 연구에서 정의한 기호들을 사용할 것이기 때문에, 해당하는 작년 논문의 일부분을 아래에 넣어둔다.

 

문제 풀이

  문제를 풀이한 과정을 설명하겠다. 편의상 문제에서 정의한 도형을 'M차원 삼각형'이라고 하자. M차원 삼각형이 똑바로 서 있는 경우와 거꾸로 있는 경우가 있을 것이다. 문제 statement의 도형의 각 영역을 점으로 생각하면, 문제 statement의 도형은 논문에서 정의한 'M차원 N번째 이산 삼각뿔'이 된다. 참고로 아래의 내용은 지금 정리하면서 수학적 근거를 적는 것이다. 대회 당시에는 빨리 풀기 위해 M=2일 때만 해본 뒤에 적당히 논문의 식에 끼워맞춰서 풀었던 것 같다.

(i) 똑바로 서 있는 경우

  먼저 M=2를 관찰해 보면, 크기가 N+1-i인 것은 i번째 삼각수로 $P^{(2)}(3, i)=\binom{i+1}{2}$ 이므로, 총합은 하키 스틱 정리로부터 $\sum_{i=1}^{n} \binom{i+1}{2} =\binom{n+2}{3}$ 또는 점화식과 Theorem 7로부터 $\sum_{i=1}^{n} P^{(2)}(3, n) =P^{(3)}(3, n) = \binom{n+2}{3}$ 이 된다. 일반적으로 M인 경우에도, 크기가 N+1-i인 것은 M차원 i번째 삼각뿔수이다. 왜냐하면 M차원 N번째 이산 삼각뿔에서 N+1-i개씩 짝지으면 (1, 2, ..., N+1-i)번 점부터 (i, i+1, ..., N)번 점까지 나오고, 이들을 합쳐서 생각하면 M차원 N+1-i번째 삼각뿔수를 구하는 것이 되기 때문이다. 따라서 똑바로 서 있는 경우의 수는 최종적으로 다음과 같다. $$\sum_{i=1}^{n} P^{(m)}(3, n) =P^{(m+1)}(3, n) = \binom{n+m}{m+1}$$

(ii) 거꾸로 서 있는 경우

  M=2인 경우부터 생각해 보자. N이 작을 때를 해보면서 규칙을 찾으면, 크기 i인 것은 N-2i+1번째 삼각수만큼이 생기게 되므로, 경우의 수는 다음과 같이 계산할 수 있다.  $$\sum _{i=1}^{\infty }P^{(2)}(3, n-2i+1)=P^{(2)}(3, n-1)+ P^{(2)}(3, n-3)+ P^{(2)}(3, n-5)+ ...$$ 물론 여기서 $n\leq 0$ 일 때는 $ P^{(d)}(3, n) = 0$ 로 정의한다.

  일반적인 경우를 고찰하기에 앞서서 위 식이 왜 나왔는지부터 생각해 보자. 한 꼭짓점에 2개의 모서리가 모이므로, 삼각형의 크기가 1 늘어나면 각각에 칸이 하나씩 할당되면서 줄어들어 i 앞의 계수가 2라고 생각할 수 있다. 물론 초기(i=1)인 경우에는, 뒤집힌 삼각형에 해당하는 삼각수가 애초에 N-1번째이기 때문에 초항은 N-1이 된다.

  그러면 M차원의 경우에는, 한 꼭짓점에 M개의 모서리가 모이므로 크기 i인 것은 N-Mi+1번째 삼각수만큼이라고 여길 수 있다. 여기서 초항이 N-M+1인 이유는, 뒤집힌 영역이 나오기 위해서는 꼭짓점으로부터 M-1칸을 떨어져서, 전체 M+1개 모서리 중 그 꼭짓점에 연결된 2개를 제외한 것에 하나씩 할당이 되어야 하기 때문이다. 그래서 이때의 답은 다음과 같다. $$\sum _{i=1}^{\infty }P^{(m)}(3, n-mi+1)=P^{(m)}(3, n-1)+ P^{(m)}(3, n-m-1)+ P^{(m)}(3, n-2m-1)+ ...$$

도형수에 이항 계수를 대입하고 정리하면 최종 답은 다음과 같다.

$$Ans=\binom{n+m}{m+1}+\sum _{i=1}^{\infty }P^{(m)}(3, n-mi+1)=\binom{n+m}{m+1}+\binom{n}{m}+\binom{n-m}{m}+\binom{n-2m}{m}+...$$

맺는 말

  우선 위의 문제풀이가 수학적인 엄밀성이 매우 부족함에 사과한다. 내가 위상수학을 공부하지 않아서 어떻게 표현해야 할지 몰라 그냥 직관적으로만 표현했으며, 그 직관조차도 내가 정확히 이해했는지 모르겠다.

  본 문제를 통해 1년 전에 진행한 연구를 다시 상기시키게 되었고, 도형수를 만나게 되어 무척 반가웠다. 한편 다차원 공간에 대해 직관조차 제대로 잡기 어려운 현재 나의 실력을 알고 더욱 열심히 공부하기로 다짐했다. 앞으로도 PS에서 수학 올림피아드나 수학 연구의 내용이 쓰이는 일이 있으면 이렇게 글을 쓰도록 하겠다.