취미로 코딩하기

이 글은 요세푸스 문제(Josephus Problem)가 무엇인지, 그리고 요세푸스 문제의 해법에 대한 내용을 대략적으로 정리해둔 글이다.

1. 유래

요세푸스 문제는 1세기 로마시대의 유대인 역사가인 플라비우스 요세푸스(Titus Flavius Josephus)의 이름을 따 이름붙은 문제로 그 유래는 다음과 같다.

유대-로마 전쟁이 일어나던 시기, 요세푸스와 40명의 동료가 로마군에게 포위되었다. 동료들은 로마군에게 죽을 바에는 스스로 목숨을 끊기로 결정한다. 그러나 유대교에서 자살은 불명예스러운 죽음이므로, 서로 대신 죽여주기로 결정하였다.
구체적인 방법은 전해지지 않지만 그 방법에 대한 야사가 존재한다. 요세푸스와 동료들은 원형으로 둘러앉아, 앉은 순서대로 3명에 한 명씩 규칙적으로 죽여나갔다는 것이다. 그러나 다른 동료들과 달리 죽고싶지 않았던 요세푸스와 그의 친구는 기지를 발휘해 그 둘이 마지막까지 생존할 자리를 계산했고, 그 둘은 결국 죽지 않고 살아남게 된다. 이후 둘은 로마군에 투항하게 된다.

요세푸스와 그 친구가 앉아있던 위치는 어디였을까? 이 글을 읽고 문제를 해결해보자.

2. 요세푸스 문제(Josephus problem)와 요세푸스 순열(Josephus permutation)

이 글에서 요세푸스 문제(Josephus problem)는 다음과 같은 문제를 의미한다.

두 양의 정수 n과 k가 주어진다.
0부터 n - 1까지의 양의 정수를 시계방향으로 차례대로 원형으로 배치하고 0부터 시작해 시계방향으로 k-1개의 수를 건너뛰고 k번째 수를 제거하는 것을 하나의 정수가 남을 때까지 반복할 때, 마지막으로 남은 정수는 무엇일까?

정수의 index가 1이 아닌 0부터 시작함에 유의하자. 1이 아닌 0부터 시작하는 것으로 문제를 정의한 이유는 풀이를 더욱 간결하게 서술하기 위해서이다.

유래의 상황은 n = 41이고 k = 3인 요세푸스 문제의 상황과 매우 유사하다는 점을 관찰할 수 있다. (유래에서는 총 두 명이 살아남는다는 점이 다르다.)

또한, 위의 과정(단, 여기에서는 모든 정수가 제거될 때까지 반복한다)에서 제거되는 정수들을 차례로 나열해 얻는 순열을 요세푸스 순열(Josephus permutation)이라 한다.

다음 문단부터는 요세푸스 순열을 구하는 알고리즘과 요세푸스 문제를 해결하는 알고리즘에 대해 알아보자.

3. 요세푸스 순열을 구하는 알고리즘

3.1. O(nk) 해법

가장 단순한 풀이 중 하나로 큐(queue) 자료구조를 이용해 요세푸스 문제의 시행을 직접 시뮬레이션하는 풀이가 존재한다. 구체적으로, 다음과 같이 문제를 해결할 수 있다.

(1) 1부터 n까지의 양의 정수가 차례대로 들어있는 큐를 준비한다.

(2) 큐의 앞에 있는 원소 x를 빼고, 다시 x를 큐에 넣는 것을 k-1번 반복한다.

(3) 큐의 앞에 있는 원소 x를 뺀다. 이 x가 다음으로 제거되는 수이다.

(4) 큐에 원소가 남아있다면 2로 돌아간다.

큐의 앞에 있는 원소를 빼고 넣는(O(1)) 작업을 k번 반복해 다음 수를 얻는 것을 n번 시행해 문제를 해결하므로 이 해법의 시간복잡도는 O(nk)이다.

3.2. O(nlgn) 해법

위 방법보다 조금 더 빠른 풀이로 세그먼트트리를 이용한 방법이 있다.

