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이다.

편의상 주어진 모양 \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


답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중