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

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

 

댓글 28

  • 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의 조건은 항상 만족합니다.

    좋아요0 댓글수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

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

    좋아요0 댓글수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 사이즈의 정사각형은 만들 수 있네요.

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

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

    좋아요0 댓글수0