문제는 : https://arca.live/b/math/39723739
----------------------------------------------------------------------------------------------
수학채널 게임의 규칙은 다음과 같다:
1, A와 B는 번갈아가면서 숫자를 쓰며, A가 먼저 숫자를 쓴다.
2, 처음에는 숫자가 1이 써져 있으며, 숫자가 k가 써져 있으면 각 차례의 사람은 이 숫자를 지우고 k+1이나 2k를 다시 써 넣는다.
3, n 이상의 수는 쓸 수 없으며, 더이상 수를 쓸 수 없는 사람이 죽는다.
(1) n이 짝수일 때 누가 필승전략을 가지는가?
(2) n = 4^t +1일때 누가 필승전략을 가지는가?
(3) 일반적인 n에 대해 누가 필승전략을 가지는가?
----------------------------------------------------------------------------------------------
댓글로 다른 분들도 풀어주셨고 저도 어느정도 써놓기는 했는데, 좀 더 "건너뛰는 부분이 적은" 풀이를 작성해 보도록 하겠습니다.
이것도 아주 formal 하지는 않고, 왠지 자꾸 알고리즘의 psuedo code를 짜는 듯한 형태가 되는군요. 
대체로 dynamic programming 의 응용입니다.
T(n, k)를 다음과 같이 정의한다.
T(n, k) = 주어진 숫자가 n일 때 k를 쓴 사람에게 필승 전략이 있으면 1, 상대에게 필승 전략이 있으면 0
예컨대 한 사람이 n 이상의 수를 썼다면, 문제의 조건에 따라서 그 사람은 패배한다. 따라서 T(n, m) = 0 for m ≧ n
만약 한 사람이 n-1을 썼다면, 그 다음 사람은 n 이상의 수를 쓸 수밖에 없으므로 n-1 을 쓴 사람이 승리한다.
따라서 T(n, n-1) = 1
T(n, k)의 값은 다음과 같다.
T(n, k) = 0 (k ≧ n 또는 T(n, 2k) = 1 또는 T(n, k+1) = 1 인 경우)
T(n, k) = 1 (k < n 이며 T(n, 2k) = T(n, k+1) = 0 인 경우)
이 게임은 B가 1을 쓰고 시작하는 것과 같으므로 T(n, 1) = 1 이면 B의 승리, T(n, 1) = 0 이면 A의 승리이다.
(1) n 이 짝수인 경우. Let n = 2m
m ≦ k < 2m 인 k 에 대해서, T(n, 2k) = L 이므로 T(n, k) = 1 - T(n, k+1)
따라서 k가 홀수이면 T(n, k) = 1, k가 짝수이면 T(n, k) = 0
k < m 인 경우는
T(n, 2m-2) = 0 이므로 T(n, m-1) = 1 - T(n, m)
T(n, 2m-4) = 0 이므로 T(n, m-2) = 1 - T(n, m-1)
...
따라서 k < 2m 인 모든 자연수 k 에 대해서 가 홀수이면 T(n, k) = 1, k가 짝수이면 T(n, k) = 0
고로 T(n, 1) = 1 이므로 B의 승리.
(2) n 이 홀수이고 n = 2m+1 에서 m이 짝수인 경우
Let m = 2v, n = 4v + 1
2v+1 ≦ k ≦ 4v 인 k 에 대해서, k가 짝수이면 T(n, k) = 1, k가 홀수이면 T(n, k) = 0
v+1 ≦ k ≦ 2v 인 k 에 대해서, 2v+1 < 2k ≦ 4v 이므로 T(n, 2k) = 1, 따라서 T(n, k) = 0
즉 v+1 ≦ k ≦ 2v 인 모든 k 에 대해서 T(n, k) = 0 이므로
k ≦ v인 k 에 대해서 T(n, k) = T(4v+1) = T(v+1, k)
그러므로 n = 4^t +1일 때
T(n, 1) = T(4^t + 1, 1) = T(4^(t-1) + 1, 1) = T(4^(t-2) + 1, 1) = ... = T(4^0 + 1, 1) = T(2, 1) = 1
따라서 B의 승리
(3) n 이 홀수이고 n = 2m+1 에서 m이 짝수인 경우는 (2)에서 다루었고, m 이 홀수인 경우
Let m = 2v + 1, n = 4v + 3
2v+2 ≦ k ≦ 4v+2 인 k 에 대해서, k가 짝수이면 T(n, k) = 1, k가 홀수이면 T(n, k) = 0
v+1 ≦ k ≦ 2v+1 인 k 에 대해서, 2v+2 ≦ 2k ≦ 4v+2 이므로 T(n, 2k) = 1, 따라서 T(n, k) = 0
즉 v+1 ≦ k ≦ 2v 인 모든 k 에 대해서 T(n, k) = 0 이므로
k ≦ v인 k 에 대해서 T(n, k) = T(4v+3) = T(v+1, k)
m이 짝수인 경우와 홀수인 경우를 종합하면 T(4v+1, 1) = T(4v+3, 1) = T(v+1, 1) 를 얻는다.
즉 n이 홀수라면 T(n, 1) = T([n/4]+1, 1) ([r] 은 r보다 작거나 같은 최대의 정수)
이제 다음과 같은 수열을 생각한다.
- a_1 = n
- a_(i+1) = [a_i / 4] + 1
- 모든 i에 대해서 a_i 는 자연수, a_j = 1 이면 a_j 는 수열의 마지막 원소
이 수열의 원소 중 하나라도 짝수이면 T(n, 1) = 1 이 되므로, T(n, 1) = 0 일 필요충분조건은 이 수열의 모든 원소가 홀수라는 것이다.
이는 1 에서 시작해서 v+1 => 4v+1, 4v+3 의 과정을 통해서 생성할 수 있는 홀수들에 대해서만 T(n, 1) = 0 을 만족한다는 말과 같다.
그런데 v+1 = 2^m_1 + 2^m_2 + ... + 2^m_k + 1(m_1 > m_2 > ... > m_k >= 1 인 자연수) 의 형태로 나타냈을 때
m_i 가 모두 홀수임을 v+1 이 만족한다면
4v+1 = 2^(m_1 + 2) + 2^(m_2 + 2) + ... + 2^(m_k + 2) + 1
4v+3 = 2^(m_1 + 2) + 2^(m_2 + 2) + ... + 2^(m_k + 2) + 2^1 + 1
4v+1, 4v+3 역시 이를 만족한다.
따라서 A 가 승리할 필요충분조건은
n 이 홀수이고
n = 2^m_1 + 2^m_2 + ... + 2^m_k + 1(m_1 > m_2 > ... > m_k >= 1 인 자연수) 의 형태로 나타냈을 때 m_i 가 모두 홀수라는 것이다.
