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} 이다
- 굳이 증명하자면, https://www.nearly42.org/cstheory/two-easy-deletion-games-on-paths/ 처럼 하면 되는것 같긴 하다
- 34가 주기라는 것을 아는 상태에서 그 주기가 무한하게 계속된다는 것을 증명하는거라서, 새로운 주기를 찾을때 쓸수 있는 방법은 아니다.
def is_win_pos_of_dawson_kayles(n): return not (n in (15, 35) or n % 34 in (5, 9, 21, 25, 29))
- 관련 문제
- Game on Plane - Dawson's Kayles과 같은 게임
- Trokut - Dawson's Kayles과 같은 게임
- 22850 - Octal game “0.4”
ps/스프라그-그런디_정리.txt · 마지막으로 수정됨: 2024/03/27 14:56 저자 teferi
토론