[수학의 세계]수학의 세계
![[수학의 세계]수학의 세계-1](http://images.happyhaksul.com/thumb/130/129308-0001.gif)
![[수학의 세계]수학의 세계-2](http://images.happyhaksul.com/thumb/130/129308-0002.gif)
분야
hwpnim sum의 예)
풀이방법 적용한 nim 게임의 예)
세 뭉치의 바둑돌 수를 이진수로 나타낸 다음 그것들의 XOR를 구합니다.
0 xor 0 = 1 xor 1 = 0, 1 xor 1 = 1 xor 0 = 1
이 XOR의 결과를 nim sum이라 합니다.
nim sum의 예)
처음 3,5,7을 이진수로 나타내면, 각각 11, 101, 111이고, 이 셋의 XOR, 즉 nim sum은 001입니다.
011
101
xor 111
--------
001
nim game에서 마지막에 한 개를 가져가는 사람이 이긴다고 가정합시다. A,B 두사람이 한다고 합시다.
처음 A의 차례에서 바둑돌 하나를 가져 간 다음, B가 몇 개를 가져 가든, nim sum이 000이 되도록 바둑돌을 가져 가면 됩니다.
풀이방법 적용한 nim 게임의 예)
3, 5, 7 ─이진수 변환 : 011, 101, 111 ─ nim sum = 001
① 3 - 1 = 2 (A의 차례)
2, 5, 7 ─이진수 변환 : 010, 101, 111 ─ nim sum = 000
② 7 - 3 = 4 (B의 차례)
2, 5, 4 ─이진수 변환 : 010, 101, 100 ─ nim sum = 011
011 xor 011 = 000이므로,
(010 xor 101 xor 100) xor 011 = (010 xor 011) xor 101 xor 100
= 1 xor 5 xor 4 = 000
이 되도록, 2개 짜리에서 1개를 가져갑니다.
