수리논술, 배움에서 논증의 완성까지.문제
어느 부부가 아홉 쌍의 부부를 집으로 초대하여 파티를 열었다. 이 자리에 모인 열 쌍의 부부는 서로 아는 사이도 있고, 처음 만나는 사이도 있다. 이들 가운데 서로 알던 사람들은 악수를 하지 않았지만, 처음 만나는 사람들은 정중하게 악수를 한번씩 나누었다. 저녁 식사가 끝나고 집 주인은 그 자리에 모인 19명(집 주인의 부인과 손님들)에게 오늘 모임에서 악수를 몇 번 하였는지 질문하였다. 놀랍게도 이들이 악수한 회수는 모두 달랐다. 이 때 집 주인의 부인은 악수를 몇 번이나 하였을지 생각해보고, 부인이 악수한 횟수를 일반화하여 설명하시오.
해설 강의
수리논술 초기 문항이라 배점과 소요 시간이 정해진 적 없어, 채점 기준을 붙이지 않음.
한 사람이 악수할 수 있는 최대 횟수는 자기 자신과 배우자를 제외한 번이고, 최소는 번이다. 집 주인을 제외한 명의 답이 모두 다르므로 악수한 횟수는 회부터 회까지 골고루 있음을 알 수 있다.
이라고 답한 사람을 , 의 배우자를 라 하면, 는 자기 자신과 를 제외한 명 전원과 악수했다. 따라서 를 제외한 모든 사람은 적어도 한 번 악수했으므로, 회라고 답한 사람이 이다. 이때 집 주인의 부인은 와 가 될 수 없다.
와 를 파티에서 빼면, 남은 명은 모두 와 한 번 악수했고, 와는 악수하지 않았으므로, 각각의 악수 횟수가 정확히 회씩 줄어든다. 그럼 집 주인을 제외한 명의 답은 회부터 회가 되어 여전히 모두 다르다. 이는 집 주인 부부가 여덟 쌍을 초대한 것과 같은 상황이다. 같은 과정을 반복하면 한 번에 한 쌍씩 빠지고, 번 반복하면 집 주인의 부인만 남는다. 따라서 집 주인의 부인이 악수한 횟수는 회이다.
일반적으로 쌍을 초대하여 파티를 열면, 집 주인의 부인은 회 악수를 한다.
TMI. 악수 보조정리(handshaking lemma)각자 악수한 횟수를 모두 더하면 악수한 총 횟수의 2배이다. 오일러가 1736년 쾨니히스베르크 다리 논문에 이미 적어둔 것.
Comment. 서울대에서 수리논술이 입시에 도입될 때 제시한 문항이지만, 정작 이 문제를 누가 처음 만들었는지는 모른다. 문헌으로 확인되는 가장 이른 등장은 1973년 5월 「사이언티픽 아메리칸」에 실린 마틴 가드너의 칼럼이다. 오일러의 악수 보조정리(handshaking lemma)에 가드너가 부부 동반 파티라는 이야기를 얹은 셈이다. 가드너보다 앞선 출처는 아직 아무도 찾지 못했다. 퍼즐의 출처를 꼼꼼히 밝히기로 유명한 피터 윙클러조차 자기 책(2004)에 이 문제의 출처를 "구전(word-of-mouth)"이라고만 적었고, 본문에서는 "아주 오래된 단골 문제"라고 불렀다.