돌아온 수학특집 4편: 조합론의 난제들

안녕, 웃대인들. 돌아온 수학특집을 진행하는 언어장애지우야. 오늘은 조합론에서 풀리지 않은 가장 유명한 두 문제를 가져와봤어. 일단 그 전에 앞서 조합론이 어떤 분야인지 알아보는 게 중요하겠지?

개요: 조합론은 무엇인가?

조합론은 다음의 문제들에 대해서 다루는 수학의 한 분야야. 자연수 분할, 그래프이론, 디자인이론, 한정기하학, 일부의 암호학등 정말 다양한 분야들을 커버하고 있지. 하지만 조합론에서 묻는 "절대적 질문"들은 다음 세가지와 같아.

임의의 패턴을 가진 배열이 존재하는가?
존재한다면 얼마나 많이 존재하는가?
해당 패턴을 예측할 수 있는가?

약간 어렵다고? 그럼 가장 기본 조합론의 예제를 들어봐줄게.

[임의의 패턴을 가진 배열이 존재하는가?]

쉬운 듯 어려운 문제 하나!

어떤 남자가 있어, 이 남자는, 21일간 총 35개의 수학문제를 풀 거래. 단, 매일 최소한 한 문제 이상, 최대 세 문제 이하로 푼다고 하더라군. 그랬을 때, 어느 연속되는 날들간 정확히 6개의 문제를 푸는 날들이 있을까?


[문제따위, 포기하면 편해... 하지마]

생각보다 어렵지? 즉 여기서 임의의 패턴을 가진 배열이란, 6개의 문제를 푼 연속되는 날들이야. 그럼 이 문제를 어떻게 공략할까? 일일이 손으로 해봐? 그건 너무 "우아하지" 못하지? 다음과 같은 방법이 있어.

첫째날까지 푼 문제의 숫자를 a_（1）이라고 하자. 둘째날까지는 a_（2）, 그리고 21째날까지는 a_（21）이라고 잡는거야. 여기서 우리가 매일 최소한 한문제씩 풀어왔다고 하니까 n번째 날까지 푼 문제의 수와 n+1번째 날까지 푼 문제의 수는 달라야 돼. 정확히는 n+1번째 날가지 푼 문제의 수가 더 많아야겠지. 고로 a_（n） < a_（n+1）. 그럼 이걸 a_（1）에서 a_（21）까지 부등식으로 연결해보자. 다음과 같을거야.

A수열: a_（1） < a_（2） < …
이번엔 새로운 수열을 만들거야. a_（n）에 6을 더한 수열이지. 즉, a_（n）+6. 이걸 b_（n）이라고 부를거야.

B수열: b_（1） < b_（2） < … < b_（21）

잠깐, 근데 흥미로운 사실이 있어. a_（1）은 최소한 1 이상이고, a_（21）은 최대 35 이하야（문제는 총 35개 뿐이니까）. 같은 논리로 b（1）은 최소 7이상, b（21）은 41 이하야. 

자 그럼 a_（1）에서 b_（21）까지 모두 모아봐. A수열 21항, B수열 21항, 총 42개의 숫자가 있어. 하지만 그들 중 가장 작은 수인 a_（1）은 1, 가장 큰 수 b_（21）은 41이야. 

자, 42개의 항, 그리고 가능한 숫자는 41개. 무슨 뜻이냐면 42개의 항들 중 최소 어느 두 개의 항이 같은 값을 갖는다는 거야. 하지만 우리가 방금 전에 A수열에 있는 항들 중 같은 수는 없다고 했어. B수열에 있는 항들 역시 마찬가지야. 고로, A수열에 있는 어떤 항 a_（n）과 B수열에 있는 어떤 항 b_（m）이 같은 값이라는 의미겠지.

근데 b_（m） = a_（m） + 6이라고 했잖아.

a_（n） = b_（m） = a_（m） + 6

고로 a_（n） - a_（m） = 6

즉, m번째 날에서 n번째 날 까지 푼 수학 문제의 수는 정확히 6개. 이 n과 m이 몇이든 상관 없어. 최소한 이 n과 m이 무조건 존재한다는 것이 증명된 셈이니까,

이 남자가 정확히 6문제를 푸는 연속되는 날들의 배열은 존재한다!

어때? 짱이지?


[작성자를 측은하게 바라보는 개구리]

[패턴이 존재한다면 얼마나 많이 존재하는가?]

이번엔 새로운 예제! 어느 기다란 체스판이 있다고 가정해보자. 이 체스판은 특이하게도 총 n칸인데, 1 x n, 즉 가로 1칸, 세로 n칸이야. 이 체스판을 도미노와 모노미노（1칸짜리 도미노）로 채운다고 했을 때 총 몇가지 방법이 나올까?


