====== 스프라그-그런디 정리 ======

  * 작성 예정

===== Octal game =====

  * [[wp>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' 이라고 하는데, 좀더 포멀한 형태로 정리한 내용은 [[https://combinatorialgames.wordpress.com/2012/08/10/i-7-a-strategy-for-kayles-guy-smith-periodicity/|여기]] 참고.
    * Dawson's Chess, Dawson's Kayles, Octal games .4, .401, .402, .403, .42, .421, .422 and .423 의 그런디 넘버는 34를 주기로 갖는다
      * [[http://oeis.org/A002187]]
  * Dawson's Kayles 게임에서 선공이 지는 경우는, n∈{0,1,15,35} 또는 n%34∈{5,9,21,25,29} 이다
    * [[https://math.stackexchange.com/questions/2467504/what-properties-can-be-derived-for-these-recursively-defined-nimbers-or-grundy]]
    * 굳이 증명하자면, [[https://www.nearly42.org/cstheory/two-easy-deletion-games-on-paths/]] 처럼 하면 되는것 같긴 하다
      * 34가 주기라는 것을 아는 상태에서 그 주기가 무한하게 계속된다는 것을 증명하는거라서, 새로운 주기를 찾을때 쓸수 있는 방법은 아니다. 
    * <dkpr py>
def is_win_pos_of_dawson_kayles(n):
    return not (n in (15, 35) or n % 34 in (5, 9, 21, 25, 29))
</dkpr>
  * 관련 문제 
    * [[ps:problems:boj:16187]] - Dawson's Kayles과 같은 게임
    * [[ps:problems:boj:31687]] - Dawson's Kayles과 같은 게임
    * [[ps:problems:boj:22850]] - Octal game "0.4"