유니폼 색깔 문제

여러 팀이 운동 경기를 하여 우승자를 가리는 대회에서 대진표를 작성할 때, 리그 방식과 토너먼트 방식이 많이 쓰인다. 예를 들어 이번 2010년 남아공 월드컵 본선에서는 조별 리그로 16강을 가리고, 16개 팀이 토너먼트 방식으로 경기를 치러 최종 우승자를 가렸다.

토너먼트 방식에서의 유니폼 선택

경기할 때는 상대방의 유니폼과 색깔 등이 비슷하지 않도록 입는 게 일반적이다. 대한민국이나 스페인이나 빨간색 유니폼만 입기를 고집한다면, 두 팀이 경기할 경우 혼란이 발생하기 때문이다. 그런데 유니폼의 색깔을 고르는 것에도 의외로 재미있는(?) 수학이 숨어 있어 소개하려고 한다.이 글에서는 토너먼트 방식의 경기에서 아래와 같은 상황이 주어진 경우만 생각해보자.

가. 모든 팀은 빨강, 초록, 파랑의 세 가지 색깔의 유니폼을 갖고 있다.
나. 경기하는 팀의 유니폼 색깔은 달라야 한다.
다. 토너먼트의 승자는 바로 이전 경기 때 자신의 팀이나, 상대방 팀이 입었던 색깔의 유니폼을 입지 못한다.

예를 들어 한쪽은 빨간색 유니폼을, 상대방은 파란색 유니폼을 입고 경기를 했다면, 승자는 다음 경기에서 반드시 초록색 유니폼을 입어야 한다는 조건을 단 것이다. 이런 조건 하에 다음과 같은 질문을 해보자.

경기 대진표가 어떻게 짜여져도 위 조건을 만족하도록 유니폼 색깔을 정할 수 있을까?

예를 들어 아래와 같이 가장 흔한 16강 대진표에 원하는 조건을 만족하도록 유니폼 색깔을 정해보라. 답은 여러 개 있을 수 있다.

16강전에서 유니폼 색깔을 정하면, 조건 (다) 때문에, 8강전부터는 자동으로 유니폼 색깔이 정해진다. 하지만 처음에 유니폼 색깔을 아무렇게나 무작위로 정했다가는 8강전, 4강전 등에서 유니폼 색깔이 서로 충돌할 수 있으니 애초에 잘 골라야 하는데, 독자 여러분도 연습 삼아 색깔을 정해보길 바란다.

내친김에 전체 팀의 수를 늘리거나 줄여보고, 부전승도 도입한 다른 대진표를 짜서 위의 문제를 풀어보자. 아마 몇 번 해보면 요령이 생길 것이고, 어떤 대진표를 가지고 오더라도 유니폼 색깔을 정할 수 있다는 자신이 생길 것이다. 예를 들어 수학적 귀납법 같은 증명 도구를 이용하면 항상 조건에 맞도록 유니폼 색깔을 정할 수 있음을 ‘증명’할 수도 있는데, 관심 있는 사람은 시도해보길 바란다

유니폼 색깔 정하는 문제 vs. 사색 문제

위와 같은 상황에서 유니폼 색깔을 정하는 문제는 사실 유명한 ‘사색 문제(四色問題, four color problem)’의 특수한 경우다. 사색 문제란, 평면 지도가 주어질 때 인접한 영역은 다른 색으로 칠해 구별해야 한다는 조건 하에 4가지 색만으로 칠할 수 있느냐는 문제를 말한다. 더 자세한 소개는 다음 편으로 미루기로 하고, 뭔가 비슷한 구석은 있어 보이지만 꽤 다른 것 같은 두 문제가 무슨 관련이 있다는 건지 설명해보자.

편의상 평면 지도에 칠하는 네 가지 색깔을 빨강(R), 초록(G), 파랑(B), 하양(W)이라고 부르자. 대진표가 주어지면 (얼기설기 꼬여있는 대진표는 사양한다) 대진표 둘레에 테두리를 그려 넣으면 평면 지도를 하나 만들 수 있다. 예를 들어 아래 그림의 왼쪽처럼 대진표가 주어지면, 테두리를 그려 넣어 오른쪽과 같은 지도를 만들자는 얘기다.

이렇게 만들면, 왼쪽 대진표에서 유니폼 색깔을 정할 때마다 대응하는 오른쪽 ‘지도’를 4색으로 칠할 수 있다. 또한, 역으로 오른쪽 지도를 4색으로 칠하면 대응하는 왼쪽 대진표에 유니폼 색깔을 정해줄 수 있다는 얘기다! 어떻게 한다는 것일까?

예를 들어 대진표에서 유니폼 색깔을 아래 왼쪽 그림처럼 정했다고 하자. 이때, 대응하는 지도에서 각 구역의 색깔은 다음처럼 정한다. 아무 영역이나 하나를 골라 하얀색(W)으로 그냥 칠한다. 예를 들어 위 그림에서 W라고 쓴 영역을 하얀색으로 칠했다고 하자.

