알티수학 쌤 수학 노트 센텀 알티수학 학원 · 부산 센텀 · 해운대

KJMO 2026년 시행 8회 가형 12번 - 가십 문제(gossip problem) 알티수학 쌤 해설, 아마도 모범답안

이 글에서는 올해 2026년 8월에 치러진 KJMO(한국주니어수학올림피아드) 8회 시험의 가형 12번, 로봇 다섯 대가 통신으로 파일을 주고받아서 모두가 파일 전체를 갖게 되는 최소 횟수를 구하는 문제를 살펴보겠습니다. 이 문제는 1970년대 초에 수학자들 사이에서 유행했었던 가십 문제(gossip problem)라는 건데 한번 살펴보겠습니다.

문제는 아래와 같습니다.

2026년 시행 KJMO 8회 가형 12번 (대한수학회, 2026년 8월 시행)

2026년 시행 KJMO 8회 가형 12번 (대한수학회, 2026년 8월 시행)

Part 1. 풀이

1. 통신 한 번의 결과

다섯 로봇을 A, B, C, D, E 라 하고, 각 로봇이 처음에 가진 파일을 차례로 a, b, c, d, e 라 하겠습니다.

통신을 하면 두 로봇이 서로 상대의 파일을 모두 복사하므로, 통신이 끝났을 때 두 로봇이 가진 파일은 똑같습니다. 예를 들어 A 와 B 가 통신하면 둘 다 a, b 를 갖게 되고, 이어서 B 와 C 가 통신하면 B 와 C 는 둘 다 a, b, c 를 갖게 됩니다. 이 때, A 는 두 번째 통신에 참여하지 않았으므로 여전히 a, b 만 갖고 있게 되죠.

이 과정을 아래와 같이 그림으로 나타내 보겠습니다. 가로줄이 로봇이고 세로선이 통신인데, 통신은 왼쪽부터 차례로 일어난 것입니다. 세로선의 양 끝에는 통신이 끝난 뒤에 두 로봇이 갖게 된 파일을 적었습니다. (ab 는 파일 a, b 를 가졌다는 뜻입니다.)

통신 도표, ① A 와 B 가 통신한 뒤 ② B 와 C 가 통신하면 B, C 는 a, b, c 를 갖고 A 는 a, b 그대로다

통신 도표, ① A 와 B 가 통신한 뒤 ② B 와 C 가 통신하면 B, C 는 a, b, c 를 갖고 A 는 a, b 그대로다

2. 한 로봇에 모으는 방법

가장 먼저 떠오르는 방법은 파일을 로봇 한 대에 다 모은 다음에 다시 나눠 주는 것입니다.

A 가 B, C, D, E 와 차례로 통신하면 A 에 파일이 하나씩 쌓여서 네 번째 통신에서 A 가 전체를 갖게 됩니다. 이때 마지막으로 통신한 E 도 A 와 같은 파일을 가지므로 전체를 갖습니다. 남은 B, C, D 는 A 와 한 번씩 더 통신하면 되므로, 모두 4 + 3 = 7 번입니다.

A 에 모은 뒤 나눠 주는 방법 7번, 빨간색이 파일 전체를 가진 것

A 에 모은 뒤 나눠 주는 방법 7번, 빨간색이 파일 전체를 가진 것

그래서 이 문제의 답은 7보다 작거나 같습니다.

이제 7회 보다 줄일 수 있는 방법을 고안해 봅시다.

3. 6번에 끝내는 방법

위의 방법에서 ⑤, ⑥, ⑦ 번째 통신을 보면 통신 한 번에 전체를 가진 로봇이 한 대씩만 늘어납니다. 전체를 가진 A 가 상대에게 건네주기만 하기 때문이죠.

그런데 통신은 두 로봇이 서로 주고받는 것이므로, 통신하는 두 로봇의 파일을 합쳤을 때 전체가 된다면 두 대가 동시에 전체를 갖게 됩니다. 이런 통신을 만들면 횟수를 줄일 수 있을것 같다는 생각이 듭니다.

