USAMO와 Hook-length formula

2016년 USAMO(미국 수학 올림피아드) 2번 문제.

임의의 양의 정수 $k$ 에 대해, $\displaystyle (k^2)! \cdot \prod_{j=0}^{k-1} \frac{j!}{(j+k)!}$ 이 정수임을 보여라.

유리식 형식으로 주어진 수가 정수임을 보이는 스탠다드한 정수론 문제로, 실제로 정수론적으로 푼다면 (임의의 소수 $p$ 에 대해 분모와 분자의 $\nu_p$ 를 계산하여 부등식을 이끌어내는 식. 위 링크 내의 첫 번째 풀이 참조) 2/5번 문제 포지션에 맞는 적절한 올림피아드 정수론 문제였어야했다.

그런데 이 문제가 enumerative combinatorics에서 등장하는 hook-length formula의 특수 케이스라서 이 정리를 이용하면 그야말로 한 줄에 풀리게 된다. 실제로 몇 학생들이 이 hook length formula를 증명 없이 인용하여 답안을 작성했고, 이 학생들에게 어떻게 점수를 줘야하는가가 논란이 된 적이 있다.

hook-length formula는 쉽게 말해 좌상단에 맞춰 정렬된 $n$ 개의 동일한 정사각형들이 있을 때, 그 안에 1에서 $n$ 까지의 자연수를 쓰되 가로방향과 세로방향으로 늘 수가 증가하도록 쓰는 경우의 수에 대한 공식이다.

이런 정사각형들이 모여있는 그림을 주어진 partition에 대한 Young diagram이라 하고, 이렇게 숫자를 쓴 오브젝트를 standard Young tableau, 줄여서 SYT라고 부른다
Source: https://en.wikipedia.org/wiki/Young_tableau

Young diagram이 주어져 있을 때 그 모양을 갖는 SYT의 개수가 어떻게 나오는지를 계산하기 위해, 먼저 각각의 정사각형에 대해, 그 자신과, 오른쪽에 있는 정사각형들과, 아래쪽에 있는 정사각형들의 개수를 센다. (단 대각선으로 우하단에 있는 정사각형은 고려하지 않는다.) 이를 각각의 정사각형에 대한 hook-length라고 부르며, (이 정사각형이 코너에 있는 Γ 모양의 후크의 길이란 인식에서 나온 네이밍) 아래 예시에서 각각의 정사각형에 써있는 수가 그 정사각형의 hook-length이다.

Source: https://en.wikipedia.org/wiki/Hook_length_formula

편의상 주어진 모양 $\lambda$ 에 대해 i행 j열에 위치한 정사각형의 hook-length를 $h_{\lambda}(i,j)$ 라고 하면, 이 모양의 SYT의 개수는 바로 $\displaystyle \frac{n!}{\prod h_{\lambda}(i,j)}$ 가 되며, 이것이 hook-length formula이다. 이에 대해 자세한 내용은 [1]을 참조. 일단은 elementary한 증명도 있긴 하다.[2]

이 정리를 알고나면 USAMO 문제를 봤을 때 주어진 값이 바로 $k \times k$ 모양의 정사각형으로 배열된 Young diagram에 대한 SYT 개수임을 알 수가 있다. (정확히는 partition $\lambda=(k,k,\ldots,k)$ ( $k$ times)에 대한 SYT 개수) 그 개수는 정수이니까 바로 증명이 끝나는 것.

문제는 이것이 증명으로 보자면 옳고 유효하지만, 올림피아드에서의 풀이로 보면 어떻냐는 것이다. 2007년 IMO 6번에서도 combinatorial nullstellensatz[3]와 관련되어 비슷한 일이 있었는데, 이런 케이스들에서 주안점을 맞춰야할 것은 인용하고자하는 결과를 썼더니 문제가 너무 트리비얼하게 되면 그에 대한 증명을 제공해야한다는 것이라고 봄. 특히나 인용하고자하는 것이 주어진 문제의 직접적 일반화라면 더더욱. 앞서 링크했던 Evan Chen의 의견과 뜻을 같이한다.

References

[1] Richard P. Stanley, Enumerative Combinatorics, Volume 2, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, Cambridge, 1999.

[2] J. Bandlow, “An elementary proof of the hook formula” The Electric Journal of Combinatorics 15 (2008), #R45 https://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1r45/pdf

[3] N. Alon, “Combinatorial Nullstellensatz” Combinatorics, Probability and Computing Volume 8 Issue 1-2, January 1999 Pages 7 – 29 https://m.tau.ac.il/~nogaa/PDFS/null2.pdf

월	화	수	목	금	토	일
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31

References

이 글 공유하기:

이것이 좋아요:

관련

답글 남기기 응답 취소