본문바로가기
함께 풀고 싶은 문제
직접 문제를 올려 폴리매스 출제자에 이름을 올리세요!
문제를 잘 표현할 수 있는 제목을 짓고, 문제에 사용된 수학 분야를 말머리로 달아주세요.
[창의 퍼즐] [게임이론] 피라미드 게임의 일반화 (1년 2개월 동안 연구해서 푼 문제)
아인수타인 2020.06.23 14:45

(침고: 이 문제의 특수한 버전은 여기 있습니다! http://www.polymath.co.kr/contents/view/1169)

 

피라미드 게임의 규칙은 위 링크에 나와 있는 것이랑 같다. 그리고 역시 파스탈부터 시작한다. 위 문제에 나와 있는 것처럼 각 층에 1개, 2개, 3개, 5개, 7개의 선분이 있다면 (1,2,3,5,7)의 순서쌍으로 나타내자. 이 때, 임의의 순서쌍이 주어졌을 때, 이 게임이 페루마가 이길지, 파스탈이 이길지 알 수 있을까? 그 방법은 무엇일까? (단, 두 사람은 최선을 다해 게임을 한다고 가정한다.)

이 문제 어떠셨나요?

유익해요

0

웃겨요

0

신기해요

0

어려워요

0

  •  
    해결
    수돌이 Lv.3 2020.06.23 15:24 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수5
    •  
      수돌이 Lv.3 2020.06.23 15:26

      아 마지막 선분을 지우면 지는 게임이네요

      이 풀이는 마지막 선분을 지우면 이기는 게임일 경우입니다ㅠㅠ

      좋아요0
    •  
      아인수타인 Lv.12 2020.06.23 15:26 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      수돌이 Lv.3 2020.06.23 16:32

      일반 님게임 필승법도, 제가 잘못 생각했던 게임 (마지막 선분을 지웠을 때 이기는 경우, 이하 게임 X)의 필승법도 모두 grundy number라는 개념을 사용하기 때문이예요!

      https://casterian.net/archives/1239

      일반 님게임과 게임 X 모두 몇 개의 부분게임을 동시에 진행하는 형태를 가지고 있죠.

      일반 님게임의 경우 "돌 무더기 하나에서 원하는 만큼 돌을 가져가기를 반복하는 게임" 여러 개를 동시에 진행,

      게임 X의 경우 "일렬로 나열된 선분들 중 연속한 몇 개의 선분을 지우는 게임"여러 개를 동시에 진행합니다.

       

      "돌 무더기 하나에서 원하는 만큼 돌을 가져가기를 반복하는 게임"에서 각 상황별로 grundy number이라는 걸 계산해 볼 거예요.

      우선, 돌 무더기에 돌이 0개일 때는 게임이 끝나고, 그 상황을 만든 사람이 이기죠. 이렇게 게임이 끝나고, 그 상황을 만든 사람이 이길 경우 해당 상태의 grundy number는 0이라고 정의합니다.

      그 외의 상태의 grundy number는 "현재 상태에서 행동을 하였을 때 갈 수 있는 상태들의 grundy number"들과 겹치지 않는 음 아닌 정수 중 가장 작은 수가 됩니다. 예시를 통해 설명드릴게요.

      돌 무더기에 돌이 1개일 때는 어떻게 될까요? 해당 상황에서 행동을 했을 때 어떤 상태가 될 수 있는지 알아봅시다. 돌이 0개인 상태로밖에 갈 수 없겠죠? 즉, grundy number가 0인 상태로밖에 갈 수 없습니다. 따라서 {0}과 겹치지 않는 음 아닌 정수 중 가장 작은 1. 돌이 1개인 상태의 grundy number는 1입니다.

      돌이 2개일 때는 행동을 하여 돌이 1개인 상태(1)과 돌이 0개인 상태(0)으로 갈 수 있겠죠. 따라서 {0,1}과 겹치지 않는 음 아닌 정수 중 가장 작은 2. 돌이 2개인 상태의 grundy number는 2입니다.

      이렇게 수학적 귀납법을 이용하여 "돌 무더기 하나에서 원하는 만큼 돌을 가져가기를 반복하는 게임"에서 돌이 n개일 때의 grundy number는 n이라는 사실을 알 수 있어요.

      grundy number의 가장 중요한 성질은 0인 상태에서는 항상 후공이 이기고, 0이 아닌 상태에서는 항상 선공이 이긴다는 것이죠. "돌 무더기 하나에서 원하는 만큼 돌을 가져가기를 반복하는 게임"을 보면 돌이 1개 이상이라면 선공이 모든 돌을 다 가져가서 이길 수 있고, 돌이 0개라면 선공이 행동을 못하기 때문에 후공이 이기겠죠.

      이제 다시 NIM 게임을 보도록 할게요. "돌 무더기 하나에서 원하는 만큼 돌을 가져가기를 반복하는 게임" 여러 개를 동시에 진행하는 것이 일반 NIM 게임이죠. 이렇게 게임이 종료되는 상황을 만들었을 때 이기는 게임 여러 개를 동시에 진행할 경우, 해당 게임의 grundy number는 동시에 진행하는 게임들의 grundy number들을 모두 Xor 한 값이 됩니다.

      그래서 NIM 게임의 필승법 판정이 댓글과 같은 것이구요!

       

      피라미드 게임으로 돌아와서, 마지막 선분을 지웠을 때 이기는 경우에는 왜 일반 NIM게임과 필승법 판정 조건이 같은가 하면,

      그것은 한 줄에 n개의 선분이 있을 때의 grundy number가 마찬가지로 n이기 때문입니다! (증명해보세요. 마냥 쉽지는 않아요ㅎㅎ)

      좋아요0
    •  
      아인수타인 Lv.12 2020.06.23 21:08

      음... 저희가 찾은 방법과 상당히 다르기는 한데, 제가 저희가 찾은 필승이 되는 쌍 몇 개를 시험해보니 맞는 것 같네요! (증명과정은 이해가 잘 안 가지만;;;) 저희가 찾은 방법도 맞긴 맞는데, 이게 훨씬 더 쉬운 것 같긴 하네요... 그 이후의 증명은 피라미드 게임에서 남은 연구 과제라고 생각하고 꼭 해보겠습니다!

       

      (그나저나 저희가 1년 2개월 걸친 걸 하루만에...ㄷㄷ)

      좋아요0
    •  
      은총알 Lv.11 2020.07.04 15:40

      와 역시 원조 ..ㄷㄷ

      좋아요0
  • 폴리매스 문제는 2019년도 정부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.

  • ☎문의 02-6749-3911