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

Problems

폴리매스 문제 보기

문제

[대한수학회] 대2. 사각형 채우기

2017.05.24

같이 풀어볼까?

네이버밴드 구글플러스

다음과 같이 정사각형 112개로 이뤄진 사각형 위에 정사각형 2개로 이뤄진 도미노 56개를 겹치치 않게 전체를 채우려고 할 때, 채운 모양이 서로 다른 것의 개수를 구하여라.

 

 
알립니다!
2월 16일 수돌이님이 제출한 풀이에 대해서 출제자는 각각의 고정점은 잘 계산했지만 전체 개수를 구하는 계산식이 틀려 전체 개수가 틀렸다고 이야기해주셨습니다.
다시 한 번 고민해 주세요!  아직 이 문제는 미해결입니다!

댓글 112

  • 수학동아 2017.05.24 11:13:25

    인절미 2017.02.02. 11:29

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

    좋아요0 댓글수2
    • 수학동아 2017.05.24 11:13:39

      아니요. 다르게 세지 않습니다.

      좋아요0
    • 수학동아 2017.05.24 11:13:53

      leo051213 2017.02.11. 08:16

      수학동아  아, 그렇군요!

      좋아요0
  • 수학동아 2017.05.24 11:14:09

    오이 2017.02.02. 14:58

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

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

    좋아요0 댓글수0
  • 수학동아 2017.05.24 11:14:33

    수학 2017.02.02. 15:36

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

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

    좋아요0 댓글수2
    • 수학동아 2017.05.24 11:14:49

      tommy 2017.02.14. 10:08

      자르는 부분에 들어가는 도미노가 붙어 있을 수도 있고 아닐 수도 있으니까 힘들지 않을까요..?

      좋아요0
    • 수학동아 2017.05.24 11:15:06

      수학 2017.02.14. 15:32

      tommy  아 그렇네요...

      좋아요0
  • 수학동아 2017.05.24 11:15:22

    프로벤젠 2017.02.02. 17:07

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

    좋아요0 댓글수0
  • 수학동아 2017.05.24 11:15:35

    ssamtkwon 2017.02.02. 20:12

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

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

    좋아요0 댓글수5
    • 수학동아 2017.05.24 11:15:51

      프로벤젠 2017.02.02. 23:08

      두 쌍이 같은 도미노라는게 무슨말인지 잘 모르겠습니다.
      한 도미노로 귀퉁이를 배열한다는 의미인가요?

      좋아요0
    • 수학동아 2017.05.24 11:16:07

      ssamtkwon 2017.02.03. 19:14

      프로벤젠  귀퉁이의 2조각을 하나의 도미노로 연결한다는 뜻입니다.

      좋아요0
    • 수학동아 2017.05.24 11:16:23

      프로벤젠 2017.02.04. 14:54

      ssamtkwon  그러면 귀퉁이 8조각을 8개의 도미노로 배열하는 방법도 가능하지 않나요

      좋아요0
    • 수학동아 2017.05.24 11:16:50

      tommy 2017.02.13. 20:58

      프로벤젠  아, 그렇게 되면 주변에 1칸짜리 틈이 생기는데, 이 틈을 메우려고 도미노를 채우다 보면 서로 걸립니다. 즉 이웃한 귀퉁이를 둘 다 2개의 도미노로 배열할 순 없는 것이죠.

      좋아요0
    • 수학동아 2017.05.24 11:17:06

      tommy 2017.02.14. 10:10

      그렇네요. 1과 2의 경우는 재귀 함수로 표현할 수 있겠네요. 저 아래 제가 댓글 올렸습니다.

      좋아요0
  • 수학동아 2017.05.24 11:17:18

    85 2017.02.02. 20:38

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

    좋아요0 댓글수3
    • 수학동아 2017.05.24 11:17:42

      85 2017.02.02. 20:56

      현재까지 풀이 과정: 24칸짜리에서 위에 여섯개를 보았을떄 (12칸짜리의 반)
      ■□
      □■□□ 여기서 위쪽에 2개중에 왼쪽에서 그아래쪽으로 도미노를 놓은다면.(검은색칠 된부분)
      여기서는 그오른쪽으로 가로로 놓을수는 없습니다. 그사이 틈떄문에. 다들 여기까지는 가셨겠죠. 그렇다면 안을 침범하지않고 도미노를 놓는다면 무조건 겉은 3가지의 수밖에 안됩니다.
      □□
      □□□□
      □□■■□□ (검은색칠된곳제외하고)
      □□■■□□ 좌우 6칸을 도미노3개를 층대로 쌓을떄, 위아래 4개를 둘다 가로
      □□□□ 로 놓는경우, 둘다 세로, 각각 가로 세로로 놓는경우이므로 겉은3가지,
      □□ 안은 두가지 이므로 3×2=6가지인데요, 안쪽을 침범할수가 없죠. 짝수이므로. 즉 24개일떄 6가지입니다.
      아까 12칸에서 4가지였으니 등비수열로 생각할수 있을것 같은데,
      확실하지 않아서, 또 그다음이 40개인데 등비수열이라하면 그다음 가짓수가 13 1/3이여서 등비수열은 아닌것 같구요, 제생각에는 그냥 1번쨰 2번쨰 3번쨰로 늘어날떄마다 가짓수가 늘어나는것 같은데, 36개 답나오면 증명만 하면 풀릴것 같습니다.

      좋아요0
    • 수학동아 2017.05.24 11:17:57

      파인만짱 2017.02.04. 23:27

      12칸일때 4가지 맞나요?
      돌리거나 뒤집어서 같다면 아무리 해봐도 3가지 밖에 안나오는데요....

      좋아요0
    • 수학동아 2017.05.24 11:18:13

      85 2017.02.06. 20:03

      파인만짱  그렇네요... 감사합니다

      좋아요0
  • 수학동아 2017.05.24 11:18:26

    joshua navey 2017.02.02. 22:45

    너무 어렵다....

    좋아요0 댓글수0
  • 수학동아 2017.05.24 11:18:39

    수학 2017.02.03. 15:15

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

     

    좋아요0 댓글수3
    • 수학동아 2017.05.24 11:18:55

      인절미 2017.02.03. 15:47

      당연히 가능하겠죠..

       

      좋아요0
    • 수학동아 2017.05.24 11:19:09

      인절미 2017.02.03. 15:47

      인절미  아니면 문제의 난이도가 .... ㅋㅋ

       

      좋아요0
    • 수학동아 2017.05.24 11:19:27

      수학 2017.02.03. 15:48

      인절미  감사합니다

      좋아요0
  • 수학동아 2017.05.24 11:19:45

    ssamtkwon 2017.02.03. 19:21

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

    좋아요0 댓글수4
    • 수학동아 2017.05.24 11:20:04

      tommy 2017.02.13. 21:01

      그런 것 같네요. 체스판처럼 색칠하면 증명이 될 것 같기도 한데..
      근데 줄 하나당 답이 2개가 나오겠죠?

      좋아요0
    • 수학동아 2017.05.24 11:20:19

      ssamtkwon 2017.02.14. 10:11

      tommy  줄이 고리 모양이라면 그렇겠죠.

      좋아요0
    • 수학동아 2017.05.24 11:20:34

      tommy 2017.02.14. 10:12

      ... 잠시만요. 맨 위 귀퉁이 2칸을 한 도미노로 메우고, 그 아래 2칸을 다시 한 도미노로 메우면, 전체 도미노들을 한 줄로 연결할 수 없지 않나요? 모양이 직사각형이 아니어서 줄이 끊기네요ㅠ

      좋아요0
    • 수학동아 2017.05.24 11:20:47

      tommy 2017.02.14. 10:20

      ssamtkwon  아 줄이 고리 모양이 아니어도 되는군요.. 죄송
      근데 그럼 줄이 연결되는지 끊기는지 수식으로(?) 구별할 수 있어야겠군요

      좋아요0
  • 수학동아 2017.05.24 11:21:33

    오딧셈 2017.02.03. 20:49

    어렵다....

    좋아요0 댓글수0
  • 수학동아 2017.05.24 11:21:46

    hyungjoon0546 2017.02.04. 15:22

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

    좋아요0 댓글수1
    • 수학동아 2017.05.24 11:22:15

      파인만짱 2017.02.04. 15:25

      세로줄을 기준으로 겹치는 경우, 안겹치는 경우 찾아 14항짜리 점화식을 세우면 될듯요

       

      아 각 줄의 개수가 달라서 안되네요

      좋아요0
  • 수학동아 2017.05.24 11:22:53

    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 나오는데요

     

     

    좋아요0 댓글수3
    • 수학동아 2017.05.24 11:23:12

      ssamtkwon 2017.02.06. 14:35

      golden ratio  제 생각에는 기본형을 사각형 네 개 짜리 정사각형으로 잡아야 할 것 같습니다.
      규칙대로라면 그게 가장 작은 마름모가(실제로 마름모는 아니지만) 되거든요.

      좋아요0
    • 수학동아 2017.05.24 11:23:28

      ssamtkwon 2017.02.07. 14:44

      85  12개에는 3가지가 있습니다.

      좋아요0
    • 수학동아 2017.05.24 11:23:45

      85 2017.02.08. 18:53

      ssamtkwon  그렇네요 실수~~감사합니다

      좋아요0
  • 수학동아 2017.05.24 11:24:00

    부엉이 2017.02.05. 10:41

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

    좋아요0 댓글수5
    • 수학동아 2017.05.24 11:24:16

      tommy 2017.02.14. 10:13

      어떻게 한단 말씀이시죠..?

      좋아요0
    • 수학동아 2017.05.24 11:24:34

      부엉이 2017.02.16. 16:17

      tommy  체스판처럼 검은색 하얀색을 반복해서 하고 두개짜리 블록에도 위에 검은색, 아래는 하얀색으로 해서 검-검, 하-하 로 맞게 배열하는 것이죠.

      좋아요0
    • 수학동아 2017.05.24 11:24:51

      tommy 2017.02.16. 21:55

      부엉이  검-검, 하-하라는 건 무슨 말씀이시죠?

      좋아요0
    • 수학동아 2017.05.24 11:25:10

      부엉이 2017.02.20. 08:36

      tommy  검정은 검정으로 덮고 하양은 하양으로 덮는다는 뜻이죠.

      좋아요0
    • 수학동아 2017.05.24 11:25:25

      tommy 2017.02.21. 20:16

      부엉이  아 그 뜻이군요ㅎㅎ
      근데 그렇게 하면 모든 경우의 수가 안 나오지 않나요..? 다 세기가 힘들 것 같은데요..

      좋아요0
  • 수학동아 2017.05.24 11:25:44

    85 2017.02.06. 20:07

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

    좋아요0 댓글수2
    • 수학동아 2017.05.24 11:26:00

      jireh4493 2017.02.12. 21:46
      만약 40일때 10개이면 비례식으로 의심이 가긴 가네요

      좋아요0
    • 수학동아 2017.05.24 11:26:16

      jireh4493 2017.02.12. 21:48

      jireh4493  만약 그러면 수학자님이 올려주신것과 차이가 나서......

      좋아요0
  • 수학동아 2017.05.24 11:27:18

    수학자 2017.02.06. 21:25

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

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

    좋아요0 댓글수0
  • 수학동아 2017.05.24 11:27:50

    파인만짱 2017.02.06. 23:13

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

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

    좋아요0 댓글수1
    • 수학동아 2017.05.24 11:28:07

      tommy 2017.02.13. 21:04

      저 죄송한데 가로 세로 14칸짜리 중간에 12칸짜리는 그 안이 다 안 채워질 수밖에 없습니다. 왜냐하면 14칸 마름모의 둘레에 1칸짜리가 남기 때문이죠. 그러니까 12칸 대신 14칸과 10칸과의 규칙성을 찾으면 되지 않을까요?

      좋아요0
  • 수학동아 2017.05.24 11:28:23

    수학자 2017.02.07. 10:09

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

    좋아요0 댓글수2
    • 수학동아 2017.05.24 11:28:42

      85 2017.02.07. 17:14

      저거 자체를 아는것은 힘들겠고 저기서 규칙을 찾아서 해야겠네요.

      좋아요0
    • 수학동아 2017.05.24 11:29:00

      tommy 2017.02.13. 21:05

      증명은 귀납법으로 하면 될 것 같은데.. 답만 알면 쉬울지도 모르겠네요

      좋아요0
  • 수학동아 2017.05.24 11:29:18

    수학자 2017.02.07. 19:19

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

     

    좋아요0 댓글수3
    • 수학동아 2017.05.24 11:29:34

      c_____x 2017.02.08. 23:57

      답 맞습니다. Aztec diamond로 잘 알려진 문제에요.

      좋아요0
    • 수학동아 2017.05.24 11:29:50

      수학더쿠 2017.02.10. 15:17

      뒤집거나 돌리는 것도 다르다고 한다면 2^28인 것이군요.

      좋아요0
    • 수학동아 2017.05.24 11:30:04

      수돌이 2017.02.14. 20:48

      감사합니다. 프로그래밍을 통한 일반항으로부터 많은 도움 얻을 수 있었습니다

      좋아요0
  • 수학동아 2017.05.24 11:30:25

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

    좋아요0 댓글수5
    • 수학동아 2017.05.24 11:30:48

      85 2017.02.08. 18:22

      정확한 풀이 알려주실수 있나요....

      좋아요0
    • 수학동아 2017.05.24 11:31:05

      수학자 2017.02.08. 23:44

      85  일단 증명은 못 했고 다만 프로그래밍으로 확인했습니다. 문제 정답의 범위는, 돌리거나 뒤집어서 같아지는 모양의 수가 2,4,8 중 하나이기 때문에 그렇습니다.

      좋아요0
    • 수학동아 2017.05.24 11:32:57

      수학더쿠 2017.02.10. 15:23

      저는 문제의 답이 33554432 (= 225)라고 생각합니다.
      왜냐하면 문제의 모양을
      __1
      2___3
      __4
      로 간단하게 보면 이 모양을 응용해서 만들 수 있는 다른 숫자 배열(돌리거나 뒤집기)가 8종류이기 때문에 228 / 23 을 하면 225가 나오기 때문입니다.

      * _은 빈칸을 대신하기 위해 쓴 것입니다.

      좋아요0
    • 수학동아 2017.05.24 11:33:17

      수학더쿠 2017.02.10. 15:29

      수학자  제 생각에는 뒤집거나 돌려서 같은 것도 모두 다르다고 한다면 컴퓨터는 사람이 육안으로 보기에 같은 것도 다르다고 할 것 같습니다. 예를 들어 가짓수가 사람이 보기에 2가지일 경우는 컴퓨터는 같은 4가지를 모두 다 센 것이기 때문에 돌리거나 뒤집어서 같은 모양은 8가지만 될 것 같습니다.

      좋아요0
    • 수학동아 2017.05.24 11:33:33

      tommy 2017.02.14. 10:15

      수학더쿠  죄송한데 '컴퓨터는 사람이 육안으로 보기에 같은 것도 다르다고 한다'가 무슨 뜻이죠...?

      좋아요0
  • 수학동아 2017.05.24 11:34:05

    kjinwoo03 2017.02.07. 21:57

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

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

    24개일때 10개??

     

    좋아요0 댓글수0