로봇이 A, B, C, D 네 대뿐이라고 하고 먼저 해보겠습니다. A 와 B, C 와 D 가 각각 통신하면 A, B 는 a, b 를 갖고 C, D 는 c, d 를 갖습니다. 이제 A 와 C 가 통신하면 두 로봇의 파일을 합친 것이 a, b, c, d 라서 A, C 가 동시에 전체를 갖고, B 와 D 가 통신해도 마찬가지로 B, D 가 동시에 전체를 갖습니다. 따라서, 네 대일 때는 4번이면 됩니다.

로봇이 네 대일 때 4번에 끝내는 방법, ③ 과 ④ 에서 두 대씩 동시에 전체를 갖는다

로봇이 네 대일 때 4번에 끝내는 방법, ③ 과 ④ 에서 두 대씩 동시에 전체를 갖는다

이제 다섯째 로봇 E 를 넣어 보겠습니다. E 가 맨 처음에 A 와 통신해서 파일 e 를 A 에게 넘겨 두면, 그 뒤로는 A 가 a 와 e 를 같이 갖고 통신하게 됩니다. 그래서 위의 네 대의 통신 4번이 끝나면 A, B, C, D 는 e 까지 포함해서 전체를 갖게 되고, 마지막에 E 가 A 와 한 번 더 통신하면 E 도 전체를 갖습니다.

다섯 대일 때 6번에 끝내는 방법, ① 에서 E 의 파일을 A 에게 넘기고 ⑥ 에서 E 가 전체를 받는다

다섯 대일 때 6번에 끝내는 방법, ① 에서 E 의 파일을 A 에게 넘기고 ⑥ 에서 E 가 전체를 받는다

따라서 1 + 4 + 1 = 6 번으로 가능합니다.

그래서 이제 이 문제의 답은 6보다 작거나 같습니다.

더 줄일 수 있을지 고민해보면...

여러가지 시도를 해봐도 잘 안됩니다.

그러면 이제 태세전환을 해서 답이 6이라는 증명을 해봐야 되겠죠. (쉽지 않습니다.)

시험에서는 이렇게 엄밀하게 하지 않아도 적절히 노가다 쳐보고 6회를 발견했다면 그냥 적고 나오는게 좋겠네요.

4. 5번으로 안 되는 이유

모든 로봇이 전체를 갖게 되는 통신 순서가 있다고 하면, 그 안에는 전체를 가진 로봇이 처음으로 생기는 통신이 있습니다. 이 통신을 기준으로 앞과 뒤로 나눠서 통신이 적어도 몇 번 필요한지 세어 보겠습니다.

먼저 그 통신이 빨라야 몇 번째인지 생각해 보겠습니다. 한 번이라도 통신으로 이어진적이 있는 로봇끼리를 한 묶음이라고 하겠습니다. 직접 통신하지 않았더라도 다른 로봇을 거쳐서 이어져 있으면 같은 묶음입니다. 파일은 통신으로만 옮겨지므로, 로봇이 가진 파일은 모두 자기와 같은 묶음에 있는 로봇의 것입니다. 통신을 3번 한 뒤의 묶음을 두 가지 예로 그려보면 아래와 같습니다.

통신 3번 뒤의 묶음의 예 두 가지, 어느 쪽도 묶음이 2개다

통신 3번 뒤의 묶음의 예 두 가지, 어느 쪽도 묶음이 2개다

최초 상태에는 다섯 대가 따로따로라서 묶음이 5개입니다. 통신 한 번은 서로 다른 두 묶음을 하나로 합치거나, 같은 묶음 안에서 일어나서 묶음의 수를 그대로 두거나 둘 중 하나이므로, 묶음의 수는 통신 한 번에 많아야 1개 줄어듭니다. 어떤 로봇이 다섯 파일을 다 가지려면 다섯 대가 한 묶음이어야 하는데, 묶음 5개가 1개로 되려면 통신이 4번 이상 필요합니다. 즉, 3번째 통신까지는 전체를 가진 로봇이 없고, 전체를 가진 로봇은 빨라야 4번째 통신에서 처음 생깁니다.

다음으로 그 통신 뒤에 적어도 몇 번이 더 필요한지 생각해 보겠습니다. 1에서 본 것처럼 통신이 끝나면 두 로봇의 파일이 같으므로, 전체를 가진 로봇이 처음 생기는 통신에서는 통신한 두 대가 동시에 전체를 갖게 됩니다. 그러면 나머지 세 대는 아직 전체를 갖지 못한 상태입니다. 로봇의 파일은 자기가 통신할 때만 늘어나므로 이 세 대는 각각 그 뒤에 한 번 이상 통신해야 하는데, 통신 한 번에 참여하는 로봇은 두 대뿐이라서 세 대가 모두 통신하려면 2번 이상이 필요합니다.

