nim에 대해서 질문.. kriii nim을 할때 한 파일에서 돌을 꺼낸 다음, 그 파일을 두 개의 다른 파일로 찢어놓을 수 있다고 할때도 grundy number가 그냥 nim이랑 같다고 하더라구요... 왜 그런지 알수 있을까요?? 12년 전
1개의 댓글이 있습니다. kriii 앜ㅋ 자문자답 합니다.. 원래 grundy number를 X라고 하고 크기가 a인 돌을 뽑아 a'로 만들면 grundy number는 Xaa'됨. 위의 문제에서의 grundy number도 파일들의 크기를 xor한 것이라고 한다면, a'을 p와 q로 나눈 경우의 gurndy number는 Xapq가 됨 즉 p ^ q != a이면 가정이 성립하게 됨. p ^ q <= p + q = a' < a이므로 가정이 성립한다. 12년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
kriii
nim을 할때 한 파일에서 돌을 꺼낸 다음, 그 파일을 두 개의 다른 파일로 찢어놓을 수 있다고 할때도 grundy number가 그냥 nim이랑 같다고 하더라구요... 왜 그런지 알수 있을까요??
12년 전