ho94949's profile image

ho94949

March 18, 2020 15:00

Erdös-Ginzburg-Ziv 정리

Mathematics , Number theory

서론

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;
}