폴리매스

인절미 2017.02.02. 11:29

돌리거나 뒤집었을때 같아지는 것은 다르게 세는 건가요?

오이 2017.02.02. 14:58

기본형으로 만들어서 규칙을 찾아야 할것 같네요.

일단 제생각은 가짓수=전체 사각형 개수/4 이고요. 이 규칙이 맞으면 답은 28가지 인것 같습니다.

수학 2017.02.02. 15:36

제 생각인데 저거 112개를 중간으로부터 4조각으로 나누고 그 1조각에 경우의 4승을하면 나오지 않을까요?

아마 4조각으로 생각 했을때랑 2조각으로 나뉘어 졌을때 온전히 그래야 할때랑 경우가 나뉘는 경우를 생각해야 하는걸까요?

프로벤젠 2017.02.02. 17:07

작은 부분부터 풀어 나가야 되지 않을까요?
12칸짜리 십자가부터 확장시켜나가면서요.

ssamtkwon 2017.02.02. 20:12

일단 귀퉁이 8조각을 배열하는 방법은 3가지가 있는 것 같습니다.
1. 2쌍이 서로 같은 도미노로 연결되어있는 것
2. 3쌍이 서로 같은 도미노로 연결되어있는 것
3. 4쌍 모두가 서로 같은 도미노로 연결되어있는 것

1과 2의 경우에는 다시 더 작은 마름모로 바뀝니다.

85 2017.02.02. 20:38

12칸짜리 십자가에서(뒤집거나 돌렸을떄 같아지는것 제외)
1.2쌍이 같은 도미노로 연결되어있는것은 1가지.
2.3쌍이 같은 도미노로 연결되어있는것은 1가지
3.4쌍이 같은 도미노로 연결되어있는것 2가지기떄문에
12칸에서는 4가지 방법이 있습니다.
일단 이것부터 점점 크게 올리면 되겠네요.

joshua navey 2017.02.02. 22:45

너무 어렵다....

수학 2017.02.03. 15:15

죄송한데 도미노를 옆으로 90도 회전시켜서 넣어도 되나요?

ssamtkwon 2017.02.03. 19:21

증명은 못했지만 제 생각에는 이 도미노로 사각형채우기 문제랑 줄 하나로 모든 사각형들을
연결하는 문제랑 비슷한 것 같습니다.
일단 줄 하나로 모든 사각형들을 연결한 뒤 그 줄을 사각형 2개 길이로 자르면 도미노랑 같아지는
것 같습니다

오딧셈 2017.02.03. 20:49

어렵다....

hyungjoon0546 2017.02.04. 15:22

아예 점화식 세워서 노가다하면 될 것 같은데요?

golden ratio 2017.02.05. 01:38

제 생각에는 아예 네 귀퉁이에서 1×2 형태를 잘라내고 원래모양과 비슷한 형태가 되도록 모서리에서 겉에 있는 조각을 잘라내서 원래모양과 꺾이는 부분이 1개 적도록 만들어 (1+2+...+6)×4=84개를 만들고 이 형태에서 이것을 계속 반복하면 (1+2+3+4+5)×4=60개, ...... ,(1+2)×4=12개 형태가 되고 이것을 기본형으로 해 여기서 규칙을 찾으면 될 것 같습니다.

...□□
□□□□ 이 형태를 기본형으로 가짓수와 규 □□□□ 칙을 찾을 수도 있을 것 같습니다. ...□□

돌리고 뒤집어서 같은 경우를 제외하면 A1=3 나오는데요

부엉이 2017.02.05. 10:41

체스판처럼 하면 될것 같은데요? 어차피 대칭이니까 한가지만 해도 될 것 같네요.

85 2017.02.06. 20:07

12개일떄 3가지, 24개일떄 6가지...즉 40개일떄만 알면 되는데... 하... 공식으로 어캐하지...

수학자 2017.02.06. 21:25

     ──
   ────
││────
││────
   ────
     ──

