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

Problems

폴리매스 문제 보기

문제

[국가수리과학연구소] 국26. 배부른 아즈텍 다이아몬드

2019.02.01

같이 풀어볼까?

네이버밴드 구글플러스

 

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

 

'아즈텍 다이아몬드'는 정사각형으로 만든 계단 4개를 90º씩 회전시킨 뒤 맞대서 만든다. 아래 그림처럼 가장 아랫변에 정사각형 5개가 있는 계단 4개로 만든 아즈텍 다이아몬드를 '크기가 5인 아즈텍 다이아몬드'라고 부른다. 아즈텍 다이아몬드를 도미노(정사각형 2개를 이어 붙인 모양)로 채우는 방법의 수는 잘 알려져 있다. 단, 이 경우 돌리거나 뒤집어서 같은 모양을 구분해서 센다. 

 

 

[문제]

 

크기가 15인 아즈텍 다이아몬드를 도미노로 채우는 방법의 수를 구하라. 단, 돌리거나 뒤집었을 때 같으면 하나로 센다.

 

+추가 문제 

아즈텍 다이아몬드의 크기가 더 큰 경우에는 어떻게 계산할 수 있을까?

 

※대한수학회 2번 문제가 크기가 7인 아즈텍 다이아몬드를 도미노로 채우는 문제입니다. 프로그래밍을 이용하돼, 새로운 풀이 방법을 생각해보세요! 

