d라이브러리

1, 2, 4, 7, 11처럼 수를 나열한 것을 ‘수열’이라고 부릅니다. 이런 수열의 일부를 똑 떼서 살펴보면 수가 점점 커지는 ‘증가수열’ 또는 점점 작아지는 ‘감소수열’을 발견할 수 있습니다. 최근 수열을 부분수열로 쪼개서 볼 때 나타나는 수학적 성질을 밝힌, 재밌는 이름의 수학 정리가 나왔습니다. 1, 2, 4, 7, 11처럼 수를 나열한 것을 ‘수열’이라고 부릅니다. 이런 수열의 일부를 똑 떼서 살펴보면 수가 점점 커지는 ‘증가수열’ 또는 점점 작아지는 ‘감소수열’을 발견할 수 있습니다. 최근 수열을 부분수열로 쪼개서 볼 때 나타나는 수학적 성질을 밝힌, 재밌는 이름의 수학 정리가 나왔습니다. 

헝가리의 유명한 수학자 에르되시 팔은 21살이던 1934년에 이미 수학 박사학위를 받았습니다. 20살에 에르되시는 부다페스트에서 수학을 좋아하는 사람들과 어울리며 지냈는데 그중에는 에르되시보다 조금 나이가 많은 헝가리 수학자 세케레시 죄르지도 있었습니다. 

1935년 세케레시와 에르되시는 아주 유명한 수학 논문을 출판합니다. 2016년 7월호 수학동아 따끈따끈한 수학에 실린 ‘해피엔딩 문제’가 바로 그 논문 이야기(디라이브러리에서 확인 가능)입니다. 이 논문에는 해피엔딩 문제뿐만 아니라 다른 재밌는 결과도 있습니다. 바로 수열에서 어떤 성질을 갖는 부분수열을 찾는 것이지요.

먼저 서로 다른 자연수 5개로 이뤄진 수열 중 하나를 골라봅시다. 수열의 길이는 그 수열에 있는 수의 개수라고 합시다. 예를 들어 (1, 5, 2, 4, 3)이라는 수열이 있다고 합시다. 이 수열에서 몇몇 수를 지우면 (1, 5), (1, 2, 3), (1, 4, 3)처럼 부분수열을 얻을 수 있습니다. 이런 부분수열 중에는 (1, 5)나 (1, 2, 4)처럼 증가수열도 있고, (5, 2)나 (5, 4, 3)처럼 감소수열도 있습니다. 

그런데 (1, 3, 2, 4, 5)라는 수열에 증가하는 부분수열은 길이가 4인 (1, 3, 4, 5)가 있지만, 감소하는 부분수열은 아무리 길어도 길이가 2밖에 안 됩니다. 극단적으로 (5, 4, 3, 2, 1)에는 증가하는 부분수열의 길이가 길어야 1밖에 안 됩니다.

놀랍게도 길이가 5인 모든 수열에서 길이가 3인 부분수열 중에 증가수열 또는 감소수열을 항상 찾을 수 있습니다. 이 사실을 처음으로 밝힌 사람들이 바로 에르되시와 세케레시입니다. 아울러 길이가 충분히 길면, 원하는 길이를 가진 증가만 하거나 감소만 하는 부분수열을 얼마든지 찾을 수 있다는 것을 밝힙니다.

이후 에르되시-세케레시 정리처럼 ‘어떤 상황에서 일부를 지우고 남은 것만 보면 좋은 성질을 갖는다’와 같은 사실을 찾는 연구가 많이 이뤄지고 있습니다. 이런 연구의 시초가 바로 에르되시와 세케레시가 1935년 발표한 논문이라고 할 수 있지요. 

수학 연구에 롤러코스터가 등장한 이유는?

최근 이와 관련해 재밌는 연구 결과가 나왔습니다. 2019년 5월 캐나다 워털루대학교의 테레사 비들과 안나 루비브를 포함한 5명의 연구자와 독일 킬대학교 플로린 마네아, 디르크 노보트카는 ‘롤러코스터’라는 단어를 담은 논문을 출판합니다. 수학자의 연구와 롤러코스터가 무슨 관계일까요? 
이 논문에서는 어떤 수열에서 연속으로 증가하는 부분과 연속으로 감소하는 부분으로 쪼개볼 때 조각 수가 3개 이상이고, 각각의 길이가 3 이상이면 그 수열을 ‘롤러코스터 수열’이라고 부르기로 했습니다. 예를 들어 (1, 4, 5, 3, 6, 7)은 (1, 4, 5), (5, 3), (3, 6, 7) 이렇게 3개의 조각으로 나눌 수 있는데, 이 중에는 2개만으로 구성된 (5, 3) 조각이 있어 롤러코스터 수열이 아닙니다. 하지만 (1, 3, 5, 4, 2, 6, 7, 8)에는 (1, 3, 5), (5, 4, 2), (2, 6, 7, 8)과 같이 증가하거나 감소하는 3개의 조각이 있고, 모두 길이가 3 이상이므로 롤러코스터 수열입니다.

