아래에 있는 논리퀴즈 풀이올립니다.

 

행과 열은 편의상 0에서 7까지 숫자를 붙입니다. 아래 그림을 참조하시면 설명을 따라가는데 도움이 될 것입니다. 배열에서 동전의 앞은 0, 뒷면은 1입니다. 열과 행의 숫자를 2진법으로도 표시하였습니다. 이 표시가 왜 필요한지는 아래에서 설명합니다.

 

 

 

1. 주어진 8*8 배열에서 (열,행) 좌표 계산하는 방법

1) 각 행과 열의 parity를 결정 : 위 그림에서 0행에는 1이 6개 있으므로 parity는 0, 0 열에는 1이 3개 있으므로 parity는 1 등등.

2) parity가 1인 각 행과 열에 그 행(또는 열)의 번호를 weight를 줍니다. parity가 0이면 weight는 0으로 줍니다. : 위 예에서 1행과 2행의 parity각 각각 0, 1 이므로 1행은 weight가 0이고, 2행은 weight가 2 즉 2진법으로 010가 됩니다.

3) 열의 좌표는 weight를 모두 더하는데 bitwise addition을 합니다. 여기서 addition은 modulo 2 연산입니다. 즉 각 bit의 숫자를 다 더해서 2로 나눈 나머지를 구합니다. 행도 마찬가지입니다. : 위 예에서 행의 weight를 모두 더하면 010+101+110=001 입니다. 왜냐하면 첫 bit를 더하면 0+1+1=2이므로 나머지는 0, 두번째 bit를 더하면 1+0+1=2, 나머지 0, 세번째 bit를 다 더하면 0+1+0=1이기 때문입니다.

4) 계산결과를 다시 10진법으롤 변환합니다.

 

2. B의 조작 방법

1)A가 좌표를 선택합니다. : 예제에서는 (열,행)=(2,4) 입니다.

2)B는 이 좌표를 2진법으로 변환합니다. :(2,4)=(010,100)

3) 현재 배열의 좌표와 A의 좌표가  같으면 B는 조작을 하지 않습니다.

4) 두 좌표가 다르면 현재배열의 좌표와 A의 좌표를 bitwise addition합니다 : (110,001)+(010,100)=(100,101)=(4,5)

5) 계산된 좌표의 동전을 뒤집습니다

 

3. 결과는 아래와 같습니다. 조작 전 (4열, 5행)의 값은 1이었는데 이 값을 0으로 바꾸고 새로운 좌표를 계산하면 A가 선택한 (2열,4행)이 됩니다.

 

 

 

 

4. 이론적배경

제가 이 풀이를 생각할 때는 수학전공 지식을 이용하였습니다. 이 부분은 관심있으신 분만 읽어보세요~. 필요한 지식은 대수학(Algebra)입니다.

 

체스판의 배열은 group G=Z_2^64={0,1}^64의 원소로 생각할 수 있습니다.이 그룹은 cyclic group Z_2={0,1}의 product group입니다.  e_i=(0,0,...,1,0,...,0)라고 합시다. (i 번째 항만 1이고 나머지 63개는 0인 원소).  i 번째 동전을 뒤집은 결과는, 현재 상태를 a(G의 원소)라고했을 때, a+e_i가 됩니다.   

 

이 문제는 적당한 조건을 만족하는 G의 분할 {H_1,H_2,...,H_64}을 찾는 것이 목표입니다. H_i는 i 번째 칸에 대응됩니다. 즉 현재 배열의 상태 a가 H_i의 원소이면 B와 C는 i 번째 칸을 좌표로 계산합니다 .( 여기서는 8*8 배열을 사용하지 않고 64개의 칸을 1줄로 세워서 생각합니다. 두 접근법의 본질적인 차이는 없습니다.)  G의 임의의 원소 x가 주어졌을 때 (편의상 x가 H_1에 속한다고 가정) 동전 하나를 뒤집어서 (혹은 내버려두어서) 모든 분할 H_i로 이동이 가능해야 합니다. 즉 x+e_j가 H_i의 원소가 되는 j를 찾을 수 있어야합니다. 예를 들어 8번째 동전을 뒤집음으로써 새로운 좌표가 3이 되도록 만들 수 있어야합니다.

 

위 조작이 가능하다고해도 원칙적으로 H_1의 원소들에 같은 e_j를 더해줘야할 필요는 없습니다. 예를 들어 y도 H_1의 원소라고 하면 y는 13번째 동전을 뒤집음으로써 새로운 좌표가 3이 되게 할 수도 있습니다. 하지만 이런식의 이동도 허용하면 문제가 너무 복잡해지므로 각 분할의 원소들에는 공통 조작을 가해줘도 결과가 같도록 해주면 풀이가 더 단순해 질 것입니다.(만약 그런 조작이 가능하다면! 물론 결과적으로 가능합니다.) 즉 i,j가 주어지면 H_i+e_j=H_k가 되고, i, k 가 주어지면 H_i+e_j=H_k가 되는 j를 찾을 수  있도록 분할을 만들면 문제가 풀립니다.  

 

이 조건을 만족하는 분할이 존재한다면 H_i들은 모두 크기가 같고 그 키기는 |G|/64=2^(64-6)=2^58이 됩니다. 또한 이 분할은 H_1+e_i꼴의 형태가 되므로 자연스럽게 G의 subgroup H의 left coset들을 고려하게 되었습니다. 즉 quotient group G/H의 크기가 64인 subgroup H를 찾아야합니다.(G가 가환군이므로 모든 부분군은 정규군). 이 때 e_i+H가 모두 달라야 합니다.(e_i+H != e_j+H for i!=j). 역으로 H가 G/H의 크기가 64인 부분군이고, e_i+H가 모두 다르면, H_i=e_i+H가 문제의 조건을 만족합니다. 이 사실이 상당히 놀라웠습니다. (증명: quotient group의 정의에 의해 G/H={g+H: g는 G의 원소}={g_1+H,...,g_64+H : for some g_i}을 알고있습니다. 이제 K={e_1+H,...,e_64+H}라고 했을 때 G/H=K 임을알수있습니다.(비둘기집의 원리) 즉, 우선 K는 G의 분할이 됩니다. e_i+H_j=(e_i+e_j)+H이고, quotient group의 성질에 의해서 이 결과는 G/H에 속해야 하므로 e_i+H_j=e_k+H for some k 가 됩니다. 두 번째 성질을 만족하려면 i,k에 대하여 e_j+(e_i+H)=e_k+H인 j를 찾아야 하는데, (e_i+e_k)+H가 G/H의 원소이므로 (e_i+e_k)+H=e_j+H인 j가 존재합니다.)

 

한편 G의 원소의 order는 2 이므로( a+a=0 for all a in G) G/H의 원소의 order도 2입니다. Finitely generated abelian group theory에 의해 G/H는 Z_2^6와 isomorphic함을 알 수 있습니다. 따라서 H를 구성하기 위해서는 f:G->Z_2^6인 group homomorphism을 만들면 되는데, 이 때 f는 onto map이 되어야하고 f(e_i)들이 모두 다른 값을 가지기만하면 위의 조건들을 만족함을 알 수 있습니다. 위 예제 1-3의 과정은 이 조건들을 만족하는 group homomorphism을 계산하는 과정입니다.