미팅에서 킹카되는법

14일, 거리마다 사탕바구니를 든 커플들로 넘쳐나는 화이트데이를 앞두고 ‘솔로탈출’에 목을 매는 이들이 많다. 솔로 탈출을 위해 선택하는 가장 좋은 방법은 미팅, 소개팅.

그런데 미팅에서 커플이 되기란 생각만큼 쉽지 않다. 사랑의 화살표가 엇갈려 서로 다른 상대를 쳐다보는 일이 많기 때문이다. 예를 들어 남자 A는 여자 A를, 여자 A는 남자 B를, 남자 B는 여자 B를, 여자 B는 남자 A를 좋아하는 상황이 벌어질 수가 있다. 이러면 아무도 커플이 되지 못한다.

미팅에 참가한 남녀 모두가 좋아하는 사람과 커플이 되는 방법은 없을까.

놀랍게도 그런 방법이 있다. 실제로 수학자들은 남성에게 고백할 기회를 여러 번 줘서 모두가 커플이 될 수 있도록 하는 미팅 방식을 연구했다. 이를 ‘안정적인 결혼 문제’라 한다. 미국의 수학자 데이비드 게일과 로이드 샤플리는 1962년 이 문제의 해결 방법을 제시했다.

남성 n명과 여성 n명이 서로 파트너를 정한다고 가정하자. 남성과 여성은 선호도에 따라 순위를 매긴 목록을 작성한다. 같은 순위는 없다. 먼저 남자는 매일 자신의 목록에서 가장 위에 있는 여성을 찾아간다.

여성은 자신을 찾아온 남성 가운데 자신의 목록에서 가장 위에 있는 사람에게 ‘내일 다시 오세요’라고 말하며 약속을 잡고, 나머지에게는 ‘약속이 있어요’라고 답하며 거절한다.

거절당한 남성이 없으면 커플이 완성된다. 만약 거절당한 남성이 있다면 그는 자신을 거절한 여성을 목록에서 지운다. 그리고 다시 자신의 목록에서 가장 위에 있는 사람을 찾아간다.

게일리-샤플리 알고리즘. 남성 4명과 여성 4명이 그림과 같은 선호도를 갖고 있다면 3일이면 모두 커플이 된다. 여자 1호와 남자 2호, 남자 4호는 가장 마음에 든 상대와 커플이 되고, 나머지 사람들도 대부분 두 번째로 호감을 가진 상대와 짝이 된다.

이 방법으로 짝을 정하면 아무리 길어도 n²번 안에 모두 짝을 찾을 수 있다. 또 모두가 가장 좋아하는 상대와 짝이 될 수는 없지만, 호감도가 가장 낮은 사람과 짝이 되는 최악의 상황만은 피할 수 있다.

사실 남녀 사이의 관계는 예기치 못한 변수가 많기 때문에 게일-샤플리 알고리즘을 곧이곧대로 믿을 수만은 없다. 하지만 고등학교에 진학하는 학생들에게 학교를 배정하거나, 신장 이식을 할 때 맞는 사람을 찾아 신장을 주고받는 경우 등 짝을 짓는 방법에는 매우 효과적이다. 실제로 미국에서는 의대졸업자와 수련병원을 짝지을 때 이 방법을 사용한다.

이 밖에도 수학동아 3월호 기획기사에는 운명의 상대를 만날 확률과 수학공식을 이용한 사랑 고백법 등 사랑에 관한 재미있는 수학 내용을 만날 수 있다.

조가현 기자 gahyun@donga.com