Erdös-Ginzburg-Ziv 정리
서론
0과 1이 $X$개 있을 때, 그 중 항상 같은 수가 $N$개 이상 있게 하는 최소의 $X$는 $2N-1$이다. $X=2N-2$인 경우에는, 0과 1이 $N-1$개 존재하면 불가능하다. $X = 2N-1$개 있을 때는, 비둘기집의 원리에 의해서 항상 0이 $N$개 혹은 1이 $N$개 존재한다.
우리는 이 비둘기집의 원리의 일반화된 버전을 생각해 본다. 임의의 정수가 $X$개 있을 때, 그 중 합이 $N$의 배수가 되는 $N$개를 고를 수 있는 최소의 $X$는 얼마인가? 수로 0과 1만 가능한 것이 아니라, 모든 정수가 가능하다. 다음 문제는, $X = 2N-1$일 때의 답이 무엇인지 질문한다.
$N$의 배수 (1), $N$의 배수 (2), $N$의 배수 (3)
Brute Force
$2N-1$개 중 수 $N$개를 고르는 경우의 수는 $\binom{2N-1}{N}$가지가 있다. 이 모두를 골라서 $N$의 배수가 되는지를 확인 해 보면, 문제의 답을 찾을 수 있을 것이다.
이 풀이는 지수시간이 걸리기도 하면서, 문제의 본질인 $N$의 배수라는 성질을 잘 이용하지 못하는 풀이이기도 하다. 시간복잡도는 구현에 따라서, $O\left(N \binom{2N-1}{N}\right)$혹은 $O\left(\binom{2N-1}{N}\right)$ 이 될 것이다.
Dynamic Programming $O(N^3)$
$N$의 배수 (1) 문제는 모든 경우를 확인해서 풀 수는 없는 문제이다. 우리는 동적계획법을 사용하여, 모든 경우를 탐색하지만 불필요하게 탐색하지는 않으려고 한다.
현재까지 우리가 수 $K$개를 골랐고, 이 수들의 합을 $N$으로 나눈 나머지가 $M$이라고 하자. 고른 $K$개의 수의 구성은 중요치 않고, 골라야 하는 나머지 수들이 $N-K$개 이고, 이 $N-K$개의 수를 $N$으로 나눈 나머지가 $(N-M) \bmod N$이어야 한다는 사실을 알 고 있다. 우리는 어떤 수를 골랐는지, 혹은 어떤 수를 고르지 않았는지에 대한 정보를 수 하나 하나씩 들고 다니면 Brute Force 방식과 다르지 않다는 것을 알고 있다. “골라야 하는 나머지 수들” 에서, 고를 수 있는 수의 여부를 확실히 하기 위해 우리는 수를 앞에서 부터 확인한다고 생각 할 것이다.
이 성질을 사용하면, 다음과 같은 동적 계획법 테이블을 생각할 수 있다.
$D_{i, j, k} = i$번째 수 까지 확인 해 봤을 때, $j$개의 수를 골라서 이들의 합을 $N$으로 나눈 나머지가 $K$가 되도록 할 수 있는가?
테이블은 다음과 같은 방식으로 채워나갈 수 있다. $a_i$를 $i$번째 수라고 쓰기로 한다.
- $D_{0,0,0}=true$
- 0개의 수 중 0개의 수를 골랐고, 합은 0이다.
- $D_{i, j, k} = true \rightarrow D_{i+1, j, k} = true$
- $i+1$번째 수를 고르지 않은 경우에, 고른 수의 개수와 고른 수들의 합은 변하지 않는다.
- $D_{i, j, k}= true \rightarrow D_{i+1, j+1, (k+a_{i+1}) \bmod N} = true$
- $i+1$번째 수를 고른 경우에, 고른 수의 개수가 1, 합이 $a_{i+1}$만큼 증가한다.
- 위 규칙에 의해 $true$가 아니면, 모두 $false$이다.
- 위 동적계획법 테이블을 채울 때, $i+1$번째 수를 고른 경우와 고르지 않은 경우를 모두 고려한다.
이제 문제에서 원하는 $2N-1$번째 수 까지 확인 해 봤을 때, $N$개의 수를 골라서 이들의 합을 $N$으로 나눈 나머지가 $0$이 되도록 할 수 있는지인 $D_{2N-1, N, 0}$이 $true$인지 $false$인지 확인하자. 이 여부에 따라서 답이 가능한지 불가능 한지를 알 수 있다. 문제에서 요구하는 실제로 수의 역추적도 진행해 주자.
$D_{i, j, k}$가 $true$이고, $D_{i-1, j-1, (k-a_i) \bmod N}$이 $true$이면, $j$개의 합을 $N$으로 나눈 나머지가 $k$가 되도록 할 때, $i$번째 수를 이용해서 만들 수 있다. 만약 $D_{i-1, j-1, (k-a_i) \bmod N}$이 $false$이면, $D_{i-1,j,k}$가 $true$이고 $i$번째 수를 이용하지 않았음을 알 수 있다. ($D_{i-1, j, k}$가 $true$라는 것은 동적계획법의 정의에서 알 수 있다.) 이 방법으로 $i=2n-1$부터 $i=1$까지 어떤 수들을 사용했고, 사용하지 않았는지 확인 해 줄 수 있다.
한 가지 가능한 구현은, 현재 집합은 비어있고, 집합에 앞으로 $j$개를 채워야 하고, 채워야 하는 수들을 $N$으로 나눈 나머지가 $k$라고 하고 집합을 뒤에서 부터 채워나가는 법이 있다. 처음에 $j=N, k =0$으로 시작한다. $i=2n-1$부터 $i=1$까지 감소시키면서, $D_{i-1, j-1, (k-a_i)\bmod N}$이 $true$이면, $j$를 $j-1$로 바꾸고, $k$를 $(k-a_i) \bmod N$으로 바꾸고, 집합에 $a_i$를 추가하면 된다.
실제로 구현한 코드는 다음과 같다.
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 500;
bool dp[2*MAXN][MAXN+1][MAXN];
int N;
int arr[2*MAXN-1];
int main() {
int N; cin >> N;
for(int i=0; i<2*N-1; ++i) cin >> arr[i];
dp[0][0][0] = 1;
for(int i=1; i<=2*N-1; ++i) {
for(int j=0; j<=N; ++j)
for(int k=0; k<N; ++k)
dp[i][j][k] = dp[i-1][j][k];
for(int j=1; j<=N; ++j)
for(int k=0; k<N; ++k) {
int s = k - arr[i-1]; if(s<0) s += N;
if(dp[i-1][j-1][s]) dp[i][j][k] = true;
}
}
assert(dp[2*N-1][N][0]);
int j = N, k = 0;
for(int i=2*N-1; i>=1 && j>0; --i) {
int s = k - arr[i-1]; if(s<0) s += N;
if(dp[i-1][j-1][s]) {
j = j-1; k = s;
printf("%d ", arr[i-1]);
}
}
puts("");
}
Erdös-Ginzburg-Ziv 정리
이제 이 문제에 대한 수학적인 성질을 관찰 할 때이다. 실제로 실험을 해 보면, 어떤 데이터를 넣어도 답이 항상 존재하는 것으로 보인다. 실제로 이것이 맞고, 다음 정리가 이를 뒷받침 해 준다.
- Erdös-Ginzburg-Ziv theorem (1961)
- 수 $2N-1$개가 주어졌을 때, 이 중 수 $N$개를 골라서 합이 $N$의 배수가 되도록 할 수 있다.
이 증명은 $N$이 소수, 합성수 혹은 1인 경우로 나뉘어서 증명하고, 합성수에 대한 증명은 깔끔한 증명과 결론으로 자주 연습문제로 등장한다. $N$이 소수인 경우의 증명이 어렵다고 주로 알려져 있지만, 이 글에서는 간단한 증명을 소개한다. 처음 증명된 방식은 이 방식이 아니라 군론에 대한 깊은 지식이 필요하기 때문에 증명이 어렵다고 자주 알려져 있다.
이 증명에서는 ($N$이 합성수인 경우를 증명하기 위해서) 강한 수학적 귀납법을 사용할 것이다. $N=1$일 때 참이고, $N=1, 2, \cdots, k-1$일 때 참인 결과로 $N=k$인 경우를 증명할 수 있으면, 우리는 모든 $N$에 대해서 해당 명제가 참이라는것을 증명할 수 있다.
- $N=1$인 경우는 쉽다. 해당하는 수 하나를 골라주면, 그 수는 1의 배수이다.
$N \ge 2$, 합성수
$N=ab$이고, $a, b\ge 2$라고 하자. 우리는 $2a-1$개의 수를 골라서 합이 $a$의 배수가 되게 할 수 있고, $2b-1$개를 골라서 합이 $b$의 배수가 되게 할 수 있다는, 강한 수학적 귀납법의 귀납 가정을 사용한다. ($a, b < N$이기 때문에 사용할 수 있다.)
총 $2ab-1$개의 수 중 $2a-1$개의 수를 뽑아서, 합이 $a$의 배수가 되도록 할 수 있다. 이렇게 $a$개의 수를 제외하게 되면, 나머지는 $a(2b-1)-1$개의 수가 남게 된다.
$2a-1$개의 수를 뽑아서 합이 $a$의 배수가 되도록 $a$개를 뽑는 작업을 $x$번 반복하면, $a(2b-x)-1$개의 수가 남게 되고, 우리는 이 작업을 $a(2b-x)-1 \ge 2a-1$을 만족 하는 한 반복 할 수 있다. $x=2b-2$일 때 작업을 한 번 더 해서 총 $2b-1$번의 작업을 할 수 있다. 여기서, $i$번째 작업에서 뽑은 수 들의 합을 $s_i$라고 하자.
우리는 이제 $2b-1$개의 새 정수 $\dfrac{s_1}{a}, \dfrac{s_2}{a}, \cdots, \dfrac{s_{2b-1}}{a}$를 모았다. $s_i$는 모두 $a$의 배수이기 때문에, $a$로 나누어도 정수이다. 이 $\dfrac{s_i}{a}$ 수들 중 $b$개를 뽑아서, 합이 $b$의 배수가 되도록 할 수 있다. 즉, 다시 말해서 $s_i$ 수들 중에서 $b$개를 뽑아서, 합이 $ab$의 배수가 되도록 할 수 있다는 의미이다. $s_i$를 다시 $a$개의 수의 합으로 풀어 쓰면, 원래 $2N-1$개의 수 중 $ab$개의 수를 골라서 합이 $ab$의 배수가 되도록 할 수 있다.
$N \ge 2$, 소수
$2N-1$개의 수 중에서 같은 수가 $N$개 이상 존재하면, 해당 수를 $N$개 고른 경우 합이 $N$의 배수가 된다,
같은 수가 $N$개 존재하지 않은 경우, 수 $2N-1$개를 $x, (a_1, b_1), (a_2, b_2), \cdots, (a_{N-1}, b_{N-1})$과 같이 재배열 할 수 있다. 여기서, $a_i \ne b_i$를 만족하도록 재배열 해야 한다. (편의상 $x=a_0 = b_0$라고 하자.)
우리는 $S_k$를 $a_0, b_0$ 중 하나, $a_1, b_1$중 하나, $\cdots$, $a_k, b_k$중 하나를 골라서 총 $k+1$개를 골라서 (가능한 $2^{k+1}$ 가지의 경우에서) 합을 $N$으로 나눈 나머지의 집합이라고 정의 할 것이다.
예를 들면,
- $S_0 = {x \bmod N}$
- $S_1 = {(x+a_1) \bmod N, (x+b_1) \bmod N}$
- $S_2 = {(x+a_1+a_2) \bmod N, (x+b_1+a_2) \bmod N,(x+a_1+b_2) \bmod N, (x+b_1+b_2) \bmod N}$
와 같은 방식이다.
우리는 새로운 Lemma를 정의 할 것이다. $S_k$의 원소의 개수가 $k+1$개 이상임을 수학적 귀납법으로 증명한다.
$\mid S_k \mid > k$
$k=0$이면 $S_0$의 원소는 1개 이상임이 자명하다.
$k = n \rightarrow k = n+1$, $S_n$의 원소의 개수가 $n+1$개 이상이면, $S_{n+1}$의 원소의 개수도 $n+1$개 이상임이 자명하다.
$S_n$의 원소의 개수를 $n$개라고 하고, 각 원소를 ${s_1, s_2, \cdots, s_n}$나열하자. 이제 $S_{n+1}$은 다음과 같은 방식으로 표현 될 수 있다.
- $A = {(a_{n+1}+s_1) \bmod N, (a_{n+1}+s_2) \bmod N, \cdots, (a_{n+1}+s_n) \bmod N }$
- $B = {(b_{n+1}+s_1) \bmod N, (b_{n+1}+s_2) \bmod N, \cdots, (b_{n+1}+s_n) \bmod N }$
- $S_{n+1} = A \cup B$
여기서 $ \mid A \mid = \mid B\mid = n$이기 때문에, $A \ne B$ 라면, $\mid A \cup B \mid \ge n+1$ 이라는 것을 알 수 있다. 여기서 $A \ne B$라는 것을 보이기 위해서, $A$와 $B$의 있는 모든 수의 합을 $N$으로 나눈 나머지의 차이를 구해보면, $\left(\sum_{a \in A} a - \sum_{b \in B} b\right) \bmod N$ $=\left( (na_{n+1} - \sum_{i=1}^n s_i)-(nb_{n+1} - \sum_{i=1}^n s_i) \right) \bmod N$ $= \left( n(a_{n+1}-b_{n+1}) \right) \bmod N$이다. $a_{n+1} \ne b_{n+1}$ 이고, $n <N$이고 $N$은 소수이기 때문에, $n(a_{n+1} - b_{n+1})$는 $N$의 배수가 될 수 없다. 즉, $A \ne B$이며 $\mid A \cup B \mid \ge n+1$이다.
$S_{N-1}$의 원소의 개수는 $(N-1)+1 = N$개 이상이기 때문에, 0부터 $N-1$까지의 수를 모두 포함한다. $S_{N-1}$이 0을 포함하기 때문에, 수를 적당히 $N$개 골라서 합이 $N$의 배수가 되는 $N$개의 수가 존재한다.
이로서, Erdös-Ginzburg-Ziv theorem이 증명되었다.
구현
위에 쓰인 증명을 그대로 구현 해 주면 된다. $N$이 소수일 때, $S_i$집합을 동적계획법과 같은 방법으로 관리 해 준다. $S_i$ 하나를 관리 할 때, 총 $O(N)$ 시간이 들기 때문에, 총 $O(N^2)$의 시간이 든다. 시간복잡도는 다음과 같다.
- $T(N)$을 $N$일 때의 시간이라고 하자.
- $N = ab$가 합성수: $T(ab) = (2b-1)T(a)+T(b)+O(N)$.
- $N$이 소수: $T(N) = O(N^2)$.
여기서 master의 정리를 사용하면 $T(N) = O(N^2)$이라는 것을 알 수 있다.
실제로 구현을 할 때는, $S_i$가 0 이상 $N-1$이하의 수들만 담는다는 것을 이용해서 std::bitset 등으로 최적화 해 주면, $O(N^2 / w)$ 시간에 문제를 해결할 수 있다. (여기서 $w$는 한 연산에 처리할 수 있는 word 크기이다.)
시간 복잡도도 마찬가지이지만 상수를 줄이기 위해서 $N=ab$로 소인수 분해 되는 경우에 $a$를 작은 값으로 고르는 등의 섬세한 구현이 필요하다. 예를 들어, $a$를 큰 값으로 고르고, 수가 $2^N$꼴일 때 시간복잡도 분석을 해 보면, $T(2^N) = 3T(2^{N-1}) + T(2) + O(2^N)$ 이다. Master 정리를 이용하면 $T(2^N) = T(3^N)$ 이라는 것을 알 수 있다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50000;
void set(int N, uint64_t* dest, int k) {
int n = k>>6; int b = k&63;
dest[n] |= uint64_t(1)<<(63-b);
}
bool isset(int N, uint64_t* dest, int k) {
int n = k>>6; int b = k&63;
return (dest[n] & uint64_t(1)<<(63-b));
}
void clear(int N, uint64_t* dest) {
N = (N+63)>>6;
memset(dest, 0, N*sizeof(uint64_t));
}
void rshiftor(int N, int k, uint64_t* src, uint64_t* dest) {
int rN = N;
N = (N+63) >> 6;
int n = k >> 6; int b = k&63;
if(b) {
dest[n] |= src[0] >> b;
for(int i=1; n+i<N; ++i)
dest[n+i] |= (src[i-1] << (64-b)) | (src[i]>>b);
}
else {
for(int i=0; n+i<N; ++i)
dest[n+i] |= src[i];
}
int rem = rN&63;
if(rem) {
uint64_t mask = (uint64_t(1) << (64-rem)) - 1;
dest[N-1] &= ~mask;
}
}
void lshiftor(int N, int k, uint64_t* src, uint64_t* dest) {
int rN = N;
N = (N+63)>>6;
int n = k >> 6; int b = k&63;
if(b) {
for(int i=0; n+i+1<N; ++i)
dest[i] |= (src[n+i] << b) | (src[n+i+1] >> (64-b));
dest[N-n-1] |= src[N-1] << b;
}
else {
for(int i=0; n+i<N; ++i)
dest[i] |= src[n+i];
}
int rem = rN&63;
if(rem) {
uint64_t mask = (uint64_t(1) << (64-rem)) - 1;
dest[N-1] &= ~mask;
}
}
void bitcopy(int N, uint64_t* src, uint64_t* dest) {
N = (N+63)>>6;
memcpy(dest, src, N*sizeof(uint64_t));
}
uint64_t dp[MAXN][(MAXN+63)/64];
vector<bool> EGZ(int, vector<int>);
vector<bool> EGZ_prime(int p, vector<int> arr) {
if(p==1) return {true};
vector<bool> ret(2*p-1, false);
for(int i=0; i<2*p-1; ++i) arr[i] %= p;
vector<int> idx(2*p-1); iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int a, int b){return arr[a]<arr[b];});
for(int i=0; i<p; ++i) {
if(arr[idx[i]] == arr[idx[i+p-1]]) {
for(int j=i; j<i+p; ++j) ret[idx[j]] = true;
return ret;
}
}
int imod = 0;
for(int i=0; i<p; ++i) {
imod += arr[idx[i]];
if(imod >= p) imod -= p;
ret[idx[i]] = true;
}
if(imod == 0) return ret;
clear(p, dp[0]); set(p, dp[0], imod);
int i;
for(i=1; i<p; ++i) {
int d = arr[idx[i+p-1]] - arr[idx[i]];
bitcopy(p, dp[i-1], dp[i]);
rshiftor(p, d, dp[i-1], dp[i]);
lshiftor(p, p-d, dp[i-1], dp[i]);
if(isset(p, dp[i], 0)) break;
}
assert(i != p);
int cur = 0;
for(int j=i; j>=1; --j) {
int d = arr[idx[j+p-1]] - arr[idx[j]];
int ncur = cur-d; if(ncur<0) ncur += p;
if(isset(p, dp[j-1], ncur)) {
ret[idx[j]] = false;
ret[idx[j+p-1]] = true;
cur = ncur;
}
}
return ret;
}
vector<bool> EGZ_composite(int a, int b, vector<int> arr) {
vector<vector<int> > index;
vector<int> index_vector;
int tp = 0;
for(int j=0; j<a-1; ++j)
index_vector.push_back(tp++);
for(int i=0; i<2*b-1; ++i) {
for(int j=0; j<a; ++j) index_vector.push_back(tp++);
vector<int> recur_vector(2*a-1);
for(int i=0; i<2*a-1; ++i) recur_vector[i] = arr[index_vector[i]];
vector<bool> recur_answer = EGZ(a, recur_vector);
vector<int> push_index, remain_index;
for(int i=0; i<2*a-1; ++i)
if(recur_answer[i]) push_index.push_back(index_vector[i]);
else remain_index.push_back(index_vector[i]);
index_vector = remain_index;
index.push_back(push_index);
}
vector<int> sum_vector(2*b-1);
for(int i=0; i<2*b-1; ++i) {
long long sv = 0;
for(int j=0; j<a; ++j) sv += arr[index[i][j]];
sum_vector[i] = sv/a%b;
}
vector<bool> rec = EGZ(b, sum_vector);
vector<bool> ret(2*a*b-1, false);
for(int i=0; i<2*b-1; ++i)
if(rec[i])
for(int j: index[i])
ret[j] = true;
return ret;
}
vector<bool> EGZ(int N, vector<int> arr) {
for(int i=2; i<N; ++i)
if(N%i == 0)
return EGZ_composite(i, N/i, arr);
return EGZ_prime(N, arr);
}
int main() {
int N; cin >> N;
vector<int> V;
for(int i=0; i<2*N-1; ++i) {
int t; cin >> t;
V.push_back(t);
}
vector<bool> ans = EGZ(N, V);
for(int i=0; i<2*N-1; ++i)
if(ans[i])
cout << V[i] << " ";
cout << endl;
return 0;
}