[여러 모양의 모노미노（1칸）, 도미노（2칸）, 트로미노（3칸）, 테트로미노（4칸）. 여기서 우리가 필요한건, 모노미노와 도미노 뿐이다.]

일단 n을 칸 수라고 정의했으니 f（n）을 도미노와 모노미노로 채우는 방법의 수라고 정의해보자.
만약 n이 0이라면? 즉 0칸짜리 체스판을 채우는 방법은?

조합론에서는 이걸 1이라고 정의해. "아무것도 사용하지 않음"이 유일한 방법이라는 거야. （이거에 대해서는 따지지말자） 즉 f（0） = 1

그럼 n이 1, 즉 1칸짜리 체스판이라면?

그렇다면 우린 모노미노밖에 쓸 수 없겠지? 도미노는 2칸이니까 체스판을 넘어갈 거 아냐?
즉, n = 1일때도 방법의 수, f（1） = 1

n 이 2, 즉 2칸짜리 체스판이라면?

그렇다면 모노미노를 두개 사용하는 방법과 도미노를 한개 사용하는 방법으로 총 두가지 방법이 있어.
즉, n = 2일때는 f（2） = 2

이걸 일일이 다하냐고? 천만에 말씀. 이제부터 귀납법을 사용할거야.

n = 3이라고 가정해보자. 가로 1칸, 세로 3칸짜리 체스판.

첫번째 칸에 모노미노를 놓는다고 가정하면 남은칸은 몇개? 2개지. 2칸짜리 체스판을 도미노와 모노미노로 채우는 방법의 수는? 방금 전 구했잖아. f（2） = 2개!
첫번째 칸에 이번엔 도미노를 놓는다면? 남은 칸은 한개지! 1칸짜리 체스판을 도미노와 모노미노로 채우는 방법의 수는? f（1） = 1
고로 f（3） = f（2） + f（1）이 돼.

그리고 귀납법을 사용하면 f（n） = f（n-1） + f（n-2）가 나오는데, f（0） = f（1） = 1이라고 했지. 근데 이거 어디서 본 것 같지 않아? 맞았어 바로 피보나치 수열이야.

신기하지? 1 x n짜리 체스판을 모노미노와 도미노로 덮는 방법이 n번째 피보나치 수열과 같다니 말이야.

[해당 패턴을 예측할 수 있는가?]

자 이제 마침내 오늘의 난제에 도달했어. 오늘 다룰 조합론의 미해결 난제는 5-5 램지수와 1324-회피배열.


1. 5,5 램지수 （R（5,5））

램지수를 알기 전에 완전 그래프를 이해해야돼. 완전그래프는  K_n으로 표현하는데, 이 n개의 꼭지점들이 서로 서로 연결되어있는 그래프를 의미해. （그래프는 너네가 생각하는 x축, y축과는 다소 다를거야.）

완전그래프 5, 즉 K_5는 다음과 같아.


[5개의 꼭지점이 모두 연결된, 일명 완전그래프. K_5]

자 이제 램지수로 넘어가볼까? 일단 램지수 （a,b）를 R（a,b）라고 써. R（a,b）는 뭐냐하면, 완전그래프 n, 즉 K_n의 변들을 빨강과 파랑으로 칠했을 때, 빨간 색의 완전그래프 K_a 나 파란 색의 완전그래프 K_b를 가지는 최소한의 n의 값은 무엇인가? 라는 질문이야.

질문이 어렵지?

여기 R（3,3） 예제야.

GIF

[이름은 별 상관 안해도 돼. 여기서 중요한 건, 임의로 변들을 색칠했는데, Fred와 Charlie와 Evelyn을 이어보면 빨간색 K_3 그래프가 완성된다는거야]

R（3,3） = 6 이라고 증명되어졌는데, 못믿겠다면, K_6 완전그래프를 그리고 색깔을 아무렇게나 칠해봐. 최소한 빨간색 혹은 파란색의 K_3 완전그래프가 있을거야. （둘다 있을 수도 있지만 둘다 없을 수는 없어）

R（3,3） 이 5일 수는 없냐고? 그럴 순 없어. 다음의 예제를 보면 명확해질거야.


[위와 같이 색칠하면, 빨간색 K_3도, 파란색 K_3도 존재하지 않는다. 고로 R（3,3）은 5보다 커야된다.]

문제는, R（a,b）에서 a와 b가 둘다 같이 커지면 정말 골치가 아파진다는거야. K_3 그래프야 쉬워. 3 점을 찍고 모두 연결되려면 3개의 변만 있으면 되거든. 하지만 K_4는 6개의 변, K_5는 10개… 이렇게 빠른 속도로 커져.


