'슬기로운 감빵생활', 죄수들에 관한 정수론 문제

(사진 출처 : 트라이버튼, https://www.tributton.com/problem)

7월 10일날 방송한 문제적 남자 163회에서는 다음과 같은 죄수문제가 나왔다.

 뇌섹 교도소 교도관이 죄수들에게 제안했다.

"내일 너희 중 100명을 직접 골라서 불러낼 것이다. 100명 중 한 번호가 다른 번호의 배수가 되는 경우가 존재한다면 모두 석방할 것이고, 그렇지 않다면 앞으로 석방은 없다."

 똑똑한 죄수들은 이 말에 전혀 동요하지 않다가 새로운 죄수의 입소 소식을 듣고 모두 좌절했다. 몇 번째 죄수가 입소한 것일까?

조건 1) 죄수들은 입소한 순서대로 1번, 2번순으로 번호를 받는다.

조건 2) 죄수들은 감옥에 입소한 죄수가 몇 명인지 알고 있다.

 이 문제에 대한 장원의 해설은 다음과 같았다.

"1에서부터 200, 뭐 이정도까지 있다고 생각해보면, 답은 199나 200이나 201중 하나라고 제가 지금 계속 헷갈려하고 있거든요.

 200명이 있다고 해봐요, 그러면 여기서 큰 숫자들을 고르면 101번부터 200번까지 고르겠죠. 여기는 지금 배수가 없어요. 1에서부터 199까지 있다고 하면 100에서부터 199까지. 여기도 배수가 없어요. 근데 1에서부터 198까지 있다고 하면 큰 숫자들만 고르면 99에서부터 198까지 있잖아요, 여긴 배수가 있어요. 그죠?

 그러면 1에서부터 198까진 어떤 조합을 해도 배수가 존재한다고 볼 수 있어요, 그쵸?

 '제일 큰 숫자들만 골랐을 때 배수가 존재할 확률이 재일 적다'라는 전제가 참이라면 198명일 때는 모두가 안심을 한다. 근데 199명이 들어오면, 그래서 큰 숫자들만 골랐을 때 100에서 부터 199번까지 고르게 됐을 때 배수가 존재하지 않게 된다면 사람들은 좌절하겠죠. 사색이 되겠죠.

 새로 입소한 죄수는 199번입니다."

 제작진은 이를 정답으로 인정하며 자막으로 퍼펙트 answer라고 띄었지만, 아무리 생각해도 마음에 걸리는 구석이 있다.

 장원의 논리는 그 스스로가 말했듯 '제일 큰 숫자들만 골랐을 때 배수가 존재할 확률이 재일 적다'라는 전제가 참일때만 성립한다. 그러나 그 전제가 어떻게 참이 될 수 있는지 궁금하다. 예를 들어 소수(prime number)와 그 근처 숫자들을 모으면 어떤가?, 혹은 13,16,19, 23, 26, 29, ...와 같이 369로 끝나는 10이상 숫자들을 적절히 선택하는 건 또 어떤가? 이런 각각의 경우들보다 제일 큰 숫자들만 고르는 경우가 배수가 존재할 확률이 적다고 이야기하는 것은 무리가 있다고 본다.(그렇기에 장원 스스로도 '전제가 참이라면'이라는 말을 덧붙인 게 아닐까?)

 이번 글에서는 이 문제의 상세한 풀이, 즉 

1) 1~199번이 있을 경우 배수가 없는 조합이 존재한다.

2) 1~198번이 있을 경우 모든 100명 조합에서 어떤 숫자가 다른 숫자의 배수가 되는 경우가 존재한다.

위 두 명제를 증명할 것이다.

 1)은 장원의 접근이 맞으므로 그대로 가지만, 2)에서는 방송으로 설명되지 않은 '비둘기집의 원리'(?!)를 이용할 것이다.

풀이

먼저

1) 1~199번이 있을 경우 배수가 없는 조합이 존재한다.

을 증명한다.

 구체적으로 100에서 199까지 100명을 선택한다. 한 숫자가 다른 숫자의 배수가 되려면 아무리 적어도 최소 두 배는 되야한다. 그런데 제일 작은 숫자인 100을 두 배로 만들어도 200이 되서 199를 넘어선다. 따라서 100~199는 배수가 없는 반례가 된다.

다음 

2) 1~198번이 있을 경우 모든 100명 조합에서 어떤 숫자가 다른 숫자의 배수가 되는 경우가 존재한다.

을 증명한다.

 99개의 방이 있고, 1~198번까지 이 방들에 집어 넣는다고 생각하자. 여기서 어떤 교도관의 재치로 인해 특정 방에서 아무 두 명을 뽑아도 하나가 다른 하나의 배수가 되게끔 만들었다고 전제하자. 예를들어 (1,3,9,27), (2,4,8), (13,65,130), (5,10,20,100), ... 와 같이 방배정이 되었다고 생각하자.

 전제가 참이라면 비둘기 집의 원리에 의해 100명을 뽑았을 때 같은 방에서 뽑히는 두 명이 있고, 이들은 반드시 배수 관계가 성립하므로 2)가 참이 된다. 결국 남은 건 전제가 정말로 참이 될 수 있느냐는 것이다. 실제로 그런 경우를 만듦으로서 증명을 끝내고자 한다.

 정수의 소인수분해 성질에 의해 모든 숫자는 (2^k)×홀수 꼴이 된다(k는 0 이상의 정수). 예를 들어

8=(2^3)×1

9=(2^0)×9

10=(2^1)×5

11=(2^0)×11

12=(2^2)×3

과 같이 말이다.

 이제 99개의 방에 1, 3, 5, 7, ... , 197번이라고 이름붙이고 각 죄수들은 자기 번호를 소인수분해 했을 때 나오는 홀수대로 방에 들어간다. 예를 들어

8=(2^3)×1  -> 1번방 입장

9=(2^0)×9  -> 9번방 입장

10=(2^1)×5 -> 5번방 입장

11=(2^0)×11 -> 11번방 입장

12=(2^2)×3  -> 3번방 입장

과 같이 방에 들어간다. 1번 방 같은 경우 매우 미어 터지고(1,2,4,8,...) 197번 방은 197번 혼자 들어가 매우 한산할 것이다.

 아무튼 이렇게 방에 들어가면 소기의 목적을 달성하게 된다. 예를 들어 어떤 홀수 방 n에서 두 숫자 (2^j)×n과 (2×k)×n이 뽑혔다고 하자. 적당히 j<k면 (2^j)×n에 2^(k-j)배 하면 (2×k)×n이 된다.

 실제로 전제를 만족시키는 구성을 찾았으므로 2)가 증명된다.

 유명한 문제이므로 여러 조합론 서적에 예제나 연습문제로 나오는데, 이번에도 Kenneth H. Rosen의 'Discrete mathematics and Its Applications'(sixth edition)을 참고한다. 문제는 책 5.2절의 11번 예제로 나온다.