대한수학회,국가수리과학연구소와 함께하며,
엔씨소프트가 후원합니다.
Problems
문제
2017.11.30
국가수리과학연구소의 12번째 문제입니다.
①‛페러스 다이어그램(Ferrers Diagram)‛은 유한개의 네모 칸이 모인 행으로 이루어진 도형으로, [그림1]처럼 각 열은 왼쪽에 정렬돼 있으며 아래로 내려갈수록 행의 길이가 같거나 더 짧다.
[그림1]
②페러스 다이어그램을 이루는 각각의 네모 칸을 
라고 하자. 이때 (
의 아래쪽에 있는 네모의 개수)+(오른쪽에 있는 네모의 개수)+1을 ‘
의 훅 길이(Hook Length)’라고 한다. [그림1]의 페러스 다이어그램을 이루는 각각의 네모 칸에 훅 길이를 적으면 [그림2]와 같다.
*c 자신의 개수까지 포함해야 하므로 +1을 한다.
[그림2]
문제1.
자연수 
에 대해, 의 배수와 
+1의 배수를 훅 길이로 가지지 않는 페러스 다이어그램은 몇 개일까? 이를테면 [그림2]의 페러스 다이어그램은 훅 길이 중 6의 배수(6, 12, 18, 
)는 없지만 7의 배수(7, 14, 21, )가 있으므로, =6인 경우 이 조건을 만족하지 않는다.
문제2.
홀수 
에 대해, 의 배수와 
+2의 배수를 훅 길이로 가지지 않는 페러스 다이어그램의 개수는 몇 개일까? [그림2]의 페러스 다이어그램은 훅 길이 중 9의 배수와 11의 배수가 없으므로, = 9일 때 이 조건을 만족한다.
(1)번 문제에 대한 관찰입니다.
n=1일 때는 존재하지 않음이 자명합니다.
n=2일 때는 1개밖에 없는 것으로 추정됩니다(■ 한 칸 짜리 모양)
n=3일 때는 4개밖에 없는 것 같습니다.
(한 칸짜리, 가로로 두 칸, 세로로 두 칸, ㄱ자 모양)
ㄱ자 모양은 존재할 수 없습니다 왼쪽에 정렬되야 하니까여
| 5 | 2 | 1 |
| 2 | ||
| 1 |
이런 모양은 나올 수 있겠군요
네 그 모양 맞습니다.
문제 푸신 건가요?
맨 왼쪽 위의 훅 길이가 가장 길고 그 칸의 훅 길이는 행의 길이가 a, 열의 길이가 b라고 하면 a+b-1입니다. 따라서 a+b-1이 n또는 k보다 작으면 문제 1, 문제2의 조건은 항상 만족합니다.
훅 다이어그램에 k의 배수가 없으면, 맨 윗 줄을 제거해도 k의 배수가 없다는 것은 자명합니다.
이 말은 즉, k의 배수가 없는 훅 다이어그램은 다른 k의 배수가 없는 훅 다이어그램의 부분집합이란 것입니다.
또한, k의 배수가 없는 훅 다이어그램을 왼쪽에서 a줄, 위에서 b줄씩 각각 제거했을 때도 이 훅 다이어그램은 k의 배수가 없는 훅 다이어그램이 됩니다. (아니면 비어있는 다이어그램이거나.)
이것과 비슷한 문제인 것 같은데...
뭔 문제요??(최단경로??)
이 최단경로 문제랑 무슨 관련이 있을까요
그리고 맨 윗쥴을 제거해도 되는 건 맞지만 그 역은 참이 아닙니다. 그러므로 항상 다른 다이어그램의 부분집합은 아니라는 거죠
문제에 대한 접근을 '다이어그램의 최대 크기'를 알아내는 방향으로 해야 할 듯 합니다..
최대 크기(행x열)을 알아내면 대칭성과 맨 위에 있는 줄, 맨 왼쪽 줄을 뺄 수 있다는 것을 이용하여 페러스 다이어그램의 수를 많이 알아낼 수 있습니다. 그런데 그게 전부라고는 못하겠군요
더 이상 위쪽이나 왼쪽에 줄을 추가할 수 없는 페러스 다이어그램을 페러스 다이어그램의 기본형이라고 하면 그 기본형은 여러 개가 있을 건데, n에 따라 그 기본형의 개수도 구해야 할 것 같습니다
문제 1에서 n=4일 때 정사각격자에서는 6x6 격자일 때가 가장 큰 페러스 다이어그램이었습니다. 제 추측으로는 a+b-1이 n보다 클 때는 ㄱ자 모양만 생기고, nxn격자가 제일 클 줄 알았는 데 아니더군요.
이걸 일반화해서 n이 4 이상의 정수일 때 기본형을 하나 찾았습니다
여러분 여기에도 관심좀요..ㅜㅜ
너무어려워요 ㅠ
수학장 님의 아이디어를 응용해 k가 n/2 이하일 때 다음과 같은 모양을 발견했습니다.
| 2n+2k-1 | n+2k-1 | n+2k-2 | ... | n+k | n-1 | ... | 1 |
| n+2k-1 | 2k-1 | 2k-2 | ... | k | |||
| n+2k-2 | 2k-2 | 2k-3 | ... | k-1 | |||
| ... | ... | ... | ... | ... | |||
| n+k | k | k-1 | ... | 1 | |||
| n-1 | |||||||
| ... | |||||||
| 1 |
예를 들어, n=6일 때
| 17 | 11 | 10 | 9 | 5 | 4 | 3 | 2 | 1 |
| 11 | 5 | 4 | 3 | |||||
| 10 | 4 | 3 | 2 | |||||
| 9 | 3 | 2 | 1 | |||||
| 5 | ||||||||
| 4 | ||||||||
| 3 | ||||||||
| 2 | ||||||||
| 1 |
의 경우가 존재합니다.
n+2k가 아니라 n+k 아닌가요
아 죄송합니다 n+k입니다.
이 문제 새로운 댓글을 본 것이 40일도 넘었네요
# 가장 재미있을것 같던 문제
# 난 왜 잘 안 풀리지
# 이 문제에 조금만 더 관심을
맞아요, 맞아! 여러분 페러스 다이어그램에도 관심을 가져주세요ㅜㅜ
#내가봐도재밌는문제
#연구원 님 힌트 좀 주세요
수돌이님이나, 수학자 같은 분들이 푸셨으면 빨리 풀렸을텐데... 그분들은 바빠서 못 하시는 것 같네요
저는 이문제에 별로 관심이 없어서...이번 국가수리과학문제는 풀어보려고요.(저 대수 팬이거든뇨.)
머리가 잘 안돌아가네요 ㅠㅠ 여러분 이제 여기에는 관심이 없나요... 관심을 가져주세요!
옳소옳소! harryahn 친구 쵝오!
위에서 1 번째 가로줄은 n(n-1)/2 개의 사각형으로,
2 ~ 3 번째 가로줄은 (n-1)(n-2)/2 개의 사각형으로,
4 ~ 6 번째 가로줄은 (n-2)(n-3)/2 개의 사각형으로,
......
k(k-1)/2 + 1 ~ k(k+1)/2 번째 가로줄은 (n-k+1)(n-k)/2개의 사각형으로,
......
(n-1)(n-2)/2 + 1 ~ n(n-1)/2 번째 가로줄은 1 개의 사각형으로 나열하면 (1)의 조건을 만족합니다.
따라서 어떤 n에 대하여 기본적으로 n(n-1)/2 X n(n-1)/2 사이즈의 정사각형은 만들 수 있네요.
아마도 제 생각에는 이 경우가 가장 큰 경우 같은데..
이 모양이 성립한다는 증명은 시간상 나중에 해서 올려야 할 것 같습니다. ㅠㅠ
동아사이언스, 콘텐츠 저작권은 동아사이언스에 있으며 무단 전재·복사·배포를 금합니다.
Copyright © Dongascience. All right reserved.
정기독자 무료 이용 안내