그런 뒤 하양과 인접한 영역(위의 그림에서는 1, 2, 3, 4 영역)에는, 두 영역 사이의 경계가 이루는 색깔로 칠한다. 예를 들어 1번 영역과 하얀색 영역의 경계가 파란색이므로, 1번 영역을 파란색으로 칠하자는 얘기다. 마찬가지로 생각하면, 2, 3, 4번 영역에 칠하는 색은 각각 초록, 초록, 빨강임을 알 수 있다.

그렇다면 5, 6번 영역은 어떻게 칠해야 할까? 위에서 1, 2번 영역은 파랑과 초록인데 경계는 빨강임을 알 수 있다. 1, 4번 영역은 파랑과 빨강인데 경계는 초록이다. 3, 4번 영역은 초록과 빨강인데 경계는 파랑이다. 이런 관계를 다른 모든 영역에도 계속 적용하면 된다. 즉, 4번 영역이 빨간색이고, 6번과의 경계가 초록이므로, 6번 영역은 파란색을 칠하면 된다! 그렇다면, 5번 영역은 무슨 색으로 칠해야 할까? 하얀색 주변의 영역을 어떻게 칠했는지 기억한다면, 5번 영역의 색깔은 하얀색이어야 함을 알 수 있다. 그러면 위 오른쪽과 같은 4색 지도를 하나 얻을 수 있다. 말로만 보면 복잡해 보이지만, 다음 표를 보면 인접한 영역 사이의 색깔에 따라 경계를 무슨 색으로 정하자는 것인지 금세 알 수 있을 것이다.

수학책 좀 들여다봤다 하는 독자라면, ‘클라인(Klein)의 4군’, 혹은 ‘공간 좌표에서의 외적’ 같은 것을 떠올릴 수도 있을 것이다.

토너먼트 대진표가 2개인 경우는?

내친김에 토너먼트 대진표가 두 개인 경우는 어떨까 생각해보자. 예를 들어 다음처럼 두 가지 대진표가 나왔는데, 그 중 어느 방식으로 경기를 할지는 정하지 않았다고 하자. 즉, 경기를 하는 팀은 왼쪽부터 차례로 6개 팀이 모두 위치가 결정되어 있는데, 왼쪽 대진표로 경기를 할지, 오른쪽 대진표로 경기를 할지는 추후에 추첨을 하기로 했다고 가정해보자.

이때 둘 중 어느 대진표로 경기를 하든, 모두 적합하도록 미리 유니폼 색깔을 지정할 수 있을까? 예를 들어 왼쪽의 대진표는 위에서도 나왔는데, 앞서 지정했던 색깔대로 옷을 입으면 오른쪽 대진표로 경기를 치를 경우 유니폼 색깔이 충돌이 난다. 그렇다면 과연 두 대진표 모두에 맞도록 유니폼 색깔을 정할 수 있을까? 당연하지만 대진표가 하나인 경우보다는 훨씬 어려운데, 한번쯤은 연습해보라. 한편, 대진표가 세 개인 경우에는 유니폼 배정이 불가능한 경우가 있는데, 어떤 반례가 있는지 찾아보는 것도 좋겠다.

토너먼트 대진표가 2개인 경우 vs. 4색 문제

두 개의 대진표가 어떻게 주어지든 항상 유니폼 색깔을 정할 수 있다는 것 역시 사색 문제의 일부에 해당한다. 위에서처럼 대진표가 주어진 경우, 오른쪽의 대진표를 상하로 뒤집은 다음 왼쪽 대진표 아래에 붙이고, 역시 테두리를 그려 지도를 만들자. 그런 뒤 이 지도를 4색으로 칠해보자. 오른쪽에 예를 하나 들어 놨다. 이제 이 그림으로부터 위에 주어진 두 대진표 모두에 적용할 수 있는 유니폼 색깔을 정하는 것은 아무것도 아니다.

위에서 했던 얘기의 반복에 불과한 것 아니냐며 코웃음을 칠 수도 있겠지만, 사실은 어마어마하게 다르다. 토너먼트 대진표가 두 개인 경우 유니폼 색깔을 정하는 문제는 4색 문제의 일부임에도 불구하고, 이 문제를 독자적으로 해결하면 4색 문제 전체가 풀린다는 것이 증명되어 있기 때문이다! 다음 시간에 보겠지만 4색 문제는 이미 해결이 되어 4색 정리가 돼 있다. 따라서 4색 정리를 이용하면, 대진표가 두 개인 경우의 유니폼 배정 문제를 항상 해결할 수 있다.

문제는 현재까지는 4색 정리를 쓰지 않고 유니폼 배정 문제를 풀지 못한다는 사실이다. 물론 아무렇게나 대진표 두 개 주고 풀라면 4색 정리 없이 무지막지한 노동력을 투입하여 풀 수도 있겠지만, 어떻게 대진표를 주더라도 풀 수 있냐는 게 핵심이다.

대진표가 하나인 경우에는 간단하게 해결할 수 있었는데, 아주 조금 복잡하게 했더니 깊고도 어려운 수학이 깔려 있다니 알다가도 모를 일이다. 어쨌거나, 4색 문제가 뭔지는 알 것 같은데 정확히 모르는 분들은 다음 수학산책을 기다리시길 바란다.

네이버캐스트