p_ce1052   5년 전

스프라그-그런디의 보조정리 중에

행동 집합 A와 B가 동치이면 A+B = P-행동집합 이라는 정리가 있더라구요. 

한 번에 두 개까지 돌을 가져갈 수 있을 때, 마지막 돌을 가져가는 사람이 이기는 게임에서

게임 A에 돌이 1개 남아있고 B에 2개가 남아있으면 각각의 게임에서 

A = {*0 } 이고 B = {*0 , *1} 로 각각이 N행동집합입니다.

그럼 위의 정리에 따라 A+B = P-행동집합 이어야 하는데

위의 보조정리에 의해 현재 턴인 사람이 무조건 져야 하잖아요? 근데 현재 턴인 사람이 2개짜리 돌무더기에서 하나를 가져가면 무조건 이기게 되는데 왜 A+B가 P-행동집합인지 이해가 안됩니다. 어느 부분을 제가 잘못 이해하고 있나요? 

두 개의 돌무더기에 각각 1개와 2개의 돌이 남은 상황에서 A+B = N행동집합임을 위의 정리와 충돌하지 않게 어떻게 해석할 수 있나요? 

yj10516   5년 전

A와B가 동치라 함은 모든 행동집합 C에 대해 , A+C , B+C가 둘 다 N-행동집합이거나 둘 다 P-행동집합이어야 합니다.

A+A 는 P행동 집합이고, B+A는 N행동집합이므로 A와 B는 동치가 아닙니다.

p_ce1052   5년 전

두 행동집합이 모두 N행동집합이나 p행동집합에 포함된다고 해서 두 행동집합이 동치는 아닌거군요

p_ce1052   5년 전

하나만 더 여쭤봐도 될까요? 게임이론 글을 보다보면 두 게임을 합한다 라는 말이 나오는데 여러 게임을 합한 게임은 합쳐진 게임 중 하나라도 이기면 전체를 이기게 되는건가요? 게임의 합이 뭔지 설명된곳이 없어서 이해가 힘드네요

p_ce1052   5년 전

한번에 k개를 가져갈때 가져갈 돌이 없으면 지는 게임 n개를 합한것과 돌무더기 n개에서 하는 님게임은 아예 다른게임이 되는건가요?

yj10516   5년 전

여러 게임을 합한 게임은 맨 마지막까지 남아있는 게임을 이기는 사람이 이기게 됩니다.
저는 https://casterian.net/archives...이 블로그를 참고했었습니다. 더 자세한 것은 이 블로그를 참고하시면 좋을것 같습니다.

두번째것은 그런디 수를 직접 계산해서 비교해보시면 좋을것 같습니다.

p_ce1052   5년 전

엇 저도 저 글 보면서 공부하고 있어요. ㅎㅎ 답변 정말 감사합니다

댓글을 작성하려면 로그인해야 합니다.