[문제]
동전 세개가 앞면이 위를 향한채 놓여있다. 한 번에 두개의 동전을 뒤집어야한다고 하자. 이 시행을 반복했을때 동전 세개가 동시에 뒷면이 위를 향할 수 있는가?
[풀이]
정답은 동전 세개가 동시에 뒷면이 위를 향할 수 없다. 입니다. 두가지 방식으로 설명할 수 있습니다.
<정수론적 방식>
어떤 동전이 뒷면이 되기 위해서는 그 동전을 뒤집은 횟수가 홀수번이어야 합니다. 짝수번이면 앞면이 되기 때문입니다. 세 개의 동전이 모두 뒷면이 된다는 이야기는 동전 각각에 대해 뒤집은 횟수가 홀수번이라는 이야기 입니다. 세개의 동전을 뒤집은 횟수를 모두 더하면 역시 홀수가 됩니다.
그런데 우리는 동전을 2개씩 뒤집기 때문에 세개의 동전을 뒤집은 횟수를 모두 더하면 짝수가 나와야합니다. 따라서 모든 동전이 뒷면이 되는 일은 있을 수 없습니다.
<군의 작용을 이용한 방식>
군의 작용(group action)이라는 개념을 이용해서 문제를 해결 할 수 있습니다. 동전을 뒤집는 행위들의 집합을 생각해봅시다. 첫번째 동전과 두번째 동전을 뒤집는 행위를 (110)이라는 이름을 붙이고, 첫번째 동전과 세번째 동전을 뒤집는 행위를 (101)이라고 씁니다. 자연스레 남은 행위는 (011)이라고 이름을 붙일 수 있습니다. 아예 뒤집지 않는 경우는 (000)이라고 이름을 붙이겠습니다. 함수의 합성처럼 생각하면서 방금 이름붙인 4개의 원소를 연산하다보면 4개의 원소를 가진 가환군이 됨을 알 수 있습니다.
이제 우리가 찾은 군은 G={(000), (110), (101), (011)}으로 쓸 수 있습니다. 군의 작용을 받게될 집합X를 생각해봅시다. 동전 3개가 나타낼 수 있는 상태는 2^3=8입니다. 앞면인 상태를 H, 뒷면인 상태를 T라 두겠습니다. 예를 들어 HHH는 모두 앞면인 상태입니다. 즉 집합 X는 {HHH, HHT, ..., TTT}가 됩니다.
이 문제에서는 군의 작용의 예로 HHH*(000)=HHH, THT*(110)=HTT, TTT*(101)=(HTH)가 됩니다.
[X/G는 잉여류의 집합, Xg는 g에 의해 고정되는 X의 부분집합입니다.]
번사이드 정리라고 부르는 공식을 이용합니다. 좌변은 G의 잉여류의 수이고 우리는 좌변이 2가 됨을 밝힐 것입니다. G의 원소의 수는 4이고, Xg는 g=(000)을 제외하면 모두 0이 되고(고정되지 않기 때문에), X(000)=8(모든 X의 원소를 고정하므로)이 되므로 X/G는 그 수가 8/4=2가 됩니다.
위 계산에 따라 G의 작용으로 나타나는 X의 부분집합의 원소는 초기 상태에 따라 많아야 4가지 원소가 존재합니다. 초기상태가 HHH인 경우 G에 의해 나타나는 상태는 {HHH, THT, TTH, HTT}이고, 그 밖의 상태는 존재하지 않습니다. 이는 HHH인 상태에서 동전 2개를 뒤집는 것으로는 TTT가 나올 수 없음을 뜻합니다. 나머지 상태도 생각해봅시다. 잉여류의 수가 2였으므로 나머지 상태는 {TTT, THH, HTH, HHT}가 됩니다. 초기상태가 HHT,HTH, THH였다면 동전을 2개 뒤집었을때 TTT가 나올 수 있게 됨을 알 수 있습니다.
문제의 숫자를 바꾸어서 만약 동전 4개를 3개씩 뒤집는다면 구성하게 되는 G의 위수가 16이므로 번사이드 정리를 적용하면 잉여류의 수가 16/16=1이 됩니다. 이는 동전의 모든 패턴이 나오게 된다는 것을 의미합니다.
이 논의를 일반화 하면 동전을 2n+1로 확장할 수 있습니다. 그러면 동전을 2개씩 뒤집을때 나오게 되는 군 G는 동전 2개를 뒤집는경우, 4개를 뒤집는 경우, ..., 2n개를 뒤집는 경우를 생각해주게 되므로 G의 위수는 2^(2n)이 됩니다. 집합 X는 2^(2n+1)개의 원소를 가지므로 번사이드 정리를 적용하면 잉여류의 수는 2가 됩니다. 초기상태를 HH....H라 하면 그 잉여류는 T의 개수가 무조건 짝수개가 될 것이므로 모두 T가 되는 것은 불가능합니다. 따라서 동전을 모두 뒤집는 것은 불가능합니다.
네이버 블로그에서 본거같은데