구체적으로, 구간합을 다루는 세그먼트트리를 이용해 남아있는 수중 다음 k번째 수가 무엇인지를 세그먼트트리 위에서의 이진탐색으로 찾아내고 해당 수를 0으로 업데이트하는 것을 반복해 문제를 해결할 수 있다. 각 작업의 시간복잡도는 O(lgn)이므로 전체 시간복잡도는 O(nlgn)이 된다.

4. 요세푸스 문제를 해결하는 알고리즘

두 양의 정수 n과 k에 대하여 J(n, k)를 n과 k에 대한 요세푸스 문제의 해답으로 정의하자.

4.1. 요세푸스 순열을 구해 해결하는 방법

위의 3문단에서 구한 요세푸스 순열의 마지막 수는 요세푸스 문제의 해답과 같다. 따라서 3문단에서 소개한 방법들을 이용해 요세푸스 문제를 O(nk)또는 O(nlgn)에 해결할 수 있다.

4.2. O(n) 해법

두 양의 정수 n과 k에 대하여 J(n, k)에 대해 다음과 같은 점화관계가 성립함을 관찰할 수 있다.

J(n, k) = (J(n-1, k) + k) % n

이와 같은 점화관계를 이용해 요세푸스 문제를 O(n)에 해결할 수 있다.

4.3. O(klgn) 해법

k가 n에 비해 크기가 많이 작은 경우 O(n)보다 더욱 빠르게 작동하는 풀이 또한 존재한다. 이 방법은 위의 점화관계를 차례대로 한 단계씩 계산하는 대신 한 바퀴 단위로 계산하는 것으로 효율의 상승을 꾀한다.

구체적으로, 두 양의 정수 n과 k에 대하여 n을 k로 나눈 몫을 p라 정의하자. 이 때, 다음과 같은 점화관계가 성립함을 관찰할 수 있다.

J(n, k) = (J(n-p, k) + pk) % n

단, p = 0인 경우 위의 식은 더 이상 사용할 수 없으므로 4.2의 식을 이용해 마저 계산을 이어나가자.

아래는 위 점화식을 이용해 요세푸스 문제를 해결할 때의 시간복잡도를 계산하는 과정이다:

두 양의 정수 n과 k에 대하여, 위와 같은 단계를 x회 거친 뒤 남는 정수의 개수는 대략 n*(1 - 1/k)^x로 계산해낼 수 있다. 남는 정수의 개수가 하나가 될 때까지 이를 반복한다고 이상적으로 생각하면 대략적으로 n*(1 - 1/k)^x = 1와 같은 관계식을 얻을 수 있고, 이 식으로부터 x = - lgn / lg(1 - 1/k)를 얻어낼 수 있다. 따라서 이 과정의 시간복잡도는 O(x) = O(klgn)과 같다는 것을 알 수 있다. p = 0 이후의 계산 횟수는 O(k)이므로 이 값은 시간복잡도에 영향을 주지 않음을 확인하자.

4.4. k=2인 경우(O(1) 해법)

유래의 상황과 같이 k=2인 경우에는 더욱 빠른 풀이가 존재한다. 바로 공식을 이용하는 것이다.

구체적으로, k=2인 경우 다음과 같은 공식으로 답을 구할 수 있다:

n = 2^m+l, l<2^m을 만족하는 음이 아닌 정수 m과 l에 대하여, J(n, 2) = 2*l + 1이다.

증명은 귀납법을 이용하여 간단히 할 수 있다.

위 공식을 활용하면 n의 이진표기에서 최상위 비트(msb;most-significant bit) 1을 지우고 최하위 비트(lsb;least-significant bit) 1을 하나 추가하는 것으로 문제를 해결할 수 있다는 것을 알 수 있다.

5. 연습문제 추천

이제 개념 연습문제를 풀면서 요세푸스 문제와 그 풀이를 더 깊이 이해하고 PS/CP 연습문제를 풀면서 코드로 직접 구현해보자. ★이 붙은 문제는 꼭 풀어보고 넘어가자.

5.1. 개념 연습문제

★(1) 1부터 41까지의 양의 정수를 시계방향으로 차례대로 원형으로 배치하고 1부터 시작해 시계방향으로 두 개의 수를 건너뛰고 세번째 수를 제거하는 것을 두 개의 정수가 남을 때까지 반복할 때, 마지막으로 남은 정수 두 개는 무엇일까?

