폴리매스

Problems

폴리매스 문제 보기

문제

[국가수리과학연구소] 국12. 페러스 다이어그램과 훅 길이
2017.11.30

같이 풀어볼까?

국가수리과학연구소의 12번째 문제입니다.

①‛페러스 다이어그램(Ferrers Diagram)‛은 유한개의 네모 칸이 모인 행으로 이루어진 도형으로, [그림1]처럼 각 열은 왼쪽에 정렬돼 있으며 아래로 내려갈수록 행의 길이가 같거나 더 짧다.

[그림1]

②페러스 다이어그램을 이루는 각각의 네모 칸을 $\LARGE c$ 라고 하자. 이때 ( $\large \mathit{c}$ 의 아래쪽에 있는 네모의 개수)+(오른쪽에 있는 네모의 개수)+1을 ‘ $\large \color{green}\mathit{c}$ 의 훅 길이(Hook Length)’라고 한다. [그림1]의 페러스 다이어그램을 이루는 각각의 네모 칸에 훅 길이를 적으면 [그림2]와 같다.

*c 자신의 개수까지 포함해야 하므로 +1을 한다.

[그림2]

문제1.

자연수 $\large n$ 에 대해, $\large n$ 의 배수와 $\large \mathit{n}$ +1의 배수를 훅 길이로 가지지 않는 페러스 다이어그램은 몇 개일까? 이를테면 [그림2]의 페러스 다이어그램은 훅 길이 중 6의 배수(6, 12, 18, $\cdots$ )는 없지만 7의 배수(7, 14, 21, $\cdots$ )가 있으므로, $\large \mathit{n}$ =6인 경우 이 조건을 만족하지 않는다.

문제2.

홀수 $\large k$ 에 대해, $\large k$ 의 배수와 $\large \mathit{k}$ +2의 배수를 훅 길이로 가지지 않는 페러스 다이어그램의 개수는 몇 개일까? [그림2]의 페러스 다이어그램은 훅 길이 중 9의 배수와 11의 배수가 없으므로, $\large \mathit{k}$ = 9일 때 이 조건을 만족한다.

+힌트!!

'패러스 다이어그램'의 테두리를 따라 가로랑 세로가 어떻게 반복되는 지를 살펴 본 뒤, 어떤 규칙이 있는지 찾아보세요!

문제 찜하기 목록보기

muse 2017.12.03 11:29:10

(1)번 문제에 대한 관찰입니다.

n=1일 때는 존재하지 않음이 자명합니다.

n=2일 때는 1개밖에 없는 것으로 추정됩니다(■ 한 칸 짜리 모양)

n=3일 때는 4개밖에 없는 것 같습니다.

(한 칸짜리, 가로로 두 칸, 세로로 두 칸, ㄱ자 모양)

좋아요1 댓글수3
- 수학장 2017.12.07 18:34:24
  
  ㄱ자 모양은 존재할 수 없습니다 왼쪽에 정렬되야 하니까여
  
  좋아요0
- 수학장 2017.12.07 18:38:50
  
  5 2 1
  
  2
  
  1
  
  이런 모양은 나올 수 있겠군요
  
  좋아요0
- muse 2017.12.09 09:35:53
  
  네 그 모양 맞습니다.
  
  좋아요0
발밤발밤 2017.12.03 22:12:15 비밀댓글

비밀댓글 입니다.

댓글수1
- 수학장 2017.12.08 18:34:31
  
  문제 푸신 건가요?
  
  좋아요0
수학장 2017.12.09 10:46:07

맨 왼쪽 위의 훅 길이가 가장 길고 그 칸의 훅 길이는 행의 길이가 a, 열의 길이가 b라고 하면 a+b-1입니다. 따라서 a+b-1이 n또는 k보다 작으면 문제 1, 문제2의 조건은 항상 만족합니다.

좋아요1 댓글수1
- muse 2017.12.09 11:19:10
  
  훅 다이어그램에 k의 배수가 없으면, 맨 윗 줄을 제거해도 k의 배수가 없다는 것은 자명합니다.
  
  이 말은 즉, k의 배수가 없는 훅 다이어그램은 다른 k의 배수가 없는 훅 다이어그램의 부분집합이란 것입니다.
  
  또한, k의 배수가 없는 훅 다이어그램을 왼쪽에서 a줄, 위에서 b줄씩 각각 제거했을 때도 이 훅 다이어그램은 k의 배수가 없는 훅 다이어그램이 됩니다. (아니면 비어있는 다이어그램이거나.)
  
  좋아요0