이렇게 표현하면 좀 더 알아보기 편할 것 같네요
.이랑 □가 크기가 달라서 좀 깨질 것 같아요

파인만짱 2017.02.06. 23:13

제 생각으로는 가로 세로로 14칸짜리가 있다면
중간에 가로 세로로 12칸씩 있는 같은 모양의 도형을 기준으로
그 안 다 채워질때, 안 채워질때로 경우를 나누어
점화식으로 푸는 곳이 제일 쉬울 듯 합니다.
다른 의견이 있으면 말씀해주세요.

즉, 85님처럼 12칸짜리와 24칸 사이의 관계를 점화식으로 찾는 거죠.

수학자 2017.02.07. 10:09

지난 번 채우기 문제의 경우 돌리거나 뒤집는 걸 고려할 필요가 없어서 프로그래밍으로 구현하는 게 아주 어렵진 않았는데, 이번엔 좀 어렵네요.
지금 시도하려는 부분은 일단 돌리거나 뒤집어서 다른 것을 다르게 센 경우의 수를 센 뒤(A), 좌우(B) 또는 상하(C,상하 좌우 모두는 D)로 뒤집어서 같은 선대칭의 경우의 수를 세서, (A-B-C-D)/8+B/4+C/4+D/2를 구하는 것입니다.
일단 오늘 내로 저 프로그래미을 완료하는 것이 목표입니다. 답을 알아내면 일반항은 알 수 있을 것 같고 증명만이 남을 것 같습니다

수학자 2017.02.07. 19:19

돌리거나 뒤집은 것을 다른 경우로 계산했을 때 경우의 수는 2^(n(n+1)/2)입니다.(n=1~7 확인함)
다른 경우는 프로그래밍이 완성되면 추후 올리도록 하겠습니다.

수학자 2017.02.07. 21:49
그리고 이로부터 문제의 정답이 33554432(=2^25) 이상 134217728(=2^27) 이하임을 알게 되었습니다...

kjinwoo03 2017.02.07. 21:57

그 경우의 수에서 n이 뭐예요?

제생각에는 위에 golden ratio님 처럼 기본모형을
00┌┬┐
┌┼┼┼┐
├┼┼┼┤
└┼┼┼┘
00└┴┘로 해야 할것 같네요
이렇게 하니까 사각형 갯수가 12개일때 3가지

24개일때 10개??

녹차쫑 2017.02.08. 13:13

아니면 큰 조각을 십자로 잘라서 합동인 4조각으로 나눈후 다른 조각들과 겹치는 개수대로 세어나가도 괜찮지 않을까요??

각 조각 내에서 가능한 것들은 가짓수를 구한 뒤 배열가짓수를 더해주면 될것 같구요.

각 조각 내에서 가능한 것들의 배열가짓수는 각 조각마다 n가지씩 가능하다 할 때 (n-4)! 개 일 것 같아요.

쏘이 2017.02.08. 14:13

알고리즘이 있을까...하고 생각도 한번 해 봤습니다..(있겠죠..?)
만약 알고리즘이 있다면, 개수가 늘어감에 따라서 규칙이 있다는 뜻이니까, 작은 것부터 해 보는 게 좋을 것 같아요..

그래서 찾은 방법이 2개가 있는데,
하나는 4개짜리, 6개짜리, 8개짜리…얘네들 사이의 규칙을 찾고, 가장 중간의 4개가 가로로 잘렸을 때, 세로로 잘렸을 때로 나눠서 4개짜리, 6개짜리(예상으로, 최소의 규칙을 가져야 할 첫항)로 채워넣기를 하는 방법입니다.
두번째 방법은 4개짜리, 4개짜리 4면에 2개씩 붙인 것(a₂),a₂에 2개씩 붙이고, 4개를 꼭짓점에 붙인 것(a₃)…이렇게 규칙을 찾는 방법입니다.

오류가 있다면 알려주세요!!

85 2017.02.08. 19:08