(2) 세 양의 정수 n, m과 k가 주어질 때, 다음과 같은 문제의 해답을 J'(n,m,k)라 하자. (단, m<n)

0부터 n - 1까지의 양의 정수를 시계방향으로 차례대로 원형으로 배치하고 0부터 시작해 시계방향으로 k-1개의 수를 건너뛰고 k번째 수를 제거하는 것을 m개의 정수가 남을 때까지 반복할 때, 남겨진 정수들의 집합을 구하시오.

J'(n,m,k)의 값을 O(nm)에 찾아내는 알고리즘을 설계해보자.

(3) 임의의 짝수 2n에 대하여 1부터 2n까지의 양의 정수를 시계방향으로 차례대로 원형으로 배치하고 1부터 시작해 시계방향으로 k - 1개의 수를 건너 뛰고 k번째 수를 제거하는 것을 n개의 정수가 남을 때까지 반복하자. 이 때, (a) n+1 이상 2n 이하의 정수들만 남게 하는 k가 존재할까? 또한 (b) 1 이상 n 이하의 정수들만 남게 하는 k가 존재할까? 이유와 함께 설명해보자.

5.2. PS/CP 연습문제(BOJ)

★11866번 문제: 요세푸스 문제 0

★1158번 문제: 요세푸스 문제

★1168번 문제: 요세푸스 문제 2

★11025번 문제: 요세푸스 문제 3

★1179번 문제: 마지막 요세푸스 문제

20301번 문제: 반전 요세푸스

6602번 문제: Eeny Meeny Moo

7580번 문제: Team Selection

6. 인용

365일 수학 - 요세푸스 문제

cp-algorithms.com - Josephus Problem

위키백과 - Josephus Problem

네 자리 정수(leading zero 포함) K에 다음과 같은 연산을 반복하면 어떻게 될까?

1. K의 각 자리로 이루어진 가장 큰 수 K1과 가장 작은 수 K2를 구한다.
2. K1과 K2의 차를 구해 새로운 K로 한다.

위 연산에 대해 단순히 추측해보면, K는 (비둘기집의 정리에 의해) 일정 주기로 같은 순서를 반복하게 될 것이라고 기대할 수 있다.

하지만 네 자리 정수에 한정하면 더욱 강력한 특징이 있다. 바로, K의 모든 자릿수가 동일(1111 등)하지 않다면 K는 7번 이하의 연산을 적용하면 항상 6174가 된다는 것이다.

위의 연산은 Kaprekar's routine이라고 불리는 연산이다. 그리고 (모든 자릿수가 동일하지 않은) 각 자리 수에 대하여 Kaprekar's routine을 반복 적용했을 때 최종적으로 나올 수 있는 수를 Kaprekar's constant라 한다. 이와 같은 이름은 이러한 개념을 탐구한 인도의 수학자 D. R. Kaprekar의 이름에서 따왔다.

세 자리 수에도 마찬가지로 네자리 수의 6174와 같은 수가 존재한다. 바로 495이다. 임의의 (모든 자릿수가 동일하지 않은) 세 자리수로 시작해 Kaprekar's routine을 반복 적용하면 그 세자리수는 6번 이하의 연산을 적용하면 항상 495가 된다.

Kaprekar's constant는 모든 자릿수에 대해 항상 존재할까? 아쉽지만 그렇지는 않다. 예를 들어, 다섯자리 수의 경우 Kaprekar's routine을 적용하다보면 각 수는 (53955와 59994를 반복하는 사이클), (61974, 82962, 75933, 63954를 반복하는 사이클), (62964, 71973, 83952, 74943을 반복하는 사이클)의 세 가지 사이클중 하나로 수렴하게 된다.

Kaprekar's routine은 세 자리 수와 네 자리 수를 한 가지 수로 수렴시키는 재미있는 특징이 있고 그 과정이 단순해 코딩 입문자들에게 구현 예제로 추천할만한 주제 중 하나이다. 관심이 있다면 아래의 문제를 해결해보자.