muse 2017.12.09 11:24:23

이것과 비슷한 문제인 것 같은데...

좋아요0 댓글수3
- 여백 패르마 2017.12.09 13:49:14
  
  뭔 문제요??(최단경로??)
  
  좋아요0
- 수학장 2017.12.09 13:49:49
  
  이 최단경로 문제랑 무슨 관련이 있을까요
  
  좋아요0
- 수학장 2017.12.09 13:52:30
  
  그리고 맨 윗쥴을 제거해도 되는 건 맞지만 그 역은 참이 아닙니다. 그러므로 항상 다른 다이어그램의 부분집합은 아니라는 거죠
  
  좋아요0
구머 2017.12.09 15:09:35

문제에 대한 접근을 '다이어그램의 최대 크기'를 알아내는 방향으로 해야 할 듯 합니다..

좋아요1 댓글수1
- 수학장 2017.12.09 15:59:43
  
  최대 크기(행x열)을 알아내면 대칭성과 맨 위에 있는 줄, 맨 왼쪽 줄을 뺄 수 있다는 것을 이용하여 페러스 다이어그램의 수를 많이 알아낼 수 있습니다. 그런데 그게 전부라고는 못하겠군요
  
  더 이상 위쪽이나 왼쪽에 줄을 추가할 수 없는 페러스 다이어그램을 페러스 다이어그램의 기본형이라고 하면 그 기본형은 여러 개가 있을 건데, n에 따라 그 기본형의 개수도 구해야 할 것 같습니다
  
  좋아요0
수학장 2017.12.09 21:32:34

문제 1에서 n=4일 때 정사각격자에서는 6x6 격자일 때가 가장 큰 페러스 다이어그램이었습니다. 제 추측으로는 a+b-1이 n보다 클 때는 ㄱ자 모양만 생기고, nxn격자가 제일 클 줄 알았는 데 아니더군요.

좋아요0 댓글수1
- 수학장 2017.12.10 18:42:08
  
  이걸 일반화해서 n이 4 이상의 정수일 때 기본형을 하나 찾았습니다
  
  좋아요1
구머 2017.12.17 23:30:53

여러분 여기에도 관심좀요..ㅜㅜ

좋아요0 댓글수1
- 수학장 2017.12.18 08:22:25
  
  너무어려워요 ㅠ
  
  좋아요0

muse 2017.12.23 11:48:01

수학장 님의 아이디어를 응용해 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

의 경우가 존재합니다.

좋아요0 댓글수2

수학장 2017.12.23 12:02:45

n+2k가 아니라 n+k 아닌가요

좋아요0
muse 2017.12.23 12:11:25

아 죄송합니다 n+k입니다.

좋아요0

서러서차 2018.01.08 21:47:19

이 문제 새로운 댓글을 본 것이 40일도 넘었네요

# 가장 재미있을것 같던 문제

# 난 왜 잘 안 풀리지

# 이 문제에 조금만 더 관심을

좋아요0 댓글수3
- 김우현 기자 2018.01.09 09:42:08
  
  맞아요, 맞아! 여러분 페러스 다이어그램에도 관심을 가져주세요ㅜㅜ
  
  #내가봐도재밌는문제
  
  #연구원 님 힌트 좀 주세요
  
  좋아요0
- 수학장 2018.01.09 10:11:06
  
  수돌이님이나, 수학자 같은 분들이 푸셨으면 빨리 풀렸을텐데... 그분들은 바빠서 못 하시는 것 같네요
  
  좋아요0
- 여백 패르마 2018.01.09 12:34:51
  
  저는 이문제에 별로 관심이 없어서...이번 국가수리과학문제는 풀어보려고요.(저 대수 팬이거든뇨.)
  
  좋아요0
harryahn 2018.03.02 10:18:00

머리가 잘 안돌아가네요 ㅠㅠ 여러분 이제 여기에는 관심이 없나요... 관심을 가져주세요!

좋아요0 댓글수1
- 김우현 기자 2018.03.02 10:26:08
  
  옳소옳소! harryahn 친구 쵝오!
  
  좋아요0