잠시 쉬었는데요. 일단 간단하게 계산을 한번 해보았습니다.
수학자님처럼 풀수없는 사람이라서;;
일단 ssamtkwon님 말대로하면.
1번경우의 규칙은.
마름모 모양이 4개일경우 1번쨰,12개일경우 2번쨰, 24개일경우 3번쨰라고 하면
(1번쨰,2번쨰 제외)
3번쨰 마름모의 1번경우는 2가지가 나옵니다.
4번쨰 마름모의 1번경우는 6가지가 나오고요.
일단 확실한 공식은 모르겠지만
자신의 차례의 전전번쨰 마름모의 가짓수의 전체 개수×2가 나옵니다.
왜냐하면 1번쨰 2번쨰 경우에는 단일겨우만 생각했는데 3번쨰 4번쨰가 되면 양쪽이 다르므로 뒤집어도 똑같은 모양이 나오지 않는다는 것을 알수가 있었습니다.

c_____x 2017.02.09. 10:43

체스판이라고 생각하고, 두 칸짜리 도미노 중 한 칸을 검은색 다른 한 칸을 하얀색이라고 해 보세요. 가로 도미노 중 검은 칸이 오른쪽일 때와 세로 도미노 중 검은 칸이 위쪽에 있을 때 그 검은 칸의 위치를 표시해보면, 저번 문제와 거의 완전히 똑같습니다. (러시아인 좌표계라 불리기도 하는데, 135도 돌려서 표시한 위치의 높이를 생각해보면 더 확실한 규칙이 보입니다.)

85 2017.02.09. 16:35

제가 지금책보고 안건데...64칸짜리 체스판을 2칸짜리 도미노로 채우는 방법은 12,988,816가지랍니다 뒤집어서나 돌려서 같은모양이되는거 포함 하는건지 안하는건지는 모릅니다

leo051213 2017.02.09. 17:27

제 생각에는 112를 8로 나눠서 14가지가 정답이 아닐까 싶은데요.

겹치지 않는다면 가짓수가 많이 작아질 것 같네요.

수돌이 2017.02.10. 10:38

아마도 돌리거나 뒤집어서 같은 모양이 된다해도 그 둘은 서로 다른 모양으로 처리해야 할 것 같습니다.
대한수학회 1번문제도 그랬거든요.

whqkrtk04 2017.02.10. 14:54

둘레의 경우(귀퉁이) 시작이 세로로 결정되면 다음 귀퉁이까지는 방향이 일정하게 결정되는 것 같습니다.

whqkrtk04 2017.02.10. 14:56

위쪽이 세로로 채워지면 양쪽까지도 세로로 채워지는 것이죠.
근데 사진을 못 올려서 답답하긴 하네요ㅠㅠ

수학더쿠 2017.02.10. 15:03

그리고 가운데 쪽에 가장 큰 정사각형(8 * 8)을 만들고 나머지 귀퉁이 부분을 따로 생각하면 답은 2의 16승이 되지 않을까 생각합니다.

앗! 제가 실수를 하나 한 것 같습니다. 즉 정답은 2의 16승이 아닙니다.

그리고 whqkrtk04는 수학더쿠와 같은 사람입니다

tommy 2017.02.13. 20:56

흠.. 맨 위 블록 2개를 각각 다른 도미노 블록 2개가 메웠다고 생각하면, 저 전체 마름모의 윗 두 변에 있는 사각형들이 각각 1개씩만 남게 되면서 전체 마름모의 대각선 길이가 2 줄어들겠군요. 그럼 재귀함수라는 말인가요..? 마름모의 대각선 길이=x라고 하고, 저 마름모를 도미노로 채우는 가짓수를 f(x), 맨 위 블록 2개를 메웠을 때 도미노로 채우는 가짓수를 g(x)라 하면, f(x)=g(x)+f(x-2)가 되네요. 문제에서 x=14니까, 답은 f(14)=g(14)+f(12)=g(14)+g(12)+f(10)=...=g(14)+g(12)+g(10)+g(8)+g(6)+g(4)+f(2)가 되겠군요. 문제는 g(x)인데.. 어쨌든 이것만 해결하면 되겠군요(별로 도움이 안 되나요?)