https://www.acmicpc.net/problem/9047 

위 문제의 풀이는 다음 글에 적어두었으니 관심이 있다면 읽어보자.

이 글은 다음 글을 참조하여 작성하였다. 더 많은 정보를 알고싶다면 다음 글을 읽어보자:

https://en.wikipedia.org/wiki/Kaprekar%27s_routine 

이 글은 Floyd-Warshall(플로이드-워셜; 플로이드-와샬) 알고리즘이 무엇인지, 그리고 Floyd-Warshall 알고리즘의 원리를 PS/CP에서 어떤 식으로 응용하는지에 대한 내용을 대략적으로 정리해둔 글이다.

1. Multiple-source multiple-destination shortest path problem

먼저 Floyd-Warshall 알고리즘을 살펴보기 전에 이 알고리즘을 적용할 문제가 무엇인지부터 살펴보자.

N개의 노드(V개의 버텍스)가 존재하고 에지에 거리 가중치가 존재하는 (방향)그래프 G를 생각해보자. 이 그래프 위의 한 점에서 모든 G 위의 각 노드까지의 거리를 구하는 문제를 single-source multiple-destination shortest path problem이라고 부른다. 이 문제의 해법으로는 거리 가중치가 음이 아닌 경우 O(ElgV)에 동작하는 Dijkstra(데이크스트라; 다익스트라) 알고리즘이, 거리 가중치가 음수일 수 있는 경우 O(VE)에 동작하는 Bellman-Ford 알고리즘이 잘 알려져있다.

한편 G 위의 모든 가능한 두 노드 사이의 최단 거리를 구하는 문제도 생각해볼 수 있는데, 이와 같은 문제를 multiple-source multiple-destination shortest path problem이라고 부른다. 이 문제는 각 노드별로 거리 가중치의 음수 존재 여부에 따라 Dijkstra 알고리즘 또는 Bellman-Ford 알고리즘을 한번씩 이용해 해결할 수도 있지만, 이보다 시간복잡도가 낮은 알고리즘이 존재한다. 바로 Floyd-Warshall 알고리즘이다.

Floyd-Warshall 알고리즘은 multiple-source multiple-destination shortest path problem의 해를 O(N^3)에 구하는 알고리즘이다. Floyd-Warshall 알고리즘은 거리 가중치가 음이 아닌, 굉장히 sparse한(에지의 밀도가 낮은) 그래프에서는 위의 V번 Dijkstra 알고리즘을 이용하는 O(VElgV) 해법보다 비효율적일 수 있으나, 에지가 많아질수록(V^2개에 가까워질수록) 좋은 효율을 보여준다. 또한 거리 가중치가 음수일 수 있다면 O(V^2E)에 작동하는, Bellman-Ford를 반복하는 해법보다 Floyd-Warshall이 더 빠르게 작동한다는 것을 알 수 있다.

이제 Floyd-Warshall 알고리즘을 알아보자.

2. Floyd-Warshall 알고리즘

Floyd-Warshall 알고리즘은 각 두 노드 사이를 잇는 최단경로를 DP를 이용하여 계산해나간다.

편의상 G의 모든 노드에 index를 1부터 N까지 하나씩 붙이자. 또한 G에는 음의 cycle이 없다고 가정하고 알고리즘을 설명할 것이다. 음의 cycle이 있는 경우는 아래의 연습문제에서 스스로 생각해보자.

집합 S(i,j,k)를 "중간에 경유하는(i와 j를 제외한) 모든 노드의 index가 k 이하인 경로"들의 집합이라 정의하자. 그리고 함수 dp(i,j,k)를 S에 속한 경로의 길이의 최솟값으로 정의하자. 다르게 쓰면 dp(i,j,k)는 노드 i에서 출발하여 1 이상 k 이하의 번호만을 가진 노드만을 거쳐 노드 j로 이동하는 최단경로의 길이를 의미한다. 단, S(i,j,k)가 공집합이라면 dp(i,j,k)는 무한대(INF)로 정의하자.

