스프라그-그런디 정리

• nim 게임을 이해해야함 일단
  • https://blog.myungwoo.kr/27
  • 상대의 상태를 0으로 만들면 되는데, (집요하게?) 만들어 갈 수 있음
• 재귀적인 특성을 이해

그런디 함수 : g()

• mex 함수와 g 함수를 이해
  • g(x) = mex{g(x의 다음 상태들)}
  • g(x) = 0 : x의 다음 상태들의 g(x') 값중에 0인 것들은 없다. 즉 g(x')는 항상 0이 아님
  • g(x) != 0 : x의 다음 상태들의 g(x') 중에서 0인 것들이 있다. 즉 g(x') = 0인 것이 있음
• 이용
  • g(x) = 0이면 내가 뭘 하든 g(x') != 0이 아니게 됨
    • 상대 입장에서는 g(x') != 0 이 아니니까 잘 고르면 g(x'') = 0인 것을 나에게 줄 수 있음
  • g(x) != 0이 아니면 내가 잘 골라서 g(x') = 0으로 만들어버릴 수 있음
  • 즉 g(x) = 0인 것을 갖게 되는 사람이 지는데, g(x) != 0인 사람은 무조건 다름 사람을 g(x) = 0으로 만들 수 있음

스프라그-그런디 정리 : nim 게임에서처럼 여러개의 게임을 xor 함

• 왜 각각의 게임을 xor해도 되지??
• 엄밀한 증명은 아니지만 nim 게임처럼 생각은 해볼 수 있음
• ${g(x_1) \oplus g(x_2) \oplus ... g(x_n) = g(y) = c}$ 라고 해봄. 그리고 c에서 가장 큰 비트가 대충 k 번째라고 하겠음
  • ${y}$는 여러가지 게임들의 집합인 상태, ${x_i..}$들은 개별적인 게임의 상태들
• 일단 ${g(x_i)}$ 중에서 가장 큰 비트가 k 번째인 것이 어딘가는 있을 것임. 편의상 ${g(x_1)}$이 그런 것이라고 치면
• ${g(x_1) \oplus {나머지} = c }$
• ${g(x_1) -> g(x')}$ 로 바꾸는데 그 값이 ${c \oplus g(x_1)}$이면 좋을 것 같음 왜냐하면 그렇게 바꾸면 ${c \oplus g(x_1) \oplus {나머지} = c \oplus c = 0}$이 되니까
• 그렇다면 진짜 ${c \oplus g(x_1)}$로 바꾸는게 가능함???
  • 일단 ${c \oplus g(x_1)}$ 는 ${g(x_1)}$보다는 작을 것임 왜냐하면 가장 큰 k 비트가 제거 될테니까
  • ${g(x_1)}$의 특징이 ${x_1}$의 다음 상태들의 ${g()}$값에 속하지 않는 것들중에 가장 작은 값인데 다음 상태들의 g값들을 표현하면 이렇게 됨
  • 0(가능), 1(가능), 2(가능), .... ${g(x_1)}$(불가능), 다음값(상관없음), 그 다음값(상관없음), ....
  • 이렇게만 되면 포함하지 않는 것중에 가장 작은 값의 조건을 만족시킴
  • 결과적으로 ${g(x_1)}$ 보다 작은 무엇인가가 있고, 그것으로 바꾸면 됨
  • 다만 엄밀한 증명을 위해서는 ${g(x_1) \oplus g(x_2) \oplus ... g(x_n)}$ 이렇게 한 것 자체가 ${g(x)}$의 특징을 만족하는지를 증명해야함..........(귀류법??????)

참고

• https://developerhan.tistory.com/30
• https://anz1217.tistory.com/110
• https://yujaa.tistory.com/entry/%EA%B2%8C%EC%9E%84%EC%9D%B4%EB%A1%A0-%EC%8A%A4%ED%94%84%EB%9D%BC%EA%B7%B8-%EA%B7%B8%EB%9F%B0%EB%94%94-%EC%A0%95%EB%A6%AC
  • 스프라그-그런디 정리를 잘 설명해 주셨음
• https://ohgym.tistory.com/21
  • 그림 설명을 잘 하셨음
  • 다만, 중간에 state와 g()를 구분해서 이해해야함
• https://casterian.net/archives/1239
  • 수식을 이용한 엄밀한 증명
  • 언젠가는 이해하겠지....