아 근데 올리고 보니 whqkrtk04 님과 같은 의견이네요ㅠ

수돌이 2017.02.14. 20:49

"돌리거나 뒤집어서 모양이 같아지면 하나로 센다"
[이 조건을 제외할 경우]에 한해 문제를 해결하였습니다.
답은 수학자 님이 코딩을 통해 제시해주신 2^{n(n+1)/2}개를 수학적으로 증명했습니다.

증명이 길으므로 저의 블로그에 올려놓았습니다.
http://blog.naver.com/dillon0108/220935388663
이렇게나 아름다운 정답과 풀이가 있는데...ㅠ
돌리거나 뒤집어서 같아지면 하나로 세는 건 정말 어려운것 같습니다 (아직 미해결)

수학책갈피 2017.02.15. 13:34

수돌이님의 풀이를 응용하여 문제에대한 접근을 완성했습니다.
의견이나 진척이 있으시면 댓글 바랍니다.

<풀이의 구조>

(참고로 n은 가장 긴 변의 반입니다, 즉 문제에서는 n이 7입니다.)
STEP1.대칭이 2개 또는 4개 인 것을 찾는다.
-대칭축 한개를 기준으로 한쪽을 수돌이님 풀이와 비숫하게 채워주면 될것 같습니다.
허나, 대칭축에 걸쳐 생기는 매칭(matching)이 조금 까다로울 것 같습니다.
-이것을 찾고 a_n이라고 놓습니다.

STEP2.대칭이 4개인 것을 찾는다.
-같은 방식으로 대칭축 2개를 기준으로 한 영역만 채워주면 자동 결정됩니다.
-이것을 찾고 b_n이라고 놓습니다.

STEP3.답을 구해냅니다.
-수돌이님의 답인 2^n(n+1)/2에서 돌리거나 뒤집어서 같은 것을 제외시켜주면 됩니다.
-먼저, 2^n(n+1)/2를 S라고 놓습니다.
i)대칭이 존재하지 않는 경우는 S-a_n입니다.
이경우에는 돌려서 같은 경우 4번, 뒤집은 후 돌려서 같은 경우가 4번이므로
(S-a_n)/8을 하면 무방합니다.
ii)대칭이 2개 존재하는 경우는 a_n-b_n입니다.
이러한 경우 돌려서 같은 경우는 2번 뒤집은 후 돌려서 같은 경우가 2번입니다.
따라서 (a_n-b_n)입니다.
iii)대칭이 4개 존재하는 경우는 당연히 b_n입니다.
또한, 같은 경우가 존재하지 않습니다.
따라서 b_n입니다.
-모든 값을 다 더해보면 (S+a_n+6*b_n)/8 이 됩니다.

<이 풀이에서의 문제점 또는 앞으로 밝혀야 할것>
-일반적인 결과가 아닐수도 있습니다.제가 가장 싫어하는 일반성이 없는 값이 나오면 정말..
-a_n과 b_n을 구하는 방법에 대해서는 현재 연구하고 있습니다.
-이 방법으로 풀릴지에 대한 증명은 존재하지 않습니다.(별로 의미 없음)

의견 있으시면 달아주시기 바랍니다.

ssamtkwon 2017.02.15. 15:05

일단 수돌이님의 접근에 있는 답들을 조건에 따라 분류한 뒤 그 조건에 따라 몇 가지로 뒤집을 수 있는지를 구하고 나서 그 숫자로 나누어주면 되지 않을까요?

수돌이 2017.02.16. 10:49

C언어 코딩을 통해 최종 답을 구했습니다. 3362만9173가지 입니다.
이제 수학적으로 증명하는 일만 남았습니다.

블로그 링크:
http://blog.naver.com/dillon0108/220936698141

85 2017.02.16. 14:31