4321 2018.04.15 22:05:06

위에서    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 사이즈의 정사각형은 만들 수 있네요.

아마도 제 생각에는 이 경우가 가장 큰 경우 같은데..

이 모양이 성립한다는 증명은 시간상 나중에 해서 올려야 할 것 같습니다. ㅠㅠ

좋아요1 댓글수1
- 김우현 기자 2018.05.08 18:33:28
  
  좋은 관찰이에요! 위에 백진언 연구원님의 힌트를 추가했으니, 참고해 보세요!
  
  좋아요0
수학장 2018.05.22 15:04:59

규칙은 (오른쪽 칸의 수)+(아래 칸의 수)-(오른쪽 아래 칸의 수)라는 겁니다. 만약 오른쪽이나 아래에 칸이 없으면 오른쪽 칸(또는 아래쪽 칸)+1입니다.

좋아요0 댓글수0
모두다같이 2018.07.27 21:50:00

다이어그램 안에 있는 가장 큰 수를 M 이라 하면

자연수 n 에 대해

M = n 인 다이어그램 개수는

총 2^n-1개인 것 같아요.

좋아요0 댓글수0
jeuno 2018.10.17 22:31:18

수학장님이 그려주신 그림이 가로로 왼쪽부터 1, 2, 3... $n-1$ 개씩 같은 높이를 가진 뭉텅이, 세로로 위쪽부터 1, 2, 3... $n-1$ 개 씩 같은 너비를 가진 뭉텅이로 이루어져 있다고 볼 수 있습니다, 즉 각 뭉텅이의 가로와 세로는 $(n-a), a$ (a는 자연수)라고 볼 수 있습니다. 여기에 추가적인 사각형을 추가하면 반드시 어느 한 뭉텅이에서 $n$ 을 가지는 곳이 존재한다. 그래서 문제 (1)에서는 이 모양이 최대라고 생각합니다.

그리고 최대인 모양에서 아무 사각형이나 골라 그 사각형부터 오른쪽 아래부분만 뜯어내면 뜯어낸 부분도 항상 문제(1)의 조건을 만족합니다. 그러니까 $\sum_{k=1}^{n-1} (n-k)(k+1)k \frac{1}{2}$ 이 최대일때 전체 사각형 개수니까 저 만큼의 가능성이 있는데 중복을 가지죠, 그래서 저 개수에서 중복하는 걸 세서 빼면 답이 나온다고 생각합니다만 아직 중복하는 개수는 찾지 못했습디다.

도움이 되는 글이었으면 좋겠네요

좋아요0 댓글수5
- jeuno 2018.10.17 23:35:16
  
  제 계산 대로라면
  
  문제 (1)은
  
  중복이 $\sum_{k=1}^{n-2}k$ 개라서
  
  $(\sum_{k=1}^{n-1}(n-k)(k+1)k\frac{1}{2})-\sum_{k=1}^{n-2}k$ 개로 개수가 나오는 것 같습니다
  
  계산 결과는 $\frac{-3n^{4}+18n^{3}-19n^{2}+44n-26}{24}$ 개가 정답인 것 같습니다 계산 지적이나 오류있다면 알려주세요
  
  좋아요0
- Poincaré12 2018.10.19 16:17:03
  
  자세히 보지는 않았지만 $\frac{-3n^{4}+18n^{3}-19n^{2}+44n-26}{24}$ 는6부터는 음수가 되는데요..?
  
  좋아요0
- jeuno 2018.10.19 23:13:11
  
  음... 시그마 계산중 오류일까요, 아니면 계산식 자체에 오류였을까요... 시그마 식 자체에서도 6일 때 음수가 나오나요?
  
  좋아요0
- 누군가 2018.10.21 23:20:59
  
  시그마 계산만 다시하면 이렇게 나옵니다. $\frac{(n-1)n(n+1)(n+2)}{24}-\frac{(n-2)(n-1)}{2}=\frac{n^4+2n^3-13n^2+34n-24}{24}$
  
  좋아요0
- jeuno 2018.10.22 23:17:06
  
  아무튼 최대가 되는 그림이 위쪽에 있는 그림들이 맞다면 최대는 이로 추측됩니다
  
  좋아요0