[R（3,3,3）의 예제. 즉 빨간색, 파란색, 초록색으로 칠했을 때 빨간색이나 파란색이나 초록색이나 최소한 하나의 K_3를 갖기 위해 필요한 최소 꼭지점의 개수는 17개로 증명되었다. R（3,3,3） = 17인 셈이다.]

오늘의 난제로 소개한 R（5,5）는, 빨간색 K_5완전그래프나 파란색 K_5완전그래프를 포함하기 위해서는 최소한 몇개의 꼭지점을 가진 완전그래프가 필요한가? 라는 질문이야. 수학자들은 이 숫자가 43 이상 49 이하라는 것 까지 알아냈어.

7개의 숫자 중 하나만 찍으면 되니 쉬워보인다구? 천만에! K_43의 완전그래프의 모든 변의 개수는 946이야. 거기다가 이를 빨간색과 파란색으로 칠하는 경우의 수는 약 6 x 10^284개 정도 돼. 여기서 K_5 빨간색과 K_5 파란색이 우연히 둘다 존재하지 않는 방법을 찾아낼 수 있을까? 엄청 시간이 걸릴걸?


[닝겐들은 정말로 어려운 문제를 마주하면 정신이 멍해진다고 한다.]

그래서 수학자들은 두손 두발 들고, 누군가가 더 현명한 제안을 해서 43~49의 범위를 더 줄여주길 바라고 있어.

R（5,5）만 문제냐고? 천만에. 5,5보다 큰 모든 숫자의 램지 숫자 모두 미해결로 남아있어. 숫자가 어떻게 증가하는지 그런 패턴도 보이지 않고 말이야. 오죽하면 수학자 스펜서가 이런 말을 했거든.

[어느날 외계인이 지구에 쳐들어와 R（5,5）의 값을 알려주지 않으면 지구를 폭파시켜버리겠다는 협박을 한다고 하면, 이 세상 모든 수학자, 과학자, 컴퓨터를 총동원해서라도 그 값을 알아낼 것이다. 만약, R（6,6）을 묻는다면, 차라리 그（것）들을 총동원해서 외계인을 물리칠 무기를 만드는 게 더 현명하다.]

2. 1324-회피배열
（원래는 avoiding pattern인데 한국말로 해석을 찾지 못해 임의로 회피배열이라 이름지었습니다.）

일단 배열의 의미를 알아봐야겠지? 배열은 영어로 퍼뮤테이션（Permutation）이라 하는데 그 앞글자 p의 그리스어를 따서 π（파이）를 사용해. 원주율이랑 헷갈리면 안돼. n배열이란 n개의 숫자의 정렬을 의미하는데, π（n）은 n개의 숫자를 정렬할 수 있는 경우의 수야.

여기까지 들은 몇몇 이과인들은, 어 그거 개 쉽네 ㅋㅋㅋ π（n）은 n! 아녀? 정답! n개의 숫자를 배열하는 경우의 수는 1에서 n까지 곱한 수야.


[일반적인 π（n）의 값을 구하는 건 존나쉽다.]

문제는 회피배열이지.

회피배열은 어떠한 패턴을 피하는 배열을 의미해. 쉬운 예제를 들어볼게.
π（2）에서 12-회피배열은 총 몇개일까?
π（2）는 1과 2의 정렬을 의미해. 1과 2의 정렬의 방법수는 총 2개, {1,2} 와 {2,1}이야. 여기서 12-회피배열이란, 12라는 오름차순적 성질을 가진 배열을 제외한다는 뜻이야. 다시말해 1,2가 되었든, 1,3이 되었든, 2,4가 되었든 뭐든 "두개의 항의 오름차순"이 존재하는 모든 항들을 다 배제하는거야. 심지어 1,4,2도 띄어져는 있지만 1,2라는 회피배열이 있기 때문에 제외돼.
물론 여기서는 π（2）, 즉 1과 2만 사용하는 배열들이니 {1,2}만이 제외되겠지. 고로 π（2）의 12-회피배열은 {2,1} 하나 뿐이야.

π（3）에서 12-회피배열은 총 몇개일까?
π（3）은 일단 총 6이겠지?
{1,2,3}
{1,3,2}
{2,1,3}
{2,3,1}
{3,1,2}
{3,2,1}
여기서 12-회피배열이 단순히 12의 오름차순이라고만 생각하면 안돼. 방금 전 말했듯 12의 오름차순의 성질을 가진 애들을 제외해야돼. 즉, 앞의 항보다 뒤의 항이 큰 모든 배열을 배제한다는 의미야.
{1,2,3}은 당연히 배제고.
{1,3,2}도 배제야. 처음 두 수 1과 3이 "오름차순"이니까 말이야.
{2,1,3}도 배제야. 왜냐하면 첫 항인 2와 마지막 항인 3이 오름차순이잖아.
{2,3,1}도 배제, 왠지 알겠지?
{3,1,2}도 배제
즉, π（3）의 12-회피배열은 {3,2,1} 하나 뿐이야.


