구글 입사 문제(말 25마리...)와 토너먼트 규칙
문제
이 문제는 구글 입사 면접 문제 중 하나로, 인터넷에서 제법 알려졌으며 TV프로 '문제적 남자'에 소개되기도 했습니다.
「
말 25마리가 있다. 말들을 한 번에 5마리씩 경주시켜, 빠르기를 대조해볼 수 있다.
전체 25마리 중 빠르기로 1위, 2위, 3위인 말을 정확히 알아내려면 경주를 최소 몇 번 시켜야 하는가?
말들은 빠르기가 서로 모두 다르고, 각자 일정하다.
넌센스 퀴즈는 아니니, 논리적으로 답을 도출하라.
」
전체 1위를 찾는 것은 간단합니다. 보통의 토너먼트 방법으로, 5마리씩 5개조를 경주시킨 뒤(말하자면 1차전)
조별 1등끼리(5마리) '전체 1위 결정전'을 치러 거기서 1등한 말을 전체 1위로 판정하면 됩니다.
'전체 1위 결정전'에서 2등, 3등한 말'들을 전체 2위, 3위로 인정하면 안 될까요? 안 됩니다.
빠르기가 전체에서 2위인 말이, '1차전에서 운 나쁘게 1위와 같은 조가 되어' 일찍 탈락했을 수 있기 때문입니다.
풀이는 이렇습니다.
'전체 1위 결정전' 결과 빠르기순으로 말들을 A, B, C, D, E라고 하겠습니다.(A가 1등, E가 5등)
그럼 이 말들이 1차전을 치렀던 조들은 각각 'X 출신 조'라고 할 수 있습니다.
'빠르기로 전체 2위일 가능성이 있는 말'들은
A 출신 조에서 2위를 한 말(편의상 A-2와 같은 식으로 표기), B 이렇게 두 마리입니다.(A-2, B-1)
'빠르기로 전체 2위나 3위일 가능성이 있는 말'들은
A-2. A-3, B-1, B-2, C-1 이렇게 5마리입니다.
이 5마리로 '전체 2, 3위 결정전'을 치러 거기서 1등, 2등 말을 전체 2위, 전체 3위로 판정하면 논리적으로 옳습니다.
정답은 7번입니다.(1차전 5번, 전체 1위 결정전 1번, 전체 2, 3위 결정전 1번)
이 방식을 '정답 방식'이라고 해보겠습니다.
현실에서는 '운, 상성, 경기 도중 컨디션/실력 변화'도 있을 수 있겠지만,
경기에 앞서 경기 방식을 설정할 때 그런 걸 미리 차별적으로 대해주는 것은 오히려 불공정합니다.
예를 들어 '월드컵에서 한국은 대진 운이 안 좋을 것 같으니, 한국은 1차전에서 무조건 부전승으로 올리겠습니다.'라고 미리 정하는 것은 불공정합니다.
실제 대회
실제 토너먼트 대회에서는 1위 결정 후, 가장 높게 진출했던 선수끼리 시합을 시켜 나머지 순위를 결정합니다.
이러면 대진 운 문제로, 어처구니 없게도 '중간 실력도 안 되는 선수'가 3위상을 수상하는 경우도 나올 수 있습니다.
진짜 실력 있는 선수는 수상하지 못하고요.
대진운에 의한 왜곡(실력이 높은 선수가 수상하지 못하고 오히려 실력이 낮은 선수가 수상하는 경우)을 줄이면서도 경기 수를 너무 많지 않게 하고자 하는 방법으로 '스위스리그'라는 방식도 있는데, 마찬가지로 왜곡을 없애진 못하고(확률상 조금 낮출 뿐) 경기 수도 정답 방식 이상입니다.
경기 수도 적게 하면서 논리적으로 왜곡을 없애는 방법은, 바로 위 풀이 방식(정답 방식)입니다. 그런데 왜 저 정답 방식이 실제 대회에는 안 쓰일까요?
두 가지 이유를 생각해볼 수 있습니다.
1. 사람들은 '전체 1위가 누구일지'에 가장 관심이 많습니다. 그걸 보고 나면 나머지 순위 결정에 대해서는 관심이 떨어집니다.
보통의 토너먼트 방식으로 하는 월드컵 같은 경우, 3, 4위 결정전을 먼저 하고 1, 2위 결정전을 치를 수 있습니다.
위 풀이 방식대로 하려면 반드시 '전체 1위가 누구일지'부터 밝혀야만 합니다.
2. 보통의 토너먼트 방식에서는, 패배했을 때 아예 탈락인지 금방 알 수 있습니다. 그래서 탈락 선수는 일찍 짐 싸고 경기장을 떠날 수 있습니다.
반면 위 풀이 방식(정답 방식)대로 대회를 하면 1차전에서 패배한 선수 입장에서 '나를 이긴 선수'가 전체 1위를 하느냐 마느냐'에 따라 자신이 2, 3위 결정전에 진출할 수 있는지가 판가름됩니다. 그래서 1위 결정전 결과가 나올 때까지 기다려야 합니다. 경기장 근처에서 좀 오래 체류해야 할 수 있습니다.
하나 덧붙여보면, 정답 방식이 왜 논리적으로 옳은지 관중들이 이해하지 못할 수도 있기 때문이기도 한 것 같습니다.
정답 방식이 좀 실제 대회에서 채택되면 좋겠습니다 저는. 대회에 나오는 선수들은 최선을 다해 실력을 갈고 닦아 겨뤄보려고 할 텐데, 운 때문에 순위 판정에 왜곡이 크게 생길 수 있으니 얼마나 허탈합니까.
'나를 이긴 선수가 1위를 하느냐 마느냐'에 따라 자신이 2, 3위 결정전에 진출할 수 있을지가 결정되면, 패배 팀이 자연스럽게 승리 팀을 응원하는 보다 우호적인 모습도 보게 될 것입니다.
※ 이 글에서는 '경기하는 조'와 '성적 매겨지는 조'를 하나로 묶어 본 것입니다. 구분을 하는 경기 대회도 있는데 원리는 같습니다.
