마법사와 모자 2

문제

원탁에 11명의 마법사들이 앉아있다. 마법사들은 각자 모자를 쓰고 있는데, 모자에는 1000 이하의 자연수가 적혀있다. 각 마법사들은 자신을 제외한 다른 10명의 모자를 볼 수 있다.

모든 마법사는 동시에 왼손 또는 오른손을 들고, 그 다음 동시에 수를 하나 외친다. 이 수가 자신의 모자에 적힌 수가 아니라면 숙청당한다.

게임을 하기 전 마법사들은 전략을 짤 시간이 주어진다. 모두 살아나갈 수 있을까?

풀이

살아나갈 수 있다.

\(i\)번째 마법사들의 모자에 적힌 수를 이진법으로 나타낸 값을 \(w_i\)라 하자.

\(S := x_{1} \oplus x_{2} \oplus ... \oplus x_{11}\) 이라 두자. 여기서 \(\oplus\)는 XOR 연산자이다.

\(i\)번째 (\(1 \le i \le 10\)) 마법사가 보는 10명의 수를 모두 XOR 연산하면 \(S \oplus w_i\)가 된다. 이 수의 \(i\)번째 비트가 1이라면 왼손을, 0이라면 오른손을 든다.

(\(\oplus\) 연산에 익숙하지 않은 사람들을 위해, 자신을 제외하고 \(i\)번째 비트가 1인 사람의 수가 홀수명이면 왼손을, 짝수명이면 오른손을 든다)

11번째 마법사는 \(S \oplus w_{11}\) 의 비트에 1이 홀수개 있다면 왼손을, 짝수개 있다면 오른손을 든다.

(\(\oplus\) 연산에 익숙하지 않은 사람들을 위해, 자신을 제외하고 모든 사람들의 비트를 세서, 1이 홀수개라면 왼손을, 짝수개라면 오른손을 든다)

\(i\)번째 마법사가 \(w_i\)의 \(k\)번째 비트를 구할 때는 다음과 같이 구한다.

• \(k \ne i\)인 경우, \(S \oplus w_i \oplus w_k\)의 k번째 비트를 구한 뒤, \(k\)번째 마법사가 든 손 (\(S \oplus w_k\))과 \(\oplus\) 연산을 시행한다.

• \(k = i\) 인 경우, 위 방법으로 \(w_i\)의 \(i\)번째 비트를 제외한 모든 비트를 이제 알 수 있기 때문에, 11번째 마법사의 손을 보고 전체 비트의 홀짝성으로 구할 수 있다.

모자의 수가 이진법으로 최대 10자리이므로, 11번째 마법사는 11번째 비트를 구할 필요가 없다.