사용자 도구

사이트 도구


ps:스프라그-그런디_정리

스프라그-그런디 정리

  • 작성 예정

Octal game

  • Octal game 참고
  • 세줄요약 먼저 하자
    • Octal game은 Take-and-break 게임을 부르는 말로, 그런디수가 주기적으로 반복될 가능성이 높다. 주기를 찾으면 그런디 수를 O(n^2)이 아닌 O(n)에 계산할수 있다.
    • Dawson's Kayles은 주기가 34이니까, 이 결과를 그냥 가져다 쓰자.
    • 제거할수 있는 갯수가 3이하인 게임이면, octal code를 https://github.com/tczajka/octal-games에서 찾아서 주기가 이미 발견되어있는지를 확인해봐도 된다.
  • 대충 n개의 돌이 있는 무더기에서 시작해서 몇개의 돌을 제거한뒤 (0개를 제거할수도 있다), 두 무더기로 나누는 행동 (한쪽이 0개가 될수도 있다 = 안나눌수도 있다) 을 번갈아서 취하는 게임이다
    • 제거할수 있는 돌의 갯수에 제한이 없고, 두 무더기로 나누는 행동을 금지하면 님 게임이 된다.
    • 제거할수 있는 돌을 2개로 고정시키고, 두 무더기로 나누는 행동을 허용하면 Dawson's Kayles 이 된다.
  • 게임 규칙을 반영해서, 인포멀하게는 take-and-break game이라고도 불리는 것 같은데 이쪽이 훨씬 직관적이긴 하다.
  • Octal game이라는 이름은, 규칙의 배리에이션을 일종의 8진수 형태로 표기할수 있기 때문이다.
    • i개를 제거하는것이 가능하고, 그때 0개를 남기는것 / 1무더기를 남기는것 /2무더기로 나누는 것 이 가능한지 여부를 bitmask형태로 만든 값 (1~7)을 소숫점 i번째 숫자로 표기한다
    • Nim 게임은 0.33333… 이고 (몇개를 가져가도 괜찮고, 가져가면서 0개를 남기거나 1무더기를 남기는것이 가능하다)
    • Dawson's Kayles 은 0.07 이다 (2개만 가져갈수 있으니까 소숫점 2번째자리만 0이 아닌값을 갖고, 그때는 0무더기/1무더기/2무더기가 다 가능하므로 값은 7)
  • 많은 Octal game은 grundy number가 periodic하게 나타난다.
    • 모든 octal game이 periodic 한지는 아직 모른다 ⇒ 수백만 자리까지 돌려봤는데도 아직 주기를 못찾은 것들이 있다.
    • grundy number을 구해보다가, 거기에 주기적인 패턴이 있는것 같아 보이면, 진짜로 그 패턴이 무한이 반복되는게 맞다.. 라는 정리가 있다
      • 'Guy-Smith periodicity theorem' 이라고 하는데, 좀더 포멀한 형태로 정리한 내용은 여기 참고.
    • Dawson's Chess, Dawson's Kayles, Octal games .4, .401, .402, .403, .42, .421, .422 and .423 의 그런디 넘버는 34를 주기로 갖는다
  • Dawson's Kayles 게임에서 선공이 지는 경우는, n∈{0,1,15,35} 또는 n%34∈{5,9,21,25,29} 이다
  • 관련 문제

토론

댓글을 입력하세요:
S B T Z L
 
ps/스프라그-그런디_정리.txt · 마지막으로 수정됨: 2022/06/07 13:56 저자 teferi