길이가 n인 수열이 있다면 그 수열의 부분수열 중에 긴 롤러코스터 수열을 찾을 수 있을까요? 바로 이 논문에서는 이를 증명합니다.

왜 n≥8이라고 했을까요? n=7일 때는 틀린 경우가 있다고 합니다. 수열 (5, 2, 6, 3, 1, 7, 4)이 바로 그 반례입니다. 이 수열의 부분수열 중에 길이가 4인 것은 모두 롤러코스터 수열이 아닙니다. 예를 들어 그 부분수열이 (5, 2)로 시작한다면 그 다음에 쓸 수 있는 것은 1뿐이고, 그 다음에 7을 쓰면 (1, 7) 때문에 롤러코스터 수열이 아닙니다. 부분수열이 (5, 6)으로 시작하면 그 다음에는 7밖에 쓸 수 없고 그 후에 4를 넣으면 롤러코스터 수열이 아닙니다. 이런 식으로 일일이 따져보면 이 경우 가장 긴 롤러코스터 수열의 길이는 3밖에 안 된다는 것을 알 수 있지요. 

이 수열은 비들과 루비브가 2017년 인터넷 논문 공개 사이트인 아카이브에 공개한 논문에 나와 있습니다. 이 논문에서 두 수학자는 이 수열 외에는 항상 길이가 절반 이상인 롤러코스터 수열이 있지 않겠냐고 추측을 했습니다. 5월의 결과는 바로 이 추측을 해결한 겁니다. 

딱 맞는 재밌는 이름 짓기는 어려워~

그런데 왜 하필 이런 수열을 롤러코스터라고 불렀을까요? 많이 오르락내리락 해야 롤러코스터처럼 보일 텐데, 이 논문에서 정의한 롤러코스터 수열은 오르막 구간이 짧아도 안 되고, 내리막 구간이 짧아도 안 됩니다. 즉 한 구간이 꽤 깁니다. 그래서 저 역시 이 이름이 조금 이상하다고 생각했습니다. 왜 이런 이름을 지었는지는 연구자들만 알겠죠? 참고로 2013년에도 한 수학자가 롤러코스터 순열이라는 개념을 만들었는데, 여기서는 오르락내리락이 최대한 많이 반복하는 것을 다룹니다. 
수학 연구를 하다 보면 새로운 개념을 만들고 이름을 붙여야 할 때가 많습니다. 흥미로운 개념을 만든 후 이름을 붙일 때 재미있으면서 어울리는 이름을 찾아서 붙이는 작업이 참 어렵습니다. 영어 사전을 뒤지면서 어울리는 단어를 찾아보기도 하지요. 제가 만든 수학 용어 중에는 이제 백여 편 이상의 수학 논문에서 사용하는 것도 있습니다. 한번은 다른 한국 사람 두 명과 쓴 논문에서 순우리말로 나무라는 개념을 만들어 사용하면서 영어로 ‘namu’라고 표기하기도 했지요. 

여러분도 롤러코스터처럼 재미있는 이름을 붙일 기회가 오면 기발하고 알기 쉬운 용어를 찾아서 남길 수 있습니다.

참고자료 테레사 비들, 아마드 비니아즈, 로버트 커밍스, 안나 루비브, 플로린 마네아, 디르크 노보트카, 제프리 샬릿 ‘Rollercoasters : long sequences without short runs’

엄상일 교수는 KAIST 수학과를 졸업하고, 미국 프린스턴대학교에서 박사 학위를 받았습니다. 현재 기초과학연구원과 KAIST에서 연구와 강의를 하고 있습니다. 그래프이론과 이산수학, 조합적 최적화가 주요 연구 분야입니다. 2012년에는 젊은과학자상(대통령상)을 수상했고, 2017년에는 한국차세대과학기술한림원 회원으로 선정됐습니다.