dp(i,j,0)은 그래프 G의 노드 i에서 노드 j를 직접 잇는 에지의 길이(의 최솟값)을 의미한다는 점을 확인하자. (존재하지 않는다면 그 값은 무한대일 것이다.) 또한 dp(i,j,N)은 G 위에서의 i에서 j까지의 최단거리를 의미함을 확인하자.

S(i,j,k)에 속하는 모든 경로는 (1)k를 포함하지 않는 경로와 (2)k를 포함하는 경로의 두 종류로 나눌 수 있다. 따라서, dp(i,j,k)는 (1)번 종류의 경로의 길이의 최솟값과 (2)번 종류의 경로의 길이의 최솟값, 두 값 중 작은 값임을 알 수 있다.

(1)번 종류 경로들은 k를 포함하지 않으므로, 중간 경유 노드로 k-1 이하의 index를 가지는 노드들만을 이용한다. 따라서 (1)번 종류 경로의 길이의 최솟값은 dp(i,j,k-1)과 같다.

(2)번 종류 경로들은 i에서 k까지의 부분경로와 k에서 j까지의 부분경로로 나눠 생각할 수 있다. 물론 각 부분경로들 또한 모든 중간 경유 노드의 index가 k 이하가 된다. 여기서 k는 각 부분경로의 끝점이 되었으므로, 각 부분경로들의 모든 중간 경유 노드의 index는 k-1 이하이다.

한편 (2)번 종류 경로들의 길이는 두 부분경로의 길이의 합으로 구할 수 있다. 이 값의 최솟값은 두 부분경로의 길이의 최솟값을 각각 구해 합하는 것으로 구할 수 있다. 따라서 (2)번 종류 경로의 길이의 최솟값은 dp(i,k,k-1) + dp(k,j,k-1)과 같다.

두 종류의 경로의 길이를 종합하면, dp(i,j,k)는 min(dp(i,j,k-1), dp(i,k,k-1) + dp(k,j,k-1))와 같다는 것을 알 수 있다.

이제, 위의 점화식을 이용하여 모든 i와 j에 대해 dp(i,j,N)을 계산하면 모든 노드의 쌍에 대한 최단거리를 구할 수 있다. 메모이제이션(memoization)을 이용하면 모든 가능한 3-tuple (i,j,k)에 대하여 dp(i,j,k)를 각각 한 번씩만 계산하게 되므로 시간복잡도는 O(N^3)이 된다.

3. Floyd-Warshall 알고리즘의 구현

Floyd-Warshall 알고리즘의 개념은 위와 같지만 노드 i에서 j까지의 최단거리를 실제로 함숫값을 재귀적으로 구하는 구현(top-down DP)보다 더욱 간단한 구현 방법이 존재한다. 바로 반복문을 이용한 bottom-up DP이다. 그 방법은 다음과 같다.

2차원 배열 dist[N+1][N+1]을 준비하자. 이 배열의 dist[i][j]의 값이 dp(i,j,k)들로 채워져 있을 때, dist[i][j]의 값들을 dp(i,j,k+1)로 바꾸는 것이 가능하다면 dp[i][j]의 값이 dp(i,j,0)들로 채워져있는 배열을 dp(i,j,N)들로 채워져있는 배열로 바꾸는 것 또한 가능해진다.

dp(i,j,k+1) = min(dp(i,j,k), dp(i,k+1,k) + dp(k+1,j,k)) 관계식을 이용하면 (새로운 dist[i][j]) = min(dist[i][j], dist[i][k+1] + dist[k+1][j])와 같이 표현할 수 있다는 것을 알 수 있다. 이 때, dist[i][k+1] 또는 dist[k+1][j]들은 이 과정에서 값이 변하지 않고, 그 외 dist[i][j]들은 새로운 dist[i][j]의 값을 구할 때에만 값을 참조한다는 점을 관찰하자.

위의 관찰을 이용하면, dp(i,j,k)의 값들로 채워져있는 2차원 배열의 각 성분 dist[i][j]들을 각각 순서에 상관없이 min(dist[i][j], dist[i][k+1] + dist[k+1][j])로 다시 계산하면 dp(i,j,k+1)의 값들로 채워져있는 2차원 배열을 얻게 된다는 것을 알 수 있다.

