d라이브러리

프런클의 추측은 헝가리의 수학자 피터 프런클이 1979년 제기한 문제입니다. 지금은 프런클이 문제를 만들었다는 걸 많은 수학자가 알고 있지만, 한동안 누가 이 문제를 냈는지 몰랐습니다. 1987년 미국 수학자 피터 윙클러가 호주에서 발간되는 수학 잡지에 이 문제를 소개하면서 출처와 해답 말고는 모든 게 다 알려져 있다고 소개할 정도였죠. 프런클이 이 문제를 만들었다는 사실이 밝혀진 것은 1995년입니다. 프런클이 직접 이 문제를 어떻게 만들었는지 설명하는 글을 써서 발표하면서 궁금증이 해소됐지요.

프런클은 1979년 프랑스 파리에서 캐나다 몬트리올로 여행을 가는 중에 프런클의 추측을 떠올렸습니다. 몬트리올에서 미국 수학자 로널드 그레이엄을 만나 문제를 이야기해 줬는데, 그레이엄이 여기저기에 문제를 퍼뜨렸다고 합니다. 1981년에는 캐나다 수학자 드와이트 더프스가 알게 됐고, 3년 뒤 더프스가 캐나다 벤프에서 열린 수학워크숍 초록집에 프런클의 추측을 소개합니다. 이렇게 프런클의 추측이 유럽에서 북미로 이동하지요.

그 다음에는 호주로 갑니다. 1987년 호주수학회에서 발행하는 신문에는 호주 수학자 제이미 심슨이 학회 도중 이 문제를 소개했다는 이야기가 실려 있습니다. 이 글의 제목이 ‘A much-travelled conjecture’입니다. 여행을 아주 많이 한 추측이라는 거지요.

프런클의 추측에 관한 첫 논문은 호주 위쪽에 있는 나라 파푸아 뉴기니에 사는 두 명의 호주 수학자 존 리날도와 디네쉬 사르바트가 씁니다. 아마도 호주수학회 신문의 영향이 아닐까 싶습니다. 이 논문 이후 여러 연구가 나오기 시작했습니다. 프런클의 추측과 관련한 중요한 논문 중 하나는 지금은 미국 매사추세츠대학교 수학과에서 일하고 있는 비요른 퓨넨 교수가 미국 캘리포니아대학교 버클리캠퍼스 학부생일 때 쓴 겁니다.

프런클의 추측
{1,2,…,n}의 부분집합으로 이뤄진 m개 목록이 합 집합에 대해 닫혀 있고 공집합이 아닌
집합을 갖 고 있다면, 그 중 절반 이상의 집합에 동시에 속한 원소가 반드시 있다.
 

사실 더 이상 합집합을 만들어도 새로 생기는 집합이 없도록 만들었으니 웬만하면 절반 이상에 동시에 속한 원소가 있을 거라고 생각하기 쉽습니 다. 하지만 이 문제는 40년 가까이 미해결 난제입 니다. 그래도 몇몇 경우에 참이라는 것이 밝혀졌 습니다. 그 중 일부만 소개하면 다음과 같습니다. 
 

변형된 프런클의 추측
남자 n명과 여자 m명이 참가한 파티에서 적어도 한 쌍의 남녀는 함께 탱고를 췄다. 단 남자끼리 또는 여자끼리는 춤을 추지 않았다. 서로 춤을 추지 않은 사람들의 집합 중 더 이상 원소를 추가할 수 없는 집합을 ‘좋은 집합’이라고 하자. 즉 좋은 집합에 속하지 않은 모든 사람은 좋은 집합 안에 있는 누군가와 춤을 춘 적이 있다. 이때 전체 좋은 집합 중 절반 이하의 좋은 집합에만 속한 남자가 반드시 있다.
 

변형된 프런클의 추측과 원래 추측은 전혀 다른 문제처럼 보입니다. 하지만 2015년 독일 수학자 헤닝 브룬과 올리퍼 샤우트, 프랑스 수학자 피에르 카빗, 노르웨이 수학자 얀 아르네 텔레는 두 추측이 완전히 동치라서 하나가 증명되면 다른 하나도 증명된다는 것을 밝혔습니다.

2017년 1월에는 브룬과 샤우트가 변형 프런클의 추측이 대다수의 경우 참이라는 사실을 증명한 결과를 유럽조합론학회지에 발표했습니다. 남녀가 어떤 동전을 던져서 앞면이 나오면 춤을 출 때 전체 좋은 집합의 절반 이하 집합에 모두 속한 남자가 있을 확률이 1에 매우 가깝다는 것입니다. 더 정확히 말하면 동전의 앞면이 나올 확률이 상수 P로 고정돼 있고, 전체 사람 수가 무한히 커지면 절반 이하의 좋은 집합에만 속한 남자가 있을 확률이 1에 수렴한다는 것이지요.

따라서 사람 수만 충분히 많다면 프런클의 추측의 99% 이상이 맞는 것입니다. 다시 말해 프런클의 추측에 반례가 있다면 매우 드물게 있다는 것이지요.