문제 원본 : https://gall.dcinside.com/board/view/?id=mathematics&no=333993&page=1


이런 문제 푸는거 ㄹㅇ 개오랜만이라, 반가운 마음에 한번 풀어봄. 출전은 2017 IMO #5라고 하니까 참고.

기존 문제는 축구 선수들의 키를 가지고 서술이 돼있는데, 그 키를 1번째부터 N(N+1)번째까지 정렬할 수 있으므로, 편의상 문제 표기를 아래와 같이 동치변형함.






정수 N>=2에 대해, 1부터 N(N+1)까지의 자연수가 칠판에 일렬로 적혀 있다. 이 수들이 어떤 순서로 적혀 있든, 언제나 이 중 N(N-1)개의 수들을 지워, 남은 2N개의 자연수가 아래 N개의 조건을 만족하게 할 수 있음을 보여라.


<조건>

남겨진 2N개의 자연수들 중,

(1) 가장 큰 두 수가 인접해 있고,

(2) 3번째 및 4번째로 큰 두 수가 인접해 있고,

...

(k) (2k-1)번째 및 2k번째로 큰 두 수가 인접해 있고,

...

(N) 가장 작은 두 수가 인접해 있다.






pf)

위 조건대로 2N개의 숫자만 남겨주는 recursive process의 존재를 수학적 귀납법의 힘을 빌려 밝히겠음. 여기서는 위 문제의 충분조건으로, N(N+1)까지의 자연수를 S_1 = {1 ~ (N+1)}, S_2 = {(N+1)+1 ~ 2(N+1)}, S_3 = {2(N+1)+1 ~ 3(N+1)}, ... , S_N = {(N-1)(N+1)+1 ~ N(N+1)}의 N개 집합으로 분할했을 때 위 조건을 만족하도록 각 집합에서 2개씩만 남기는 게 가능함을 보일 거다. 이때 가장 큰 수 2개는 S_N, 3번째 및 4번째로 큰 두 수는 S_(N-1), ..., 가장 작은 두 수는 S_1에 들어있는 방식일 테니, 같은 분할집합에 든 정수끼리 인접한 상태로 남겨지게 되겠지.




1. P(2)의 증명

즉 1~6의 정수들을 칠판에 적어, 2개를 지우고 남은 4개의 수를 봤을 때, 큰 놈들끼리 붙어 있고, 작은 놈들끼리 붙어 있도록 하는 게 되냐는 문제임.

이를 보이기 위해, 원소 6개짜리 배열을 끝에서부터 3개씩 끊어, 2개의 그룹으로 나누려고 함. 예컨대 [3,5,1,6,2,4]의 순서로 적혀 있다면, 이렇게 나누자는 거다.


3, 5, 1, | 6, 2, 4


1~6의 수 중 가장 작은 3개, 즉 1부터 3까지를 보자. 위처럼 수를 2개의 그룹으로 나누면, 비둘기집의 원리에 의해 {1,2,3}의 원소 중 적어도 2개를 가지고 있는 그룹이 반드시 나옴(이 그룹을 G_1이라 하자). 예컨대 위 예시에서는 왼쪽 그룹이 1과 3을 가지고 있지.

한편, 그 그룹의 반대쪽 그룹에는 {1,2,3}의 원소가 많아야 하나 있을 테니 그 여집합인 {4,5,6}의 원소는 적어도 2개 존재하겠지(이 그룹을 G_2라 하자). 위 예시는 오른쪽 그룹이 6과 4를 가지고 있음.

그럼 G_1에 든 {1,2,3}의 원소 뭐든 2개를 남기고, G_2에 든 {4,5,6}의 원소 뭐든 2개를 남긴 상태로 나머지는 다 지우면 해결. 위 예시 같은 경우는 5 지우고, 2 지워서 [3,1|6,4] 남기면 OK.




2. P(N-1) => P(N)의 증명