따라서, 단순하게 3중 반복문을 이용해 Floyd-Warshall 알고리즘을 구현할 수 있다. 아래는 이해를 돕기 위한 예시 C++ 소스코드이다. 직접 돌려보고 위의 내용을 한번씩 다시 확인해보자.

// NODE: 전체 노드 개수 + 1 (1-based index)
#define NODE 5
#define INF 0x3f3f3f3f
#include <iostream>
using namespace std;

// 초기 dist[i][j]: 노드 i에서 j로 바로 이어지는 에지의 길이(의 최솟값), 그러한 에지가 없다면 INF
int dist[NODE][NODE] = {
	{0, 0, 0, 0, 0},
	{0, 0, 4, 3, INF},
	{0, INF, 0, 1, INF},
	{0, INF, INF, 0, 2},
	{0, -1, 7, INF, 0 }
};

void floyd_warshall() {
	for (int k = 1; k < NODE; k++) {
		cout << "---\n";
		cout << "k: " << k << '\n';
		for (int r = 1; r < NODE; r++) {
			for (int c = 1; c < NODE; c++) {
				dist[r][c] = min(dist[r][c], dist[r][k] + dist[k][c]);
				if (dist[r][c] == INF) cout << 'X' << ' ';
				else cout << dist[r][c] << ' ';
			}
			cout << '\n';
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cout << "k: 0\n";
	for (int r = 1; r < NODE; r++) {
		for (int c = 1; c < NODE; c++) {
			if (dist[r][c] == INF) cout << 'X' << ' ';
			else cout << dist[r][c] << ' ';
		}
		cout << '\n';
	}

	floyd_warshall();

	cout << "---\n";
	cout << "X: i에서 j로 가는 경로가 없음";
}

4. 연습문제 추천

이제 개념 연습문제를 풀면서 Floyd-Warshall 알고리즘을 더 깊이 이해하고 PS/CP 연습문제를 풀면서 다양한 상황에서 Floyd-Warshall 알고리즘 또는 그 원리를 적용하는 연습을 해보자. ★이 붙은 문제는 꼭 풀어보고 넘어가자.

4.1. 개념 연습문제

★(1) 음의 가중치를 갖는 간선이 있는 방향그래프가 음의 사이클을 가지는 경우, 몇몇 노드 사이의 최단거리가 음의 무한대가 될 수도 있다. Floyd-Warshall 알고리즘으로 음의 무한대의 거리까지 처리하는 방법을 생각해보자. (negative cycle detection)

★(2) Floyd-Warshall 알고리즘의 과정을 변형해 각 두 노드 i와 j가 주어졌을 때 i와 j 사이의 최단거리 뿐만이 아닌 경유하는 경로를 그대로 출력하는 방법을 생각해보자. (경로 역추적)

(3) 노드가 N개이고 에지에 가중치가 있는 방향그래프에서 만약 노드 i에서 노드 j로 가는 경로가 존재한다면 그 중 "경유한 에지의 가중치들 중 가장 큰 값"의 최솟값을, 없다면 없다는 정보를 모든 노드쌍에 대하여 구하는 효율적인 방법을 생각해보자. (all-pairs minimax path problem)

4.2. PS/CP 연습문제(BOJ)

기본문제

11404번 문제: 플로이드 (풀이) ★

23258번 문제: 밤편지 (풀이) ★

1507번 문제: 궁금한 민호 (풀이)

1719번 문제: 택배 (풀이) ★

11403번 문제: 경로 찾기 (풀이)

응용문제

2458번 문제: 키 순서 (풀이)

6135번 문제: Cow Hurdles (풀이)

13141번 문제: Ignition (풀이)

24617번 문제: Redistributing Gifts (풀이)

1746번 문제: 단체 릴레이 (풀이)

0. 필요한 배경지식

 - 가장 긴 단조증가하는 부분수열

 - 비둘기집의 원리(pigeonhole principle)

1. 서론

가장 긴 단조증가하는 부분수열(LIS)를 찾는 문제는 이산수학에서 유명한 문제로, 길이 N인 수열의 LIS의 길이를 구하는 문제나 그런 길이의 단조증가 부분수열을 직접 찾는 문제는 모두 O(NlogN)에 해결할 수 있다.

심지어는 길이가 N인 수열의 서로 다른 LIS가 몇 개 존재하는지 찾는 문제 또한 O(NlogN)에 해결할 수 있다.

LIS를 구하다보면 LIS가 전체 수열의 길이에 비해 특히 짧은 경우들을 자주 만날 수 있다.

이런 경우를 만나면 LIS와 반대방향인, 가장 긴 단조감소하는 부분수열(이후 LDS라 칭한다)의 길이가 길어지는 것이 자주 눈에 띄지 않는가?

Erdős–Szekeres Theorem은 이러한 관점에서 바라볼 때, 주어진 모든 원소가 서로 다른(distinct) 수열이 주어졌을 때 LIS의 길이와 LDS의 길이 사이의 상관관계를 보여주는 정리이다.

2. 정리 소개

Erdős–Szekeres theorem는 다음과 같이 서술할 수 있다.

두 수 r과 s에 대하여, 모든 원소가 서로 다른(distinct) 길이가 rs + 1인 수열은

길이 r + 1인 LIS를 포함하거나 길이 s + 1인 LDS를 포함한다.

rs + 1보다 더 긴 길이의 수열은 길이가 rs + 1인 부분수열을 포함하므로 위의 성질을 만족한다.

증명을 하기 전에, 길이가 (r - 1)(s - 1)인 수열중에서 길이가 r + 1인 단조증가 부분수열과 길이가 s + 1인 단조감소 부분수열이 둘 다 존재하지 않는 예시를 직접 찾아보자. 아래 접은 글로 그러한 수열의 예시를 적어두었다.

3. 증명

이 글에서는 Seidenberg의 증명을 소개한다.

길이가 rs + 1이고 모든 원소가 서로 다른 임의의 수열 a_i를 생각하자.

또한, m_i를 a_i서부터 시작되는 부분수열의 LIS의 길이, n_i를 a_i서부터 시작되는 부분수열의 LDS의 길이로 정의하자.

임의의 i < j에 대하여, 다음이 성립한다는 것을 쉽게 관찰할 수 있다.

 - a_i < a_j 이면 m_i > m_j 이다.

 - 반대로 a_i > a_j 이면 n_i > n_j 이다.

따라서, 각 i에 순서쌍 (m_i, n_i)를 대응시키면, 수열 a_i는 길이가 rs + 1이므로 서로 다른 rs + 1개의 순서쌍 (m_i, n_i)를 얻을 수 있다.

만약 a_i의 LIS의 길이가 r이고 LDS의 길이가 s이면, 만들 수 있는 서로 다른 순서쌍 (m_i, n_i)의 개수는 많아야 rs개이다.

따라서, 수열의 항이 rs개보다 많으므로, 비둘기집의 원리에 의해 이는 모순임을 알 수 있다.

따라서, LIS의 길이가 r보다 크거나, LDS의 길이가 s보다 클 수밖에 없음을 알 수 있다.

이것으로 Erdős–Szekeres Theorem이 증명되었다.

4. 응용

Erdős–Szekeres Theorem을 기하학적으로 생각해보자.

위 증명에서의 수열의 각 항 a_i를 2차원 좌표평면 위의 점 (i, a_i)에 대응시켜 생각을 해보면, Erdős–Szekeres theorem은 좌표평면 위의, 같은 x좌표 또는 y좌표를 가지지 않는 rs + 1개의 점에서 기울기가 연속적으로 양수인 r + 1개의 점 또는 기울기가 연속적으로 음수인 s + 1개의 점을 항상 찾을 수 있다는 것을 말해준다.

5. 여담

글쓴이는 다음 문제를 풀고 관련된 내용을 찾아보다가 위의 내용을 정리하게 되었다.

관심이 있다면 다음 문제를 풀어보자.

www.acmicpc.net/problem/1201

6. 참고한 내용

위키백과 Erdős–Szekeres Theorem: en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem

Seidenberg, A. (1959), "A simple proof of a theorem of Erdős and Szekeres"