통신 횟수 세기, 전체를 가진 로봇은 빨라야 ④ 에서 처음 생기고 그 뒤로 2번 이상 더 필요하다

통신 횟수 세기, 전체를 가진 로봇은 빨라야 ④ 에서 처음 생기고 그 뒤로 2번 이상 더 필요하다

따라서 통신은 적어도

4+2=6\textcolor{#ff0010}{4+2=6}

번이 필요합니다. 그리고, 3에서 6번 이하 임을 보였었죠. 그러므로 이 두 가지를 종합하면 최소 횟수는 6번입니다.

즉, 답은 6 입니다.

Part 2. 더 생각해보기

5. 가십 문제

제가 조합 문제에 오랫동안 관심이 많은 편이라 관련 썰을 좀 더 풀어드리겠습니다~

이 문제에서 로봇을 사람으로, 파일을 소문으로, 통신을 전화 통화로 바꾸면 조합수학(combinatorics)에서 가십 문제(gossip problem) 또는 전화 문제(telephone problem)라고 하는 유명한 문제가 됩니다. 원래 문제는 아래와 같습니다.

「n 명의 부인이 저마다 다른 사람은 모르는 소문을 하나씩 알고 있다. 두 사람이 전화 통화를 할 때마다 그때까지 알고 있는 소문을 서로 전부 알려 준다. 모두가 모든 소문을 알게 되려면 통화가 몇 번 필요한가?」

당시 논문들에 따르면, 이 문제는 A. 보이드(A. Boyd)라는 사람이 낸 것이고 1970년대 초에 수학자들 사이에서 한동안 이슈가 되었었다고 합니다. 1971년과 1972년에 테이데만(Tijdeman), 베이커와 쇼스탁(Baker, Shostak), 허이널과 밀너와 세메레디(Hajnal, Milner, Szemerédi)가 서로 다른 방법으로 풀어서 각각 논문으로 발표했는데, 그중 세 사람이 함께 쓴 논문의 제목은 「전화 병의 치료법(A cure for the telephone disease)」입니다.

일반적인 정답은 사람이 1명, 2명, 3명일 때 각각 0번, 1번, 3번이고, 4명 이상일 때는

2n−4(n≥4)\textcolor{#ff0010}{2n-4}\quad \left(n\ge 4\right)

번입니다. n = 5 를 넣으면 6 이고, 이것이 이 문제의 답이죠.

가십 문제의 답, 사람이 4명 이상이면 2n − 4 번이고 빨간 칸이 이 문제

가십 문제의 답, 사람이 4명 이상이면 2n − 4 번이고 빨간 칸이 이 문제

6. 로봇이 n 대일 때의 방법

2n − 4 번에 끝내는 방법은 3의 방법을 그대로 늘리면 됩니다. 3에서 E 가 A 와 맨 처음과 맨 마지막에 한 번씩 통신했는데, 로봇이 더 있으면 그 로봇들도 똑같이 하면 됩니다. 처음에 나머지 로봇들이 차례로 A 와 통신해서 파일을 A 에게 넘기고, 가운데에서 A, B, C, D 가 4번 통신하고, 마지막에 나머지 로봇들이 A 와 다시 한 번씩 통신합니다.

로봇을 점으로, 통신을 선으로 그리면 아래 그림과 같습니다. 선 옆의 수는 통신의 차례입니다.

2n − 4 번에 끝내는 방법, 왼쪽은 로봇 5대(6번)이고 오른쪽은 로봇 7대(10번)

2n − 4 번에 끝내는 방법, 왼쪽은 로봇 5대(6번)이고 오른쪽은 로봇 7대(10번)

A, B, C, D 를 뺀 나머지 로봇은 n − 4 대이고 한 대마다 통신을 2번씩 하므로, 통신 횟수는

4+2(n−4)=2n−44+2\left(n-4\right)=2n-4

입니다. 로봇이 한 대 늘 때마다 통신은 2번씩 늘어나는 셈이죠.

7. 로봇이 6대일 때

2n − 4 번이 최소라는 것도 4처럼 알 수 있을까요? 4의 방법을 로봇 n 대에 그대로 적용해 보겠습니다.

전체를 가진 로봇은 묶음 n 개가 1개로 되는 n − 1 번째 통신 이후에야 처음 생깁니다. 그때 남은 n − 2 대가 각각 한 번 이상 통신해야 하므로, 그 뒤로 (n − 2) ÷ 2 번 이상(나누어떨어지지 않으면 올림)이 더 필요합니다. 이렇게 센 횟수와 실제 최소 횟수 2n − 4 를 비교하면 아래와 같습니다.

Part 1 의 방법으로 센 횟수와 실제 최소 횟수의 비교, 로봇이 5대일 때까지만 같다

Part 1 의 방법으로 센 횟수와 실제 최소 횟수의 비교, 로봇이 5대일 때까지만 같다

로봇이 4대, 5대일 때는 두 값이 같아서 4의 방법으로 최소임을 알 수 있습니다. 하지만 6대일 때는 5 + 2 = 7 번 이상이라는 것까지만 알 수 있고, 실제 최소 횟수는 8번입니다. 4에서는 전체를 가진 로봇이 처음 생긴 뒤로 통신 한 번에 두 대씩 전체를 갖게 되는 경우까지 넣어서 센 것인데, 로봇이 6대 이상이면 계속 그렇게 될 수는 없다는 뜻입니다.

허이널과 밀너와 세메레디의 논문은 이 부분을 다음과 같은 사실로 해결했습니다. 통화를 n − 4 + k 번 했을 때 모든 소문을 아는 사람은 많아야 k 명이라는 것입니다. n 명이 모두 알려면 k 가 n 이상이어야 하므로 통화는 n − 4 + n = 2n − 4 번 이상 필요합니다. 로봇 5대에 적용하면 통신 5번 뒤에 전체를 가진 로봇은 많아야 4대이고, 6번을 해야 5대가 될 수 있습니다.

이 사실의 증명은 통화의 순서를 바꿔 가면서 따지는 수학적 귀납법인데, 과정이 길고 복잡해서 여기에 담지는 않겠습니다.

8. 한쪽으로만 보내는 통신 (변형 문제)

이 문제의 통신은 두 로봇이 서로의 파일을 복사합니다. 만약 편지처럼 한 로봇이 다른 로봇에게 보내기만 한다면 몇 번이 필요할까요?

앞의 2처럼 A 에게 모았다가 나눠 주면 B, C, D, E 가 A 에게 보내는 4번과 A 가 B, C, D, E 에게 보내는 4번을 합쳐서 8번입니다.

한쪽으로만 보내는 통신 8번, 화살표가 보내는 방향이고 받는 로봇의 파일만 늘어난다

한쪽으로만 보내는 통신 8번, 화살표가 보내는 방향이고 받는 로봇의 파일만 늘어난다

이 경우에는 4의 방법만으로 8번이 최소라는 것을 알 수 있습니다. 전체를 가진 로봇은 이번에도 빨라야 4번째 통신에서 처음 생기는데, 이번에는 받는 쪽 한 대만 전체를 갖게 됩니다. 남은 네 대가 각각 한 번 이상 받아야 하고 통신 한 번에 받는 로봇은 한 대뿐이라서 4번 이상이 더 필요하고, 모두 4 + 4 = 8 번 이상입니다. 로봇이 n 대이면 같은 방법으로 (n − 1) + (n − 1) = 2n − 2 번이 최소입니다.

테이데만은 1971년 논문에서 편지로도 2n − 2 통이면 되는 일이 전화로 2n − 4 번이나 걸리는 것은 꽤 낭비로 보인다고 적었습니다. 한쪽으로만 보내던 것을 서로 주고받는 통신으로 바꿔도, 줄어드는 횟수는 로봇이 4대 이상이면 몇 대이든 2번뿐이라는 것이 신기한 사실이죠.

https://blog.naver.com/rtmath-/224452723074

KJMO 2026년 시행 8회 가형 12번 - 가십 문제(gossip problem) 알티수학 쌤 해설, 아마도 모범답안 — 썸네일

#KJMO #한국주니어수학올림피아드 #KJMO기출 #KJMO2026 #가십문제 #전화문제 #gossipproblem #조합수학 #수학적귀납법 #아마도모범답안