구독상품안내
얼광아, 우리도 무한도전처럼 서운한 외모를 가진 친구들과 함께 신개념 미남 페스티벌을 열어 보는 건 어때? 외모는 서운하지만 매력은 최고인 친구들을 초대해 파티를 여는 거야.
돈? 아…, 어쩌지? 나도 돈은 별로 없는데….
걱정하지 마! 내가 최소 비용으로 즐거운 파티를 기획해 줄게.
저…, 누구~세요?
몇 명을 초대하는 것이 좋을까?
좋아요! 그럼 박사님만 믿을게요. 그런데 파티에 몇 명을 초대하는 것이 좋을까요? 너무 많은 사람을 초대하면 비용이 많이 들잖아요. 또 서로 모르는 사람이 많으면 파티가 재미 없다구요.
하하~, 걱정 말게. 다 방법이 있다구!
즐거운 파티를 이루는 요소에는 맛있는 음식과 신나는 공연, 특별한 장소 등 많이 있지만 수학자들은 얼마나 많은 참석자들이 서로 아는 사이인지에 관심을 가졌다. 사실 참석자 모두가 서로를 안다면, 편안하고 즐거운 분위기에서 파티를 즐길 수 있다. 아는 사람이 아무도 없는 경우에도 서로를 알아가는 재미를 느낄 수 있다. 하지만 단 한 사람만 제외하고 나머지 사람들이 모두 아는 사이라면, 그 한 사람만 파티에서 소외될 가능성이 크다. 반대로 한 사람은 모든 사람들을 알지만, 나머지 사람들끼리 서로 모르는 경우라면 한 사람에게만 관심이 집중돼 자칫 파티가 지루할 수 있다.
따라서 파티를 계획할 때에는 서로 친구인 사람과 모르는 사람의 수를 균형 맞추는 것이 중요하다. 수학자들은 바로 이 문제를 연구했다. 일명 ‘파티 문제’다.
파티 문제를 풀기 위해선 먼저 몇 가지 가정을 해야 한다.
1. 파티에 참석한 사람들은 서로 친한 친구이거나 전혀 모르는 사이다.
2. 조금 아는 사이처럼 어중간한 상태는 없으며, 사이가 아주 안 좋은 경우도 없다.
3. A가 B를 친구로 생각한다면, B도 A를 친구로 생각한다. 혼자만 좋아하는 짝사랑은 없다.
이제 서로 친구인 사람 3명이 반드시 있거나, 서로 전혀 모르는 사이인 사람 3명이 반드시 있으려면 최소 몇 명을 초대해야 하는지 구해 보자. 그런데 만약 3명을 2명으로 바꾸면 답은 아주 간단해진다. 어떤 두 사람을 초대해도 둘은 서로 친구이거나 모르는 사이기 때문이다.
하지만 3명이 되면 답은 쉽게 구해지지 않는다. 예를 들어 정치, 희열, 호동을 초대한다고 가정하자. 정치는 희열과 친구고, 희열은 호동과 친구다. 그런데 호동은 정치를 모를 수 있다. 그렇다면 이 셋은 서로 친구라고 할 수 없다. 즉 3명을 초대하는 것으로는 부족하다.
이제 4명을 초대해 보자. 3명일 때처럼 안 되는 예 하나만을 찾으면 되지만, 사람수가 많아지면 바로 떠올리기가 쉽지 않다. 따라서 수학자들은 그래프 이론을 이용했다.
먼저 문제를 그래프 이론 문제로 바꿔 보자. 사람을 꼭짓점, 사람 사이의 관계를 선으로 표시한다. 이때 서로 친구 사이라면 빨간색, 전혀 모르는 사이라면 파란색으로 나타낸다. 그러면 문제는 ‘꼭짓점들 사이에 선을 어떻게 연결해도 파란색 또는 빨간색 삼각형이 반드시 존재하려면, 꼭짓점이 최소 몇 개 필요한가?’로 바뀐다.
이제 문제를 풀어 보자. 4명을 초대했을 때 A와 B, A와 C, B와 D는 친구 사이지만 A와 D, B와 C, C와 D는 모르는 사이라고 하면 파란색 또는 빨간색 삼각형이 그려지지 않는다. 따라서 4명은 답이 아니다. 5명일 때도 쉽게 안 되는 예를 찾을 수 있다.
그런데 문제는 6명일 때다. 어떻게 연결해도 쉽게 삼각형이 그려진다. 사실 6명을 초대했을 때 사람들 사이의 관계는 3만 2768가지나 된다. 두 사람 사이의 관계는 두 꼭짓점을 연결해 나타내는데, 이는 꼭짓점 n개 중에서 2개를 뽑는 경우의 수와 같다.
그런데 선은 빨간색과 파란색 2가지로 표시된다. 따라서
즉 모든 경우를 따져 보는 것은 불가능하다. 그래서 수학자들은 ‘비둘기집의 원리★’를 이용했다.
서로 친구인 사람이 3명이거나 모르는 사람이 3명일 때 파티 문제의 답안
만약 A와 B, A와 C, A와 D를 잇는 선이 빨간선이라면 B와 C, B와 D, C와 D를 잇는 선 중 하나라도 빨간선으로 그으면 서로 친구인 3명이 존재한다. 반대로 세 선 모두 파란선으로 그으면, 서로 전혀 모르는 3명이 존재한다.
따라서 6명인 경우에는 선을 어떻게 연결해도 파란색 또는 빨간색 삼각형이 그려진다. 즉 6명인 경우가 서로 친구인 3명 또는 모르는 사람 3명이 반드시 존재하는 최소 인원인 것이다.
경우의 수는 그래프로!
그런데 박사님, 그래프라고 하면 막대그래프나 꺽은선그래프, 이차곡선 같은 거 아니에요? 사람들에게 사랑의 작대기를 날린 것도 그래프인가요?
오호~, MC 쌩유! 수학 좀 하는데…. 학창시절 배운 것도 기억하고!
아하! 내가 그래프 이론에 대해 설명한다는 걸 깜박했구나. MC 쌩유의 말도 맞지만 꼭짓점과, 두 꼭짓점을 연결하는 선으로 이루어진 그림도 그래프라고 하지. 사실 그래프 이론이라고 하면, 스위스의 유명한 수학자 레온하르트 오일러가 발견한 쾨니히스베르크 다리 문제를 떠올릴 거야. 프레겔 강에 있는 7개의 다리를 한 번만 건너서 처음 시작한 위치로 돌아올 수 있는지 묻는 문제로, 그래프 이론의 시초거든.
이 문제가 발표된 이후 수학자들은 ‘최적화 문제’에 관심을 가졌어. 최단 거리로 길을 찾거나 최소 시간이나 최소 비용으로 물건을 만드는 등의 문제지. 그런데 사람들은 이런 문제를 풀 때면 작은 수에게 자꾸 속는 거야. 언뜻 작은 수를 이용한 방법이 최적이라고 여겨지는데, 사실은 그렇지 않거든. 예를 들어 볼까?
작은 수 함정이 있는 경우의 수 문제
재석이는 말 4마리를 100km 떨어진 성광이네 집까지 옮기려고 한다. 이때 재석이는 한 번에 두 마리까지 이동시킬 수 있다. 각각의 말이 이동하는 데 걸리는 시간은 아래와 같이 서로 다르다. 재석이가 말 4마리를 모두 옮기는 데는 최소 몇 시간이 걸릴까?
풀이 대부분 이 문제의 답을 14시간이라고 구한다. 경주마를 이용해야 최적의 방법이라고 여기기 때문이다. 따라서 경주마와 선수말을 이동시킨 뒤(2) 경주마를 이용해 돌아오고(1), 경주마와 회사원말을 이끌고 다시 성광이네로 간다(4). 다시 경주마를 타고 돌아온 뒤(1), 경주마와 양반말이 성광이네로 간다(6). 그러면 총 2+1+4+1+6=14시간이 소요된다.
그런데 이 경우 경주마의 능력이 다 발휘되지 못하는 문제점이 있다. 경주마가 아무리 빨라도 양반말과 함께 가면 6시간이 걸리기 때문이다. 따라서 경주마와 선수말을 이동시킨 뒤(2) 경주마를 타고 돌아오고(1), 회사원말과 양반말을 이동시킨다(6). 돌아올 때는 선수말을 이용하고(2) 경주마와 선수말을 이끌고 간다(2). 그러면 총 13시간이 걸려, 경주마를 계속 활용하는 것보다 시간이 적게 걸린다.
이처럼 작은 수에 현혹되지 않고 문제를 풀기 위해서 수학자들은 그래프 이론을 이용했어. 어때? 이제 그래프의 필요성을 알겠지?
그래프는 앞에서 살펴본 것과 같이 꼭짓점과, 두 꼭짓점을 연결한 선으로 구성돼 있어. 이 중에서도 서로 다른 두 개의 꼭짓점이 반드시 선으로 연결된 그래프를 ‘완전그래프’라고 하지. 꼭짓점의 개수에 따라 K₁, K₂, K₃, …, Kn으로 표현한단다.
그런데 완전그래프가 아니더라도, 그래프에서 한 부분이 완전그래프를 이룰 때가 많아. 이것을 ‘클릭’이라고 해. 클릭에 있는 꼭짓점의 개수를 ‘클릭의 크기’라고 하고, 어떤 그래프에서 주어진 크기의 클릭이 있는지 찾는 문제를 ‘클릭 문제’라고 하지.
앞에서 살펴본 ‘서로 친구인 3명이 반드시 있거나 또는 서로 전혀 모르는 사이인 3명이 반드시 있으려면, 최소 몇 명을 초대해야 하는지 구하는 문제’는 크기가 3인 클릭 문제(이하 3-클릭 문제)에 해당하지.
돌발 퀴즈
아래의 전개도를 따르는 상자 4개를 이용해 사방이 모두 다른 색이 되도록 상자를 쌓으세요. 상자를 쌓는 경우는 총 8만 2944가지로, 일일이 다 해 본다는 것은 불가능합니다! 하지만 그래프를 활용한다면 쉽게 문제를 풀 수 있습니다.
완벽한 파티는 항상 존재한다? 램지 정리
A-YO! 박사님, 잘 들어요. 우리가 겨우 6명을 초대하려고 못친소 페스티벌을 여는 건 아니잖아요. 많은 사람이 모일 수 있게 해 주셔야죠!
우리 얼광이 수학자한테까지도 따지고, 살아 있네!
파티 문제를 자연스럽게 확장하는 방법은 서로 친구이거나 서로 모르는 사람의 수를 늘리는 것이다. 만약 친구인 수와 모르는 사람의 수를 각각 4명으로 늘리려면, 빨간색 또는 파란색으로 이뤄진 K₄를 반드시 갖는 그래프의 꼭짓점의 개수를 구하면 된다. 즉 4-클릭 문제를 풀면 된다. 이 문제의 답은 1955년 미국의 수학자 앤드류 글리슨과 로버트 그린우드가 18명이라고 알아냈다.
그런데 서로 친구인 사람과 모르는 사람의 수를 꼭 같게만 해야 하는 걸까? 그렇지 않다. 글리슨과 그린우드는 서로 친구인 사람이 4명이거나 서로 모르는 사람이 3명일 때, 서로 친구인 사람이 5명이거나 서로 모르는 사람이 3명일 때를 각각 9명과 14명이라고 알아냈다. 그런데 이때 서로 친구인 사람이 4명이거나 서로 모르는 사람이 3명일 때와 반대인, 서로 친구인 사람이 3명이거나 서로 모르는 사람 4명일 때는 같은 결과를 갖는다. 그래프 문제를 풀 때 빨간색인지 파란색인지에 따라 색깔만 차이가 나기 때문이다.
이제 서로 친구이거가 모르는 사람의 수를 5명으로 늘려 보자. 그런데 비둘기 집의 원리를 이용해도 따져야 할 경우의 수가 사람이 계산할 수 있는 수준을 넘어선다. 10명에 이르면 경우의 수가 수백억 가지나 돼, 속도가 아주 빠른 슈퍼컴퓨터로도 구할 수 없다.
그렇다고 포기할 수학자들이 아니다. 1995년 미국의 수학자 제프리 엑수와 스타니스와프 라지쇼프스키, 캐나다의 수학자 존 매케이는 복잡한 수학 공식을 이용해 5-클릭 문제의 해가 43명에서 49명 사이라는 것을 밝혀냈다.
그리고 1930년, 드디어 모든 파티 문제를 다룰 수 있는 획기적인 연구 결과가 발표됐다. 바로 램지 정리다. 램지 정리는 꼭짓점의 개수가 충분히 큰 완전그래프의 선을 색칠할 때, 동일한 색의 선으로만 구성된 완전그래프가 항상 포함되어 있다는 것이다.
여기서 꼭짓점의 개수가 충분히 크다는 말은 서로 친구인 사람을 k명, 서로 모르는 사람을 l명이라고 했을 때 초대하는 사람의 수는 k+l명과 같거나 훨씬 많다는 뜻이다. 이때 k와 l값에 따라 큰 수의 의미는 변한다.
파티 문제에서 친구인지 모르는 사람인지 구별 없이 한 가지 색으로 선을 그으면, 이것은 완전그래프가 된다. 여기에 두 사람 사이의 관계를 나타내기 위해 빨간색 또는 파란색으로 색을 칠한다. 그런데 이때 램지 정리에 의하면, 어떤 한 부분이 빨간색 또는 파란색 완전그래프가 되는 꼭짓점의 개수가 반드시 존재한다. 즉 파티 문제에는 반드시 해가 존재한다는 뜻이다.
이것은 얼핏 대단한 이야기가 아닌 것처럼 들릴지 모른다. 하지만 수학에서는 증명되기 전까지는 아무것도 확실한 것으로 여기지 않는다. 즉 램지 정리가 증명되기 전까지는 파티플래너의 기획대로 만들 수 없는 파티가 존재할 수도 있다는 것을 염두해야 했다. 하지만 램지 정리 덕분에 이런 고민이 말끔히 해결됐다.
파티 문제에서 시작된 램지 정리는 무질서한 것에서 질서를 찾아낼 수 있다는 데 의미가 있다. 현재는 네트워크와 인공지능 분야 등 여러 곳에서 활용되고 있다.
램지수, 범위로 구한다
에이, 뭐야? 결국 현재로선 모든 파티 문제의 답을 구할 수는 없는 거잖아요! 이제 어쩌죠? 난 서로 친구인 6명이 있거나 서로 모르는 사람이 4명인 파티를 만들고 싶었다고요. 그런데 몇 명에게 초대장을 보내야 하는지도 모른다니…!
걱정하지 말라니까! 정확한 답은 구할 수 없지만, 어림잡아 몇 명 정도 초대해야 하는지 그 범위는 알 수 있다구!
램지 정리로 모든 파티 문제에는 정확한 답이 존재한다는 것은 알 수 있었지만, 파티 문제의 정확한 답은 구할 수 없다. 하지만 1947년 헝가리 수학자 폴 에르되시와 헝가리계 호주 수학자 조지 세케레시는 램지 정리를 따르는 최소의 정수를 ‘램지수’라고 정의했다. 이후 수학자들은 램지수의 범위를 구할 수 있는 정리를 발표했다.
램지수
서로 친구인 사람의 수를 k, 서로 모르는 사람의 수를 l이라고 하자. 이때 k명 또는 l명이 반드시 존재하도록 하기 위해, 파티에 초대해야 하는 최소 사람의 수를 R(k, l)이라고 표기한다.
아래의 표는 수학자들이 현재까지 찾아낸 램지수와 램지수의 범위다. 앞에서 살펴본 3-클릭 문제와 4-클릭 문제의 램지수는 R(3, 3)=6과 R(4, 4)=18이다.
램지수의 범위는 상한과 하한으로 나눠 구한다. 상한은 수가 가질 수 있는 최고 큰 값이고, 하한은 가장 작은 값이다. 상한을 구하는 공식은 여러 가지가 고안 돼 있는데, 여기서는 한 가지만 소개한다.
대만의 수학자 팬청과 미국의 수학자 로널드 그램은 R(k, l)≤R(k-1, l)+R(k, l-1)이라는 공식을 1983년에 발표했다. 이 공식은 k와 l이 모두 2보다 크거나 같을 때 성립한다. 여기서는 공식이 맞는지 확인하기 위해 k와 l에 각각 3과 4를 대입해 보자.
R(3, 4)≤R(2, 4)+R(3, 3)이다. 그런데 R(2, 4)는 4이고, R(3, 3)은 6이다. 둘을 더하면 10이 되는데, 실제 R(3, 4)은 9이기 때문에 비교적 정확하게 상한이 구해지는 것을 알 수 있다.
그렇다면 램지수의 하한은 어떻게 구할까? 사실 하한을 구하는 방법은 알려진 것이 없다. 램지수를 찾는 것만큼이나 어렵기 때문이다. 하지만 k와 l의 값이 같은 경우에는 여러 가지 공식이 개발되어 있다. 그 중 하나가 R(k, k)≥[sqrt{{2}^{k}}$]이다. 여기서 [$x$]는 $x$를 넘지 않는 최대 정수다.
그런데 실제 값 4와 18은 차이가 너무 크다. 과연 이 공식이 의미가 있는 걸까? 앞에서 살펴본 것과 같이, 숫자가 조금만 커져도 경우의 수는 상상을 초월할 만큼 커진다. 따라서 헤아릴 경우의 수를 조금만 줄여 줘도 램지수를 찾는 데 도움이 된다.
최근에 수학자들은 상한과 하한을 구하는 공식을 이용해 경우의 수를 줄인 뒤, 모든 나머지 경우를 일일이 따져 램지수를 구한다. 또한 지금까지 발견된 상한과 하한 공식보다 더 정확한 공식을 찾기 위해 노력하고 있다.
램지 정리 덕분에 결혼했다? 해피엔딩 문제
박사님, 왜 수학과 과학에서는 새로운 것을 발견하면 자기 이름을 붙이잖아요? 만약에 제가 현재까지 구해지지 않은 램지수를 발견하면 제 이름이 붙는 건가요?
당연하지. 실제로 지금까지 발표된 램지수와 램지 범위에는 발견한 수학자들의 이름이 붙어 있다고. 그런데 말이야, 수학자들은 때론 사람 이름 말고 특별한 것으로 이름을 짓기도 해.
파티 문제 외에도 램지 정리로 해결할 수 있는 대표적인 수학문제가 있다. 바로 ‘해피엔딩 문제’다. 이름만 들으면 파티 문제처럼 재미있는 상황을 설명하는 문제일 거 같지만, 볼록 n각형이 그려지려면 점을 최소 몇 개 찍어야 하는지 묻는 문제다.
그렇다면 왜 해피엔딩 문제라는 이름이 붙었을까? 헝가리계 호주 수학자 에스터 클라인과 조지 세케레시는 이 문제를 해결하기 위해 함께 연구했다. 그 결과 놀라운 수학적 결과를 발견했을 뿐만 아니라, 둘은 사랑이 싹터 결혼하게 된다. 이 모습을 처음부터 지켜본 에르되시가 해피엔딩 문제라고 이름 지은 것이다.
해피엔딩 문제를 풀기 위해선 먼저 종이 위에 점들을 아무 생각 없이 무작위로 찍어야 한다. 점을 찍으면 대개 질서라고는 찾아볼 수 없지만, 아주 우연히 세 점 이상이 한 직선 위에 일렬로 놓인다면 규칙을 발견할 수 있다. 하지만 이것은 통계적으로 매우 낮은 확률이기 때문에, 일어나지 않는다고 가정한다. 따라서 어떤 세 점도 한 직선 위에 놓이지 않을 때를 ‘일반적인 위치’에 있다고 하자.
1932년 에스터 클라인은 적어도 점을 5개 찍어야 볼록 사각형을 만들 수 있다고 밝혔다. 이를 증명하기 위해서는 먼저 5개의 점을 무작위로 찍은 뒤, 이 중 세 점을 이어 삼각형을 만든다.
이제 볼록 오각형으로 넘어가 보자. 항상 볼록 오각형이 만들어지려면 점을 몇 개 찍어야 할까? 볼록 오각형만 돼도 헤아려야 하는 경우의 수가 많아 구하기가 쉽지 않다. 하지만 수학자들은 노력 끝에 볼록 오각형과 육각형의 경우에는 각각 9개와 17개의 점을 찍어야 한다는 걸 증명했다. 그러나 볼록 칠각형 이상에서 필요한 점의 개수는 아직까지 풀리지 않았다.
램지수로 풀커슨상을 받은 김정한 교수
박사님, 제가 어제 램지수라고 인터넷 검색을 했더니, 2006년 방영됐던 <;눈의 여왕>;이라는 드라마가 나오더라고요. 그거 내 친구(?) 현빈이 나오는 드라마인데, 대체 램지수와 <;눈의 여왕>;은 무슨 관련이 있는 거예요?
아, 그 드라마는 연세대 수학과 김정한 교수를 실제 주인공으로 제작됐거든. 김정한 교수는 램지수와 관련된 미해결 난제를 풀어 풀커슨상을 받았지. 직접 만나 보러 갈래?
오늘 강연은 올해 풀커슨상을 수상한 한태웅 박사의 초청강연이 되겠습니다. 한태웅 박사는 올해 60년 동안 풀리지 않았던 램지수 부분을 명쾌하게 증명함으로써, 조합론 분야에서 가장 뛰어난 논문에 수여되는 풀커슨상을 수상하셨습니다.
램지수는 쉽게 얘기하자면 큰 집단에서 공통 특성을 갖는 작은 집단을 찾을 수 있느냐 없느냐에 관한 문제라고 할 수 있습니다. <;…중략…>;
이렇듯 램지수를 증명하게 됨으로써 우리는 유한한 개체가 점점 늘어날 경우 어떤 일이 벌어질지 미리 예측할 수 있게 되었습니다.
- KBS 드라마 <;눈의 여왕>; 중
드라마 속 현빈의 이야기가 실제 교수님 이야기라고 하던데, 정말인가요?
물론 제가 극중 태웅이처럼 권투를 하거나 부잣집 딸과 지독한 사랑을 한 것은 아니에요. 극중 태웅이가 세운 수학 업적이 제 이야기이지요. 드라마 중간에 나오는 수학 이야기도 제가 드라마 작가에게 직접 알려 준 거예요.
이 작품은 수학자가 주인공인 드라마를 제작하고 싶다고 연락이 와서 참여하게 됐어요. 작가들과 여러 번의 회의를 통해서 대중들이 수학과 친숙해질 수 있는 소재를 발굴했죠. 현빈 씨에게 수학을 가르쳐 준 것이 추억으로 남아 있네요.
교수님처럼 수학계 난제를 해결하려면 어떤 노력이 필요할까요?
다양한 분야에 호기심을 가지고, 그것이 왜 그런지 스스로 답을 찾는 노력을 하면 돼요. 학교에서 수학을 가르치는 이유는 생각하는 힘을 길러 주기 위해서예요. 수학 문제를 스스로 고민해서 풀다 보면 문제 해결 능력이 생기거든요.
그런데 요즘 학생들은 같은 문제를 반복해서 푸는 연습을 하면서 생각을 하지 않고 문제를 풀려고 해요. 이런 공부법은 사고력을 키우는 데 도움이 되지 않아요. 꼭 수학 문제가 아니더라도 궁금증이 생기면 그것에 답을 구하기 위해 가정과 추측을 하고, 나름대로 답을 구한 뒤 그 답이 맞는지 확인하세요. 그러면 수학적 사고력이 길러지고, 이것은 난제를 해결하는 원동력이 됩니다.
얼광아, 사실 파티 문제에서 수학적으로 가장 잘 조직된 것은 한 가지 색으로 그려진 그래프래. 즉 서로 모두 모르거나 모두 아는 경우지.
정말? 그럼 아예 모르는 연예들로 초대하자. 나 요즘 대세인 조정치를 만나 보고 싶어. F1 노홍철도. 근데 우리가 초대하면 올까?
서로 모두 몰라야 한다니까. 조정치와 노홍철은 이미 아는 사이잖아. 얼광이는 파티 전에 다시 공부 좀 해야겠다.
아, 몰라몰라! 일단 초대하자고. 못생긴 형제들이여 일어나라~! 곧 축제가 시작될지니…. 크크크~.
