nim에 대해서 질문..

  • kriii
    kriii

    nim을 할때 한 파일에서 돌을 꺼낸 다음, 그 파일을 두 개의 다른 파일로 찢어놓을 수 있다고 할때도 grundy number가 그냥 nim이랑 같다고 하더라구요... 왜 그런지 알수 있을까요??


    6년 전
1개의 댓글이 있습니다.
  • kriii
    kriii

    앜ㅋ 자문자답 합니다..

    원래 grundy number를 X라고 하고 크기가 a인 돌을 뽑아 a'로 만들면 grundy number는 X^a^a'됨.
    위의 문제에서의 grundy number도 파일들의 크기를 xor한 것이라고 한다면, a'을 p와 q로 나눈 경우의 gurndy number는 X^a^p^q가 됨
    즉 p ^ q != a이면 가정이 성립하게 됨.
    p ^ q <= p + q = a' < a이므로 가정이 성립한다.


    6년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.