댓글 24

  • muse 2019.02.01 17:02:28

    대한수학회 2번 문제에서 계산한 데이터입니다.

    n값
    1 1
    2 3
    3 16
    4 168
    5 4394
    6 265422
    7 33605540

    n=15 답:166153499473114484112977761122098384

    해결했습니다.

    좋아요0 댓글수2
    • mjh 2019.02.13 22:01:51

      대한수학회 2번 문제와 같은 방법으로 계산한 것인가요?

      좋아요0
    • muse 2019.02.14 10:55:58

      아니요. 다른 방법으로 계산했습니다.

       

      좋아요0
  • muse 2019.02.01 17:20:57

    돌리거나 뒤집는 것을 따로따로 셀 때 나올 수 있는 가짓수는 2^{120}임이 증명되어 있습니다. 또한, 한 모양은 돌리거나 뒤집어도 아무리 많아야 8개의 모양을 가질 수 있으므로 이 문제의 답은 2^{117} 이상 2^{120} 이하입니다. 그리고, 크기가 1~7일 때의 답의 추이를 관찰한 결과 답이 점점 2^{{{n(n+1)} \over {2}}-3}에 가까워졌습니다. 2^{117}이 36자리 수(링크, 166153499473114484112975882535043072)이므로 답도 약 36자리 수일 것으로 추정됩니다. 

    이는 백트래킹으로는 문제를 시간 내에 해결할 수 없음은 물론 백트래킹이 아니더라도 어지간한 알고리즘으로는 해결할 수 없음을 의미합니다.

    해결할 수 있는 방법으로는 Dynamic Method나 점화식 정도가 있겠네요. 그런데 설령 방법을 찾는다 하더라도 python이 아닌 이상 overflow가 일어나(c++의 경우 최대 2^64-1까지 저장할 수 있는 자료형을 기본으로 제공합니다.) 코드를 짜는 것도 매우 힘들 것 같습니다.

     

    게다가 돌리거나 뒤집는 것도 생각해야 하니...

     

    방법 1.

    돌리거나 뒤집었을 때 1가지 경우가 나오는 모양은 만들 수 없습니다. (가운데 2x2 모양과, 염색 문제를 생각하면 증명은 쉽습니다)

    따라서 돌리거나 뒤집었을 때 2가지가 나오는 경우, 4가지가 나오는 경우, 8가지가 나오는 경우로 나눌 수 있습니다.

     

    1) 2가지가 나오는 경우: 좌우대칭이고 180도 돌렸을 때 같은 모양( H )뿐입니다. (좌우대칭이 아니고 90도 돌렸을 때 같은 모양(卐)인 경우도 가운데 2x2를 생각하면 만들 수 없다는 것을 알 수 있습니다.)

    2) 4가지가 나오는 경우: 좌우대칭이 아니고 180도 돌렸을 때 같은 모양인 경우( N )와, 좌우대칭이고 180도 돌렸을 때 같은 모양이 아닌 경우( ㅠ )뿐입니다.

    3) 8가지가 나오는 경우: 좌우대칭도 아니고 180도 돌렸을 때 같은 모양도 아닌 경우( P )뿐입니다.

     

    (1), (2), (3)의 개수를 모두 세서(이때 돌리거나 뒤집어서 같은 모양도 여러 번 세기 때문에 (1)은 2번, (2)는 4번, (3)은 8번 세어졌겠죠) (1)/2+(2)/4+(3)/8 하면 됩니다. 

    또한 우리는 (1)+(2)+(3)=2^120이라는 것도 알고 있습니다.

    문제는 이걸 언제 다 세냐는 거지만요...

    p.s. 대각선을 기준으로 대칭인 모양을 생각할 수도 있습니다. 오른쪽 위를 향하는 화살표 같이요. 하지만 이런 모양도 가운데 2x2 사각형을 생각하면 존재하지 않음을 쉽게 증명할 수 있습니다.

     

    이제 각 경우별로 생각해 봅시다.

    1. H형 모양

    좌우대칭인 모양을 구하는 방법에서, 대칭 축은 x축 또는 y축 방향이겠네요. 이때 그 대칭 축을 x축으로 고정시킨다면 한 번씩만 세지겠죠. 그럼 코드를 복잡하게 할 필요 없고, 시간도 단축됩니다. 일석이조군요. 점대칭인 모양을 구하는 방법은, 왼쪽 반절을 구해서 오른쪽 반절에 거꾸로 붙여넣기한다고 생각하면 될 것 같습니다.

    여기서 질문.

    선대칭형 모양은 왼쪽 반절을 좌우만 뒤집어 오른쪽에 붙여 넣는 거고, 점대칭형 모양은 왼쪽 반절을 좌우, 상하 모두 뒤집혀 오른쪽에 붙여 넣는 거네요.

    그럼 왼쪽 모양은 가로 축에 대해서 대칭이라는 결론을 얻을 수 있습니다.

    따라서 우리가 할 일은 왼쪽 위 부분만 만든 뒤, 그것을 상하로 뒤집어 왼쪽 아래 부분을 채워 왼쪽 반절을 얻고, 그것을 좌우로 뒤집어 오른쪽 반절에 채우는 것입니다.

    또한 대각선을 기준으로 대칭이 존재하므로 반절로 나누어야 하겠죠.

    또한 여기서는 돌리거나 뒤집는 것을 고려하지 않아도 되니 단순 백트래킹으로 짜도 시간이 크게 모자라지 않을 것으로 보입니다. 안 되네요. bit dynamic으로 해결하겠습니다.

    그럼 당장 시작해 보죠.

    249339936384가 나오네요. 이제 이것을 2로 나누면,

     결과: (H)/2 = 124669968192

     코드: 여기 있습니다.

     

    2. ㅠ형 모양

    이런 모양을 어떻게 만들어야 할까요?

    단순하죠. 왼쪽 반절을 구한 뒤 그대로 좌우 반전시켜 오른쪽에 붙여 넣으면 되겠습니다.

    아까의 코드를 조금만 수정하면 되겠네요.

    계산해 보겠습니다.

    5607636598784 가지가 나옵니다.

    따라서, 이 중에서 좌우대칭인 것의 개수는 124669968192개이므로, 좌우대칭이 아닌 것의 개수는 5482966630592개 입니다.

    이제 이것을 상하로 뒤집은 것까지 세 졌을 거니까 2로 나누어 주면 2741483315296개이겠네요.

    결과: (ㅠ)/4=2741483315296

    코드: 여깁니다.

     

     

    중간 점검. (1) = (H) = 249339936384

    (2) = (ㅠ) + (N) = 10965933261184 + (N).

     

    3. N형 모양.

    가장 까다로운 부분입니다.

    어떻게 구할 수 있을까요?

    음... 아무래도 왼쪽 반절을 만든 뒤 상하-좌우 반전시켜 오른쪽에 붙여야 할 텐데요,

    이때 가운데 연결부위가 상당히 중요합니다.

    지금까지는 모양을 만들 때 오른쪽으로 한 칸 씩 삐져나오는 파트가 있어도 무시할 수 있었는데, 이젠 그렇게 할 수 없습니다.

    따라서 조금 더 신경써 줘야겠죠.

    먼저 오른쪽으로 삐져나갈 것들을 미리 정해 준 뒤, 그 칸들은 생각하지 않고 나머지를 계산해야겠죠.

    당연히 삐져나간 것들은 상하 대칭적이여야 합니다. 그래야 왼쪽과 오른쪽의 연결이 가능하니까요.

    이제 해 봅시다.

    3564083308544가 나옵니다.

    점대칭 모양이 3564083308544개 라는 것인데, 이 중에서 좌우대칭인 것은 빼기로 했으므로 249339936384개를 빼 줍니다.

    남은 것의 개수는 3314743372160개입니다.

    그런데 좌우 대칭인 것들이 섞여 있으므로 2로 나누어 주면 1657371686080개입니다.

    또한 점대칭 모양을 자르는 방법은 가로로, 세로로 두 가지가 있으므로 다시 2로 나누어 주면 828685843040입니다.

    결과: (ㅠ)/4=828685843040

    코드: 여깄습니다.

    따라서 (ㅠ)는 3314743372160이네요.

     

    이상의 결과를 종합하여 (1)은 249339936384, (2)는 14280676633344입니다.

    (3)을 구해 볼까요? (3)은 2^120-(1)-(2)=

    1329227995784915872903792530263774848

    입니다. 즉 (3)/8은

    166153499473114484112974066282971856

    즉 (1)/2+(2)/4+(3)/8=

    166153499473114484112977761122098384

    입니다. 따라서 전체 개수는

    166153499473114484112977761122098384
    좋아요0 댓글수5
    • 김우현 기자 2019.02.18 18:58:40 비밀댓글
      비밀댓글 입니다.
    • muse 2019.02.18 19:22:58 비밀댓글
      비밀댓글 입니다.
    • 출제자(국) 2019.02.18 20:33:48

      출제자입니다. 이제 시간이 어느 정도 됐으니 풀이를 친구들과 공유해서 검증하는 건 어떨까요? 풀이가 나온지 꽤 되어서 어떻게 풀었는지 궁금해 하는 친구들도 많을 거 같아요!

      좋아요0
    • muse 2019.02.18 20:52:32

      네. 

      좋아요0
    • 출제자(국) 2019.04.22 17:27:20

      안녕하세요 muse 친구! 접근 방식을 문제에 맞게 잘 한 것 같아요. 이 문제는 사실상 muse 친구가 푼 것으로! (짝짝!!) muse 친구의 접근 방식이 궁금한 친구들을 위해 조만간 muse 친구의 풀이를 설명한 글을 올릴게요.

      다만 프로그램이 정확한지를 확인해야 하는데, 제가 따로 프로그램을 만들어서 돌려보니 답이 다르게 나와요. muse 친구가 시간이 나는 동안 n이 작은 값일 때 프로그램으로 계산한 값이 표에서 나오는 값과 일치하는지를 확인해보면 디버깅을 하는 데 도움이 될 것 같아요. 오늘 생각보다 바빠져서 코드를 한줄씩 보지는 못했는데, 시간이 나는대로 틈틈히 봐서 좀 더 디테일한 피드백을 줄게요~

      좋아요0
  • 수학자 2019.02.01 19:35:38

    일단 답 자체가 매우 크다는 걸 주의해야겠군요. 답이 2^{117} \leq ans \leq 2^{120}라는 걸 생각하면, c/c++로 코딩할 때 long long(64비트) 범위조차 충분하지 않을 것 같습니다. 큰 정수를 다루는 새로운 자료형을 선언해야 할 수도 있습니다. g++ 컴파일러 환경에서는 __int128을 제공하기는 하지만, __int128 정수를 출력하는 것도 좀 까다롭습니다. python으로 코딩하는 게 좀 더 편할 수도 있겠네요. python의 경우 100자리수 이상의 큰 정수도 정확하게 표현해줍니다.

    좋아요0 댓글수5
    • 1975fanboi 2019.02.01 20:06:52

      Chinese remainder theorem을 이용하면 C++로도 코딩할 수 있지 않을까요? 충분히 큰 여러 소수에 대해 (대충 18자리) 전체 수의 나머지를 계산하고, 역으로 나머지 정리로 원래 수를 구할 때만 큰 정수를 다루는 언어로 계산하면 될 거 같습니다

      좋아요0
    • muse 2019.02.02 11:54:08

      64비트 안에서 해결할 수 있습니다. 그러고 나면 계산 몇 개 정도만 울프럼알파로 해결해 주면 됩니다.

      좋아요0
    • muse 2019.02.02 11:54:53

      그리고 python의 경우 매우 느리다는 것도 감안해야죠.

      좋아요0
    • mjh 2019.02.08 22:44:23

      어떻게 64비트 안에서 해결할 수 있나요?

      unsigned long long도 0 ~ 18446744073709551615인데요.

      좋아요0
    • muse 2019.02.09 09:15:43

      부분부분 나눠서 계산하면 되겠죠?

      좋아요0
  • sincostan 2019.02.07 21:33:56

    muse님의 데이터에서 무슨 규칙이라도 찾을 수 없을까요?

    좋아요0 댓글수1
    • sincostan 2019.02.07 21:36:24

      제가 코딩이 좀 안되서 규칙을 찾는데 n값이4부터는 너무 수가 커져서 어렵습니다.

      좋아요0
  • mjh 2019.02.08 23:00:08

    완전탐색보다 더 수학적인 방법은 없을까요?

    좋아요0 댓글수2
    • 디듀우 2019.02.10 21:12:24

      대칭을 이용하면 되지 않을까요?

      좋아요0
    • sincostan 2019.02.12 22:27:48

      제가 직접그려도 보았는데 크기가 n인 아즈텍 다이아몬드와 크기가 n-2인 아즈텍 다이아몬드와 연관이 있는것 같아요.

      그런데 어떤 관계인지는......

      좋아요0
  • 인천 오일러 2019.02.23 22:24:25

     도움이 될지는 모르겠지만, n-아즈텍 다이아몬드의 가운데 라인을 타고 1-아즈텍 다이아몬드 n개를 배치하면 양옆의 부분들이 n-1 아즈텍 다이아몬드 절반씩으로 보입니다. 이를 잘 이용하면 경우의 수를 쉽게 계산 할 수도 있을 것 같습니다.  부분들의 경계에 걸쳐 채울 수도 있어서 복잡해집니다.

    좋아요0 댓글수0
  • muse 2019.03.21 20:10:15

    원래 문제에 대한 풀이를 제출한 지 2달이 되어가도록 정답 여부를 알 수 없습니다.

    혹시 정답 여부가 확인이 되었으면 알 수 있을까요?

    좋아요0 댓글수2
    • 김우현 기자 2019.03.25 16:23:18 비밀댓글
      비밀댓글 입니다.
    • 출제자(국) 2019.04.22 10:01:28

      안녕하세요 muse 친구!

      피드백이 늦어서 정말 미안해요. 최근 한달 동안 육군훈련소를 가게 되어서 더욱 답장이 늦어졌네요. 문제를 열심히 풀었는데 오랜 기간동안 피드백이 없어 아쉬운 마음이 클 거 같아요. 김우현 기자님 말씀대로 muse 친구의 프로그램을 다른 친구들이나 muse 친구 스스로 교차검증을 하는 걸 의도해서 추가 코멘트를 하지 않았는데, 이런 의도를 muse 친구에게 전달했다면 muse 친구가 안 답답해하지 않았을까 후회하고 있어요 ㅜㅜ 앞으로는 친구들의 활동이 없는 풀이는 며칠 내로 피드백을 줘서 오랫동안 기다리는 일이 없도록 할게요!
      muse 친구의 프로그램에 관한 피드백은 프로그램을 면밀히 확인한 뒤 대댓글로 달아줄게요!

      좋아요0