마법사와 모자 1

문제

1000명의 마법사와 1부터 1001까지의 자연수가 하나씩 적힌 모자 1001개가 있다.
마법사들은 일렬로 서 모자를 하나씩 랜덤으로 쓰게 된다. 사용되지 않은 1개의 모자는 버려진다.

마법사들은 자신보다 앞에 있는 사람들이 쓴 모자들의 수를 모두 볼 수 있다.
예로 들어, 가장 뒷 마법사는 앞 999개의 수를 모두 볼 수 있으며, 가장 앞 마법사는 아무 수도 볼 수 없다.

가장 뒷 마법사부터 가장 앞 마법사까지 차례대로 1부터 1001까지의 자연수 중 하나를 부른다. 단, 이미 불린 수는 다시 부를 수 없다.
모두가 수를 부른 뒤, 자신이 쓴 모자의 수를 부르지 못한 마법사들은 모두 숙청당한다.

마법사들은 모자를 쓰기 전 전략회의를 할 시간이 주어진다. 이때,

a) 최소 500명을 살릴 수 있는 전략이 있을까?
b) 최소 999명을 살릴 수 있는 전략이 있을까?

풀이

a) 최소 500명을 살릴 수 있는 전략이 있을까?

살릴 수 있다. 최소 997명을 살릴 수 있는 전략을 소개한다.

편의를 위해 가장 뒷 마법사부터 가장 앞 마법사까지 1 부터 1000까지 번호를 붙이고. \(i\)번째 마법사의 수는 \(w_i\)라 두자.

1. 1번째 마법사는 \(R := \sum_{2}^{1000}w_i \pmod{1001}\) 을 부른다. \(R=0\) 이라면 대신 \(1001\)을 부른다.

2. i번째 (\(2 \le i \le 999\)) 마법사는 \((방금 불린 수 - \sum_{i+1}^{1000}{w_i}) \pmod{1001}\) 을 계산하면 자신의 수 \(w_i\)를 계산할 수 있다.

\({w_i} = R\)인 \(i\)를 \(k\)라 두자. \(k\)번째 마법사는 \(R\)이 이미 불렸기 때문에, 다시 부를 수 없다. 이 경우 가장 앞 사람의 수 \(w_{1000}\)을 부른다.

\(w_{1000}\)는 본인을 제외한 다른 모두가 볼 수 있으므로, \({w_k}=R\)임을 다른 마법사들도 알 수 있다. 해당 정보를 이용하여 계속 이 전략을 수행한다.

1. 1000번째 마법사는 앞 전략을 사용하여 계산한 수를 부를 수 있다면 부르고, 그렇지 않다면 남은 수들 중 아무 수를 부른다..

이 전략으로 1번째, \(k\)번쨰, 1000번째 마법사를 제외하고 모두가 생존할 수 있다.

b) 최소 999명을 살릴 수 있는 전략이 있을까?

살릴 수 있다.

이 풀이는 순열의 홀짝성에 관한 성질을 이용한다.

편의를 위해 가장 뒷 마법사부터 가장 앞 마법사까지 1 부터 1000까지 번호를 붙이고. \(i\)번째 마법사의 수는 \(w_i\)라 두자. 버려진 모자는 \(w_0\)이라 두자.

1번째 마법사가 알고있는 정보로는 순열이 \(w_0, w_1, ... w_{1000}\) 또는 \(w_1, w_0, ... w_{1000}\) 중 하나임을 알 수 있다.

순열의 홀짝성에 의해 둘 중 한쪽만 홀순열이다. 둘 중 홀순열을 택해 자신의 수를 부른다.$$

그 다음 마법사부터는 가능한 순열 두 가지중 홀순열인 경우를 택하여 자신의 수를 부르면 된다.

이 방법으로 1번째 마법사를 제외한 모두가 생존할 수 있다.

출처

Tournament of Towns