ho94949's profile image

ho94949

March 18, 2020 15:00

Erdös-Ginzburg-Ziv 정리

Mathematics , Number theory

서론

0과 1이 개 있을 때, 그 중 항상 같은 수가 개 이상 있게 하는 최소의 이다. 인 경우에는, 0과 1이 개 존재하면 불가능하다. 개 있을 때는, 비둘기집의 원리에 의해서 항상 0이 개 혹은 1이 개 존재한다.

우리는 이 비둘기집의 원리의 일반화된 버전을 생각해 본다. 임의의 정수가 개 있을 때, 그 중 합이 의 배수가 되는 개를 고를 수 있는 최소의 는 얼마인가? 수로 0과 1만 가능한 것이 아니라, 모든 정수가 가능하다. 다음 문제는, 일 때의 답이 무엇인지 질문한다.

의 배수 (1), 의 배수 (2), 의 배수 (3)

Brute Force

개 중 수 개를 고르는 경우의 수는 가지가 있다. 이 모두를 골라서 의 배수가 되는지를 확인 해 보면, 문제의 답을 찾을 수 있을 것이다.

이 풀이는 지수시간이 걸리기도 하면서, 문제의 본질인 의 배수라는 성질을 잘 이용하지 못하는 풀이이기도 하다. 시간복잡도는 구현에 따라서, 혹은 이 될 것이다.

Dynamic Programming

의 배수 (1) 문제는 모든 경우를 확인해서 풀 수는 없는 문제이다. 우리는 동적계획법을 사용하여, 모든 경우를 탐색하지만 불필요하게 탐색하지는 않으려고 한다.

현재까지 우리가 수 개를 골랐고, 이 수들의 합을 으로 나눈 나머지가 이라고 하자. 고른 개의 수의 구성은 중요치 않고, 골라야 하는 나머지 수들이 개 이고, 이 개의 수를 으로 나눈 나머지가 이어야 한다는 사실을 알 고 있다. 우리는 어떤 수를 골랐는지, 혹은 어떤 수를 고르지 않았는지에 대한 정보를 수 하나 하나씩 들고 다니면 Brute Force 방식과 다르지 않다는 것을 알고 있다. “골라야 하는 나머지 수들” 에서, 고를 수 있는 수의 여부를 확실히 하기 위해 우리는 수를 앞에서 부터 확인한다고 생각 할 것이다.

이 성질을 사용하면, 다음과 같은 동적 계획법 테이블을 생각할 수 있다.

번째 수 까지 확인 해 봤을 때, 개의 수를 골라서 이들의 합을 으로 나눈 나머지가 가 되도록 할 수 있는가?

테이블은 다음과 같은 방식으로 채워나갈 수 있다. 번째 수라고 쓰기로 한다.

    • 0개의 수 중 0개의 수를 골랐고, 합은 0이다.
    • 번째 수를 고르지 않은 경우에, 고른 수의 개수와 고른 수들의 합은 변하지 않는다.
    • 번째 수를 고른 경우에, 고른 수의 개수가 1, 합이 만큼 증가한다.
  • 위 규칙에 의해 가 아니면, 모두 이다.
    • 위 동적계획법 테이블을 채울 때, 번째 수를 고른 경우와 고르지 않은 경우를 모두 고려한다.

이제 문제에서 원하는 번째 수 까지 확인 해 봤을 때, 개의 수를 골라서 이들의 합을 으로 나눈 나머지가 이 되도록 할 수 있는지인 인지 인지 확인하자. 이 여부에 따라서 답이 가능한지 불가능 한지를 알 수 있다. 문제에서 요구하는 실제로 수의 역추적도 진행해 주자.

이고, 이면, 개의 합을 으로 나눈 나머지가 가 되도록 할 때, 번째 수를 이용해서 만들 수 있다. 만약 이면, 이고 번째 수를 이용하지 않았음을 알 수 있다. (라는 것은 동적계획법의 정의에서 알 수 있다.) 이 방법으로 부터 까지 어떤 수들을 사용했고, 사용하지 않았는지 확인 해 줄 수 있다.

한 가지 가능한 구현은, 현재 집합은 비어있고, 집합에 앞으로 개를 채워야 하고, 채워야 하는 수들을 으로 나눈 나머지가 라고 하고 집합을 뒤에서 부터 채워나가는 법이 있다. 처음에 으로 시작한다. 부터 까지 감소시키면서, 이면, 로 바꾸고, 으로 바꾸고, 집합에 를 추가하면 된다.

실제로 구현한 코드는 다음과 같다.

#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)
    • 개가 주어졌을 때, 이 중 수 개를 골라서 합이 의 배수가 되도록 할 수 있다.

이 증명은 이 소수, 합성수 혹은 1인 경우로 나뉘어서 증명하고, 합성수에 대한 증명은 깔끔한 증명과 결론으로 자주 연습문제로 등장한다. 이 소수인 경우의 증명이 어렵다고 주로 알려져 있지만, 이 글에서는 간단한 증명을 소개한다. 처음 증명된 방식은 이 방식이 아니라 군론에 대한 깊은 지식이 필요하기 때문에 증명이 어렵다고 자주 알려져 있다.