(내가 한 서술이 좀 복잡한데, 이해가 안 되면 2' 항목을 따로 달아서 예시를 설명해놨으니 읽고 오자)

증명 초두에 언급한 대로, 1부터 N(N+1)까지의 자연수를 아래의 N개 집합으로 분할하자.


S_1 = {1, 2, ..., N+1}

S_2 = {N+2, N+3, ..., 2(N+1)}

S_3 = {2N+3, 2N+4, ..., 3(N+1)}

...

S_k = {(k-1)N+k, (k-1)N+k+1, ..., k(N+1)}

...

S_N = {(N-1)(N+1)+1, N^2+1, ..., N(N+1)}


이때 각 집합은 N+1개 원소들을 가지고, 칠판에는 위 S_1~S_N의 모든 원소들이 좌우 일렬로 나열되어 적혀 있는 상태임. 그 개수는 앞서 말했듯 N(N+1)개.

이제 이 배열의 가장 왼쪽에 있는 수부터 차례로 위 집합 중 몇 번째 것인지 그 index값을 그 수 바로 아래에다 적어가는데, 기존에 나온 index 값 중 하나가 처음으로 다시 적히는 순간까지만 이걸 계속할거야. 예를 들면 N=3일 때,


11, 2, 6, 9, 4, 8, 12, 1, 5, 10, 3, 7


의 순서대로 1부터 12까지의 수들이 적혀 있을 때, 위처럼 자연수를 분할하면


S_1 = {1,2,3,4},

S_2 = {5,6,7,8},

S_3 = {9,10,11,12}


일 테니, 맨 왼쪽의 11부터 시작해 차례로 위의 몇 번째 집합 소속인지를 적는 거임. 11은 3번째, 2는 1번째, 6은 2번째니까, 각각의 아래에


11, 2, 6, ..., 10, 3, 7

3, 1, 2, ...


처럼 새로운 수열을 하나 더 적는 거지. 그런데 바로 다음 수인 9가 3번째 집합 소속인데, 앞서 3번째 집합 소속인 수가 이미 하나 나왔으니까(11) 9를 본 시점에서 마지막으로 index를 적고 마치자는 거임. 즉


11, 2, 6, 9, 4, ..., 10, 3, 7

3, 1, 2, 3


까지 적히겠네.


이렇게 index number를 적는 행위는, 역시 비둘기집의 원리에 의해, 많아야 N+1번 가면 종료됨. 왜냐하면 전체 분할된 집합 수가 N개인데 N+1번째 수까지 이걸 계속한다 생각하면 한 집합당 많아야 하나씩밖에 적혀 있지 않았다 생각하면 개수가 맞지 않으니 모순일 테고, 즉 당연히 1부터 N까지의 index number 중 적어도 하나는 2번 적힌 상태일 테니까.


어쨌거나 이 방법대로 index number sequence를 적었을 때, 이렇게 적혔다고 하자.


???, ???, ???, ???, ???, ... , !!!, ... , ???, @@@, ###, ..., ..., ..., ###

  |     |     |      |     |            |           |     |

i_1, i_2, i_3, i_4, i_5, ... , i_m, ... , i_n, i_m (종료)


물론 이때 1 <= m <= n <= N && 1 <= i_l <= N for each i_l's. 즉 위 과정에서 적히는 indices를 차례로 i_1, ... , i_n이라 하고, 그 중 한 번 더 적히는 유일한 index number를 i_m이라 한 거임. 이후 논의의 편의를 위해, 모든 index number를 모아놓은 집합을 I = {1, 2, ... , N}이라고 하고, 위 과정에서 칠판에 적힌 indices의 집합을 J = {i_1, i_2, ..., i_n}이라고 하자.


이제 i_m이 아래에 적힌 두 수(즉 !!!와 @@@)는 남기고, 나머지 i_1, ..., i_(m-1), i_(m+1), ..., i_n이 아래에 적힌 수들(즉 ???들)은 모조리 지울 거임. 추가로 아래 과정을 따라서, 이 뒤로 나오는 수들 중 몇 개를 더 지우자.

(i) 먼저 두 번째 i_m이 적힌 수 뒤로 나오는 모든 S_(i_m)의 원소들 N-1개를 지워버릴 거임. 그리고,

(ii) I-J의 모든 원소 i에 대해, S_i의 원소는 모조리 @@@ 뒤에 등장하겠지. 이 S_i들에서 원소를 아무거나 하나씩만 골라서 지워버리자. S_i 안에서 가장 작은 수만 찾아 지우거나, 가장 큰 수만 찾아 지우거나, 아니면 위 sequence에서 제일 먼저 나오는 원소를 지우거나... 진짜 뭐든 하나씩만 찾아서 지우면 됨. 각 S_i 안에서의 지워지는 수들의 유일성이 보장되는 선에서 맘대로 ㄱㄱ.


이렇게 해서 수들을 일부 지우고 남은 칠판 상태는 이런 모양임.


!!!, @@@, ###, ..., ..., ..., ### (이 ###들 중 위 (ii)의 각 S_i에 든 원소 하나씩만 골라 지워진 상태)

i_m, i_m


이렇게 하면, I-{i_m}의 모든 원소 j에 대해, 처음 상태에서 S_j의 원소들 중 정확히 하나씩만 골라 지워진 상태가 될 거임. 이때 맨 왼쪽에 남은 2개 수는 S_(i_m)의 원소일 테고, 나머지 수들은 (S_j들의 남은 원소 각 N개) * (가능한 j의 개수 N-1) = N(N-1)개만 남아 있음. 이제 우리가 하면 되는 건, 이 남은 길이 N(N-1)짜리 배열 [###, ..., ###]에서도 (N-1)(N-2)개 지우고 2(N-1)개 수만 남겨서 문제의 조건과 증명 초두에 내가 말한 조건이 만족되도록 하는 거임. 이미 S_(i_m)에 든 원소들은 모조리 지워진 상태니 !!!과 @@@ 사이의 수는 더는 등장하지 않을 테고, 남겨진 S_j의 수들 중에서 2개씩만 남겨서 문제 조건을 만족하도록 하면 곧 [###, ..., ###] 부분에는 S_1, S_2, ..., S_(i_m-1), S_(i_m+1), ..., S_N의 수들 중 2개씩만 서로 이웃하도록 남겨진 상태일 테니 문제의 조건 및 내가 걸어둔 더 강한 조건까지 만족.


이를 명확하게 보이기 위해서, [###, ..., ###]의 수들을 모은 집합에서 {1,...,(N-1)N}으로 가는 전단사 증가함수 f를 정의할 거야. 즉 f 혹은 그 역함수를 적용해도 일반적인 자연수의 순서가 보존되도록 정의하는 거임. 원소의 개수가 같으니 그러한 전단사 증가함수 f는 당연히 존재하고, 그러면 아래가 성립하겠지.


f(S_1 - {방금 지워진 수들}) = S'_1 = {1, 2, ..., N}

f(S_2 - {방금 지워진 수들}) = S'_2 = {N+1, N+2, ..., 2N}

...

f(S_(i_m-1) - {방금 지워진 수들}) = S'_(i_m-1) = {(i_m-2)N+1, ..., (i_m-1)*N}

f(S_(i_m-1) - {방금 지워진 수들}) = S'_(i_m) = {(i_m-1)*N+1, ..., (i_m)*N}

...

f(S_N - {방금 지워진 수들}) = S'_(N-1) = {(N-2)N+1, ..., (N-1)N}


!!!, @@@를 제외하고 남겨진 배열 [###, ..., ###] 전체에 f를 적용하면, 크기 관계를 그대로 보존한 채 수들만 1, 2, ..., (N-1)N으로 바꿔 쓴 배열이 나옴. 귀납 가정 P(N-1)에 의해 이 길이 (N-1)N짜리 새로운 배열에서 (N-1)(N-2)개의 수들을 지워서 남은 2(N-1)개의 수들 중 S'_1의 원소 2개끼리, S'_2의 원소 2개끼리, ... , 그리고 S'_(N-1)의 원소 2개끼리가 이웃하도록 할 수 있음. 이렇게 해서 남겨진 수들에 다시 f의 역함수를 적용해서 S_1, S_2, ..., S_(i_m-1), S_(i_m+1), ..., S_N의 원소들로 바꿀 수 있음. 물론 이 과정에도 순서는 모조리 보존되며, 즉 이 과정이 끝나면 S_1, S_2, ..., S_(i_m-1), S_(i_m+1), ..., S_N의 각 원소가 2개씩 남아 서로 이웃한 상태로 남아있게 됨. 이미 S_(i_m)의 원소 2개는 처음의 [###, ..., ###]의 왼쪽에 남겨져 있었으니, 이상에서 P(N)을 보였음.




2'. N = 4일 때의 예시

갤럼들의 이해를 돕기 위해 예시를 하나 가져왔어. N = 4, 즉 초기 배열의 길이가 20인데, 좀 길어도 이게 이해하기 쉬울 거야.


3, 10, 15, 13, 4, 9, 18, 6, 11, 19, 5, 1, 14, 8, 12, 16, 2, 17, 7, 20


이때 1부터 20까지의 자연수들을 아래처럼 분류하자.

S_1 = {1,2,3,4,5}

S_2 = {6,7,8,9,10}

S_3 = {11,12,13,14,15}

S_4 = {16,17,18,19,20}


위에서 설명한 과정을 따라 이 배열 아래에다 index number를 적을 거임. 다만 중복된 숫자가 나오면 적은 직후 종료.


3, 15, 10, 13, 4, 9, 18, 6, 11, 19, 5, 1, 14, 8, 12, 16, 2, 17, 7, 20

1, 3, 2, 3 (3 중복되므로 종료)


그럼 15와 13을 남기고, 앞의 3과 10은 지우자. 그리고 나머지 배열 4, 9, ..., 20에서도 S_3에 든 수들은 모조리 지우자. 그러면


4, 9, 18, 6, 19, 5, 1, 8, 16, 2, 17, 7, 20


이 남음. 여기서 추가로 지워지지 않은 S_4의 원소를 아무거나 하나 잡아서 지우자. 왼쪽부터 search해서 제일 먼저 발견되는 수가 18이니 이걸 지우면


4, 9, 6, 19, 5, 1, 8, 16, 2, 17, 7, 20


이 남음. 여기서 남은 S_1, S_2, S_4의 원소를 모으면

{1,2,4,5}, {6,7,8,9}, {16,17,19,20}

이 되는데, 얘네들의 합집합에서 1부터 12까지의 자연수 집합으로 보내는 전단사 증가함수를 생각하자.


{1,2,4,5} ---> S'_1 = {1,2,3,4}

{6,7,8,9} ---> S'_2 = {5,6,7,8}

{16,17,19,20} ---> S'_3 = {9,10,11,12}


이걸 위 배열에다 씌우면 이렇게 됨.


3, 8, 5, 11, 4, 1, 7, 9, 2, 10, 6, 12


얘네들을 S'_1, S'_2, S'_3의 원소 2개씩만 서로 이웃하도록 남기고 나머지는 지우면 이렇게 됨. N = 3, N = 2의 과정을 재귀적으로 적용하면 되는데, 이건 님들이 알아서 해보셈.


8, 5, 4, 1, 10, 12


여기다 다시 f의 역함수를 씌우면 이렇게 됨.


9, 6, 5, 1, 17, 20


처음 배열의 맨 왼쪽에 남겨둔 15와 13까지 가져오면


15, 13, | 9, 6, | 5, 1, | 17, 20


이 남고, 이건 주어진 조건을 모두 만족함.




3. 종합

사실 더 적을 것도 없지만, 굳이 적자면 수학적 귀납법에 의해 주어진 문제의 충분조건이 증명되었고, 따라서 문제로 주어진 명제도 True.




역시 IMO라고 해야 할까, N-1=>N 증명 논증을 좀 치밀하게 짜야 했음. 대충 이리 끊고 저리 끊고 하면 되겠지 했는데 어림도 없더라.

물론 내가 맞다고 생각한 풀이고, 혹여 틀린 부분이나 더 간략화 가능한 부분이 있을 수 있으니 발견한다면 가차없이 피드백해주시길.