주메뉴바로가기.. 본문바로가기

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일 때 이 조건을 만족한다.

 

+힌트!!

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

 

댓글 37

  • 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 친구 쵝오!yes

      좋아요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 인 다이어그램 개수는 

    총  2n-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