이 증명에서는 (이 합성수인 경우를 증명하기 위해서) 강한 수학적 귀납법을 사용할 것이다. 일 때 참이고, 일 때 참인 결과로 인 경우를 증명할 수 있으면, 우리는 모든 에 대해서 해당 명제가 참이라는것을 증명할 수 있다.

  • 인 경우는 쉽다. 해당하는 수 하나를 골라주면, 그 수는 1의 배수이다.

, 합성수

이고, 라고 하자. 우리는 개의 수를 골라서 합이 의 배수가 되게 할 수 있고, 개를 골라서 합이 의 배수가 되게 할 수 있다는, 강한 수학적 귀납법의 귀납 가정을 사용한다. (이기 때문에 사용할 수 있다.)

개의 수 중 개의 수를 뽑아서, 합이 의 배수가 되도록 할 수 있다. 이렇게 개의 수를 제외하게 되면, 나머지는 개의 수가 남게 된다.

개의 수를 뽑아서 합이 의 배수가 되도록 개를 뽑는 작업을 번 반복하면, 개의 수가 남게 되고, 우리는 이 작업을 을 만족 하는 한 반복 할 수 있다. 일 때 작업을 한 번 더 해서 총 번의 작업을 할 수 있다. 여기서, 번째 작업에서 뽑은 수 들의 합을 라고 하자.

우리는 이제 개의 새 정수 를 모았다. 는 모두 의 배수이기 때문에, 로 나누어도 정수이다. 이 수들 중 개를 뽑아서, 합이 의 배수가 되도록 할 수 있다. 즉, 다시 말해서 수들 중에서 개를 뽑아서, 합이 의 배수가 되도록 할 수 있다는 의미이다. 를 다시 개의 수의 합으로 풀어 쓰면, 원래 개의 수 중 개의 수를 골라서 합이 의 배수가 되도록 할 수 있다.

, 소수

개의 수 중에서 같은 수가 개 이상 존재하면, 해당 수를 개 고른 경우 합이 의 배수가 된다,

같은 수가 개 존재하지 않은 경우, 수 개를 과 같이 재배열 할 수 있다. 여기서, 를 만족하도록 재배열 해야 한다. (편의상 라고 하자.)

우리는 중 하나, 중 하나, , 중 하나를 골라서 총 개를 골라서 (가능한 가지의 경우에서) 합을 으로 나눈 나머지의 집합이라고 정의 할 것이다.

예를 들면,

와 같은 방식이다.

우리는 새로운 Lemma를 정의 할 것이다. 의 원소의 개수가 개 이상임을 수학적 귀납법으로 증명한다.

이면 의 원소는 1개 이상임이 자명하다.

, 의 원소의 개수가 개 이상이면, 의 원소의 개수도 개 이상임이 자명하다.

의 원소의 개수를 개라고 하고, 각 원소를 나열하자. 이제 은 다음과 같은 방식으로 표현 될 수 있다.

여기서 이기 때문에, 라면, 이라는 것을 알 수 있다. 여기서 라는 것을 보이기 위해서, 의 있는 모든 수의 합을 으로 나눈 나머지의 차이를 구해보면, 이다. 이고, 이고 은 소수이기 때문에, 의 배수가 될 수 없다. 즉, 이며 이다.

의 원소의 개수는 개 이상이기 때문에, 0부터 까지의 수를 모두 포함한다. 이 0을 포함하기 때문에, 수를 적당히 개 골라서 합이 의 배수가 되는 개의 수가 존재한다.

이로서, Erdös-Ginzburg-Ziv theorem이 증명되었다.

구현

위에 쓰인 증명을 그대로 구현 해 주면 된다. 이 소수일 때, 집합을 동적계획법과 같은 방법으로 관리 해 준다. 하나를 관리 할 때, 총 시간이 들기 때문에, 총 의 시간이 든다. 시간복잡도는 다음과 같다.

  • 일 때의 시간이라고 하자.
    • 가 합성수: .
    • 이 소수: .

여기서 master의 정리를 사용하면 이라는 것을 알 수 있다.

실제로 구현을 할 때는, 가 0 이상 이하의 수들만 담는다는 것을 이용해서 std::bitset 등으로 최적화 해 주면, 시간에 문제를 해결할 수 있다. (여기서 는 한 연산에 처리할 수 있는 word 크기이다.)

시간 복잡도도 마찬가지이지만 상수를 줄이기 위해서 로 소인수 분해 되는 경우에 를 작은 값으로 고르는 등의 섬세한 구현이 필요하다. 예를 들어, 를 큰 값으로 고르고, 수가 꼴일 때 시간복잡도 분석을 해 보면, 이다. Master 정리를 이용하면 이라는 것을 알 수 있다.

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