1. 90도 회전하여 모양이 같다.(점대칭이다)
2.180도 회전하여 모양이 같다.(점대칭이다)
3.270도 회전하여 모양이같다.(점대칭이다)
4.좌우 대칭이다.(선대칭이다)
5.위의 조건중 2개에 해당된다.(점대칭을 2개이상 쓸순 없다)
이 5가지의 경우에 해당하는것을 규칙을 찾으면
문제가 해결될것 같습니다!

5의경우에 해당하는것은 총 3가지입니다. 

수돌이님의 풀이에 따르면 n이 2일경우 포함안하면 8가지. 포함하면 3가지이고요
3일경우 포함 안하면 64가지 포함하면 17가지입니다.
자세한 것은 수돌이님의 블로그를 보시기 바랍니다.

n이 2일경우
1번의 경우 1가지
2번의 경우 3가지
3번의 경우 1가지
가 나왔는데...
2번과 4번의 경우를 같은걸로 생각해야 하는지 모르겠습니다...

85 2017.02.17. 09:40

선대칭4형만으로만 해도 규칙이 안나오느까 뭐라 증명을 할수 없네요.,

자유인 2017.02.26. 12:48

안녕하세요. 초등학교 3학년 윤준환이라고 합니다.

Lucky star 2017.05.18. 23:05

음...

문제는 묻혔지만...

일단 수학자님, 수돌이님의 의견과 같이 돌리거나 뒤집지 않았을 때 가짓수는 268 435 456가지입니다.

하지만 돌렸을때, 뒤집었을때를 계산해준다면...

크게 6가지 경우가 있습니다.

(선: 선대칭, 점: 180도 점대칭, 90점 : 90도 점대칭)

(1) 선+90점 : 아무리 돌려도 똑같기 때문에 1가지. (┼모양)

(2) 선+점 : 2가지. (H모양)

(3) 선 : 4가지. (ㅠ모양)

(4) 90점: 2가지 (卐 모양)

(5) 점: 4가지 (N모양)

(6) 일반: 8가지 (P모양)

이제 이 각각의 경우만 구하면 끝나겠네요!!!

지금 프로그램을 돌리고 있습니다.

앞에 댓글 안 봤습니다

모서리부터 채워나가면 모서리부터 중심까지 4개의 층이 생기는데 각 층마다 도미노를 놓을 수 있는 가짓수가 가로와 세로 2가지가 되네요

따라서 2^4=16가지 아닌가요?

무식하게 프로그램을 짰더니 n=7일때는 답이 안 나오네요(시간 초과)...

프로그램을 최적화 시킬 방법을 찾아야겠습니다.

(드립입니다) 문제의 그림을 관찰해보면, 112개의 정사각형으로 만들어진 모양과 그 옆에 도미노가 하나 놓여져 있습니다. 즉, 큰 사각형만을 돌리거나 뒤집어서 같은 모양이 나와도 저 도미노 1개를 채우는 것도 고려를 해야 하므로 돌리거나 뒤집어서 같은 모양을 다르게 세야 합니다. 따라서 답은 수돌이님이 제시한 2^28가지....

백트래킹 함수는 1초에 약 10만 번을 수행하더군요.

백트래킹 함수의 호출 수는 n값에 따라서 5, 35, 389, 8725, 373429, 33872309로 전 n값의 답과 양상이 비슷하네요.

이에 의해서 n이 7일 때는 답이 약 4000만 이하일 것이며, 호출 시간은 7배, 11배, 22배, 42배, 91배로 증가해 (7*1), (7*1.5), (7*3), (7*6), (7*13)배로 증가한 것입니다.

즉 다음에는 7*25배로 증가할 것이라고 예측할 수 있으며, 7*25=175로 33872309 * 175 = 5927654075 = 약 60억이 되겠네요.

1초에 10만 번의 계산을 하므로 60억 나누기 10만 = 6만 초가 필요합니다.

하루가 86400초이니까 하루 안에는 되겠네요.

이제 돌립니다.

답 구했습니다.

33605540

/resources/comment/2018/09/8bfcd580408675a6ea6d943bb9400eed.zip