좀 더 어려운 예제를 들어볼까?
일단, π（4）의 배열의 갯수는 24개. 다음과 같아.
{1,2,3,4}, {1,2,4,3}, {1,3,2,4}, {1,3,4,2}, {1,4,2,3}, {1,4,3,2},
{2,1,3,4}, {2,1,4,3}, {2,3,1,4}, {2,3,4,1}, {2,4,1,3}, {2,4,3,1},
{3,1,2,4}, {3,1,4,2}, {3,2,1,4}, {3,2,4,1}, {3,4,1,2}, {3,4,2,1},
{4,1,2,3}, {4,1,3,2}, {4,2,1,3}, {4,2,3,1}, {4,3,1,2}, {4,3,2,1}


그렇다면 π（4）의 132-회피배열의 수는 몇일까?


[뭘 기다리고 있는거야? 같이 함께 풀어보자.]

여기서 132-회피배열, 즉 앞의 수보다 더 큰 수가 뒤에 나오고, 그 뒤에는 그 두수의 중간인 수가 위치하는 배열을 모두 제외해야돼. 다음의 배열들이 제외돼.
{1,2,4,3} - 243 때문
{1,3,2,4} - 132 때문
{1,3,4,2} - 132, 142 때문
{1,4,2,3} - 142, 143 때문
{1,4,3,2} - 143, 142, 132 때문
{2,1,4,3} - 143, 243 때문
{2,4,1,3} - 243 때문
{2,4,3,1} - 243 때문
{3,1,4,2} - 142 때문
{4,1,3,2} - 132 때문

24개중 10개가 걸리니, 132-회피배열의 수는 14개.


수학자들은 다음의 π（n）에서 다음의 회피배열의 개수를 알아냈어.
12-회피배열
21-회피배열
123-회피배열
132-회피배열
213-회피배열
231-회피배열
312-회피배열
321-회피배열
1234-회피배열
1432-회피배열
2143-회피배열
1243-회피배열

문제는 1324-회피배열이야（사실 1342/2413-회피배열도 미해결 문제다）. 이건 되게 어렵거든. 4보다 큰 n에 대해서 1324-회피배열의 빈도수에 대해서는 알려진 바가 없어. 물론 컴퓨터로 계속 돌리면서 데이터는 모아지지만, 점점 n이 커지면 커질수록 배열의 수도, 제외되는 배열의 수도 점점 많아져서 데이터만 더 복잡해져. 이제 필요한건, 예측! 그리고 증명!

π（n）의 1324-회피배열의 수는 총 몇 개인가? 아직 미스테리로 남아있는 문제지.

글을 마치며...
조합론은 접하기는 쉬울 지 몰라도, 배우면 정말 어려운 분야 중 하나야. 수학에서 "천재성"은 정말로 중요한 덕목이긴 하지만, 조합론이 아닌 수학에서 "천재성"은 필수적인 덕목은 아니거든. 근데 조합론 만큼은 남들이 못본 것들을 꿰뚫어보는 "절대적인 통찰력" 이른바 천재성이 절대적으로 요구돼.


[단순히 노력만으로는 불가능한 학문, 노력의 천재도 "천재성"이 결여되어있다면 조합론은 힘든 여정이 될 것이다.]

누구나 이해할 수 있는 문제들 투성이지만, 누구도 생각치 못한 천재성이 필요한 학문, 그게 바로 조합론이야.

한번 조합론에 관심이 있다면 조합론에 관련된 서적들을 읽어보는 것도 좋을거야. 그럼 다음번에도 재밌는 난제들로 찾아올게. 그 때 까지 안녕~

---------------------------------------------------------------------------------------------------------------------------------------------
[돌아온 수학특집 1편: 페르마의 마지막 정리편: http://web.humoruniv.com/board/humor/read.html?table=pds&pg=0&number=489068]
[돌아온 수학특집 2편: 푸앵카레의 추측편: http://web.humoruniv.com/board/humor/read.html?table=pds&pg=0&number=489528]
[돌아온 수학특집 3편: 수의 난제들: http://web.humoruniv.com/board/humor/read.html?table=pds&pg=0&number=492051]

추천은 창작커에게 큰 힘이 됩니다!

지난번 많은 분들께서 수학 스릴러 소설에 관심을 가져주시고 응원을 해주셔서 감사합니다. 현재 1화를 작성중인데, 적은 양이 아닌지라 검토하고 보완하면 시간이 꽤 걸릴 것 같습니다. 1화가 완성되는 대로, 돌아온 수학특집을 통해서 공지를 드릴게요!

감사합니다!!