18번째 문제는

KPP 멤버 '한동규' 님이 만든 문제입니다

세계적인 악당 ‘타노시’를 잡기 위해 국가 정보 요원 13명이 모였다. 요원들은 이번 미션의 통신 수단으로 ‘샵메시지’를 사용하기로 했다. 국가에서 만든 채팅 앱 ‘샵메시지’는 세계 최고 수준의 보안을 자랑하는데, 기술적인 한계로 한 채팅방에 최대 4명까지만 들어갈 수 있다.

조건 

두 요원이 직접 소통하기 위해서는 같은 채팅방에 속해 있어야 한다.

예를 들어 A, B, C가 속한 채팅방이 있다면 A와 B, A와 C, B와 C는 서로 직접 소통이 가능하다.

문제 어떤 두 요원끼리도 직접 소통할 수 있으려면 채팅방은 최소 몇 개여야 할까?

각 채팅방에 어떤 요원들이 속해야 하는지도 구해보자!

<주의 사항>

정답과 풀이는 비밀 댓글로 부탁드려요!

이름, 주소, 연락처를 함께 남겨주세요!

당첨자는 수학동아 7월호에 공개합니다!

풀이는 6월 25일 이후 이 게시물에서 확인하세요!

*KPP (Korean Puzzle Party)는 '퍼즐을 좋아하는 사람들의 모임'으로 퍼즐을 모으는 사람, 퍼즐을 만드는 사람, 퍼즐을 푸는 사람들이 모여 직접 만들고 수집한 퍼즐을 함께 풀어보며 이야기를 나눈다. 현재 두 달에 한 번 서울에서 정기적인 모임을 갖고 있으며, 퍼즐을 푸는 것뿐 아니라 퍼즐 관련 행사에 참여하거나 박물관에 다녀오는 등 다양한 활동을 하고 있다. 

스크롤 주의!

아래 정답이 있습니다!

.

.

.

.

정답과 해설

어떤 두 요원이 동시에 속한 채팅방의 수를 두 요원 사이의 '연결'이라고 하자. 예를 들어 요원1이 채팅방 A, B, C에 속하고 요원 2가 채팅방 A, C, D에 속했다면, 요원1, 2는 채팅방 A와 C에 공통으로 속해있으므로 두 요원 사이의 연결은 2다. 또, 두 요원 사이의 연결이 1 이상이면 두 요원은 '연결돼 있다'라고 하자. 13명의 요원은 서로 연결돼 있어야 하므로 연결의 총 개수는 이상이다. 한편 채팅방 하나당 만들어지는 연결의 수는 이고, 여기에 채팅방의 수를 곱하면 연결의 총 개수가 나온다. 따라서 채팅방은 최소 개가 있어야 한다. 13개의 채팅방으로 모든 요원이 연결돼 있으려면, 어떤 두 요원을 골라도 둘 사이의 연결이 1이어야 한다. 2 이상의 연결을 가진 두 요원이 있다고 가정하면 연결의 총 개수가 78을 넘지만, 채팅방 13개로는 총 6×13=78개의 연결밖에 만들 수 없기 때문이다. 이 조건을 만족하는 채팅방 목록을 직접 찾으면 위와 같은 그림이 나온다. 각각의 점을 요원으로 생각하고, 네 개의 점을 잇는 각각의 선을 채팅방으로 생각하자.

한 걸음 나아가기!  

물론 채팅방 목록을 직접 찾는 대신 수학적으로 접근할 수도 있다. 조합론에서 다루는 주제 중 하나로 '블록 설계'라는 것이 있다. 전체 집합에서 특정 조건을 만족하도록 같은 크기의 부분 집합의 모임을 찾는 문제이다. 이 부분 집합들을 '블록'이라고 부른다. 이번 문제의 경우 13명의 요원을 전체 집합으로 본다면, 채팅방은 크기가 4인 블록에 대응된다. 여기에 임의의 두 원소(요원)을 모두 포함하는 블록(채팅방)이 정확히 하나라는 조건이 붙는다. 이 조건들은 블록 설계의 한 종류인 슈타이너 시스템(Steiner system)의 조건과 일치한다. 전체 집합의 크기가 n이고 블록의 크기가 k이며, 임의의 t개 원소를 모두 포함하는 블록이 항상 하나가 되도록 하는 블록 설계를 슈타이너 시스템 S(t, k, n) 이라고 표기한다. 이번 문제는 S(2, 4, 13) 으로 표기할 수 있다. 알려진 슈타이너 시스템으로는 사영 평면(projective plane)과 아핀 평면(affine plane) 등이 있다. 차수가 q인 사영 평면은 S(2, q+1, q²+q+1) 에 해당되고, 따라서 S(2, 4, 13) 은 차수가 3인 사영 평면으로 표현할 수 있다. (3은 소수이므로 사영 평면의 차수가 될 수 있다.) 위 그림은 사실 차수가 3인 사영 평면을 시각화한 그림인 것이다.  

-끝-