우연히 모인 파티의 법칙

 파티에는 참 많은 사람들이 온다. 가장 잘 생각할 수 있는 것이 결혼식. 외국이고 우리나라고 할 것 없이 결혼식만 되면 아는 사람 모르는 사람 전부 와서 신랑신부 두 사람의 영원할 행복을 축하해준다. 어쩌면 그런 의미에서 파티(party) 에는 사교모임이라는 뜻에 단체, 동아리라는 뜻도 있는 듯 하다.

 

 여기 어떤 일로 몇명의 사람들이 모였다고 하자. 개중에는 아는 사람도 있고 모르는 사람도 있을 것이다. 애매한 구석을 없애기 위해, 내가 알면 상대방도 나를 알아서 우리는 친구인거고, 내가 모르면 상대방와 나는 완전히 남남이라고 하자. 그렇다면 그 파티에는 각자 일종의 친구수를 가지게 된다. 이제 이야기가 재미있어진다. 놀랍게도, 그 어떤 파티에도 친구수가 똑같은 그런 두 사람을 늘 찾을 수 있다고 한다. 어떻게 그럴 수 있을까?

 

해설

 생일 역설에서도 그렇지만, 사람들은 파티에 모인 많은 사람들이 죄다 골고루 다른 특성을 가진다고 믿는다. 하지만 실제로 사람들을 만나서 이야기해보면 자신과 비슷한 특성을 의외로 적잖은 사람들이 공유한다는 것을 알 수 있다. 가령 혈액형을 보면 4명만 만나도 나와 같은 혈액형을 가진 사람을 평균적으로 1명정도 만날 수 있다. 즉 골고루 다르기가 확률적으로 더 힘든 상황인 것이다.

 

 이제 파티에서의 친구 이야기로 가보자. 우선 친구수는 그 사람이 파티인원 전원을 알 때 최대가 된다. 최소인 경우는 파티인원을 아무도 모를 때 이다. 총 인원을 n명이라고 하면 친구수는 최소 0에서 최대 n-1이다. (자기 자신은 제외하므로 n-1이 된다.) 잘 살펴보면, 가능한 친구수는 총 n개로, 파티의 총 인원수과 똑같다.  따라서 모든 사람이 친구수가 다르다고 한다면, 각자 친구수가 0명에서 n-1명까지 골고수 배치됬다는 뜻이다.

 

 이제 모순이 발생한다. 친구수가 n-1인 사람이 있다는 얘기는 이 사람이 파티에 있는 사람 전원을 안다는 이야기이므로, 친구수가 0명인 신참은 존재할 수 없다. 따라서 친구수가 전부 다른 상황은 일어날 수 없다. (반대로도 모순을 설명할 수 있다. 친구수가 0인 사람이 있으면, 그 사람은 모두에게 낯선 사람이기 때문에 파티에 있는 사람 전원을 아는 사람은 있을 수 없다. 고로 모순이 일어난다.)

 

 

 

(증명에는 귀납법이 쓰였다.)