다섯 명의 해병

1. 개요2. 문제3. 해답4. 관련 문제 15. 관련 문제 26. 참고 자료

1. 개요

서양에서 전해내려오는 유명한 취미수학문제. 묘하게 같은 행동을 반복하는 것이 특징이다.

2. 문제

해병 5명이 긴 항해 끝에 태평양의 어느 섬에 도착했다. 도착한 해병들은 웬 엄청나게 많은 야자가 쌓여있는 야자무더기와 원숭이 한 마리가 근처를 서성이고 있는 것을 보았다. 그러나 긴 항해로 지쳤던 해병들은 야자에 신경 쓸 겨를 없이 대충 텐트를 치고 잠을 잤다.

그렇게 한참을 자다가 한 명이 일어났다. 그 해병은 야자무더기로 가서 야자들을 다섯 무더기로 나눴는데, 하나가 남길래 그것을 원숭이에게 주었다. 원숭이가 야자를 다 먹자 자기 몫으로 한 무더기를 섬 깊숙한 곳에 감춰둔 다음 다시 텐트로 가서 잠을 잤다.

다음엔 다른 해병이 일어났다. 그 해병도 야자무더기로 가서 남은 야자를 다섯 무더기로 나눴는데, 이번에도 하나가 남아 원숭이에게 주었다. 그리고 자기 몫으로 한 무더기를 감춰두고 텐트로 돌아가 잠을 잤다. 그리고 남은 3명의 해병들도 각각 위의 해병들과 같은 행동을 돌아가면서 했다. 헌데 남은 야자를 다섯 무더기로 나눌 때마다 하나씩 남아 그것을 원숭이에게 주게 되었다.

시간이 흘러 다섯 명의 해병들이 남은 야자무더기 앞에 모였다. 그들은 자기 몫을 챙겼다는 듯 말없이 있었는데, 공정성(?)을 기하기 위해 남은 야자들을 다섯 무더기로 나누어 각자 한 무더기씩 가졌다. 그러나 이상하게도 또 야자 하나가 남아 그것을 원숭이에게 주었다.

처음에 쌓여있던 야자는 최소 몇 개일까?

3. 해답

일견 굉장히 쉬워보이지만 직접 풀어보면 생각만큼 쉬운 문제는 아니라는 사실을 알 수 있다. 물리학자 폴 디랙이 이 문제를 풀었다고 한다.

[ 해답 보기 ]: ||<tablebordercolor=#552582>각자 가진 야자 수를 A, B, C, D, E로 두고 처음 야자 수를 X로 두어 연립방정식으로 계산할수도 있다. 그런데 그냥 계산하기에는 계수가 너무 커져서 한번에 정답을 알기 힘들다는 점이 단점. 그래도 해병들이 같은 행동을 반복하는 것을 역이용해서 계수를 치환해 풀 수는 있다.

초등수학만으로 풀려면 역산을 이용해서 푸는 것이 가장 쉬운 풀이법이다. 얼핏 이렇게 많은 미지수에서 역산이 어떻게 가능하냐고 할 수도 있지만 약간 방법을 복잡하게 하면 역산으로 풀 수 있다. 야자들을 나눈 순서대로 해병들을 A, B, C, D, E로 하고 풀어보자.

일단 마지막에서 5로 나눴을 때 1이 남는 수는 1, 6, 11, 16, 21 ... 순이다. 여기서 해병 E가 다섯 무더기로 나누고 한 무더기로 감췄을 때 남은 무더기는 4개이기 때문에 마지막에 남은 야자는 4의 배수여야 한다. 따라서 해병 E가 야자를 다섯 무더기로 나누고 하나를 원숭이에게 주었을 때 남은 야자를 만족하는 최소 수는 16이 된다.

16에서 시작해서 규칙성을 알아내야 한다. 마찬가지로 4로 나누어떨어지면서 5로 나눴을 때 1이 남는 다음 수는 36이 된다. 이렇게 20씩 증가시켰을 때 조건을 만족하는 수가 된다는 것을 알 수 있다. 16, 36, 56, 76 ...

여기서 해병 E가 야자를 나누기 전의 야자 개수를 알아내려면 해당 수에 5/4를 곱하고 1을 더하면 된다. 따라서 21, 46, 71, 96 ... 의 순으로 증가한다. 이때 이 야자들도 해병 D가 야자를 다섯 무더기로 나누고 한 무더기를 감춘 나머지이기 때문에 4로 나누어떨어져야 한다. 만족하는 최소 수는 96이 되고 그 다음으로 만족하는 수는 196, 296, 396 ... 으로 100씩 증가한다.

이제 여기서 5/4를 곱한다음 1을 더하고, 또 4로 나누어 떨어지는 것을 찾는 것을 계속해서 반복하면 된다.

1. 5/4를 곱하고 1을 더하면 121, 246, 371, 496 ... (해병 D가 나누기 전의 야자 수)
2. 4로 나누어 떨어지는 수는 496, 996, 1496, 1996, ...
3. 5/4를 곱하고 1을 더하면 621, 1246, 1871, 2496, ... (해병 C가 나누기 전의 야자 수)
4. 4로 나누어 떨어지는 수는 2496, 4996, 7496, 9996, ...
5. 5/4를 곱하고 1을 더하면 3121, 6246, 9371, 12496, ... (해병 B가 나누기 전의 야자 수)
6. 4로 나누어 떨어지는 수는 12496, 24996, 37496, 49996, ...
7. 5/4를 곱하고 1을 더하면 15621, 31246, 46871, 62496, ... (해병 A가 나누기 전의 야자 수)

즉, 15621이 해병 A가 나누기 전의 최초 야자수에서 조건을 만족하는 최소의 개수라는 것을 알 수 있다. 따라서 정답은 무려 15621개. 여담으로 A가 가진 야자 수는 4147개, B가 가진 야자 수는 3522개, C는 3022개, D는 2622개, E는 2302개이다.(원숭이가 먹은 야자는 6개) ~~일찍 일어나는 해병이 야자를 많이 먹는다. 일찍 일어난다해도 3522개의 코코넛을 옮기는 일은 쉽지 않았을 것이다.~~

정답을 보면 해병들이 혼자서 야자들을 나누기에는 야자 수가 많이 비현실적이라는 사실을 알 수 있다. 그래서 판본에 따라 마지막에 야자를 나누고 각자 가질 때에는 야자가 남지 않는다고 되어있는 경우도 있다.~~원무룩~~ 이 경우 야자의 수는 최소 3121개로 원본보다는 좀 나은 편.

여기서 소개한 풀이법은 다소 번거로운 방법이지만 중간에 2개, 3개씩 남거나 할 때에도 확실하게 풀 수 있는 방법이다. 이외에 야자가 -4개 일 경우 무한반복이 된다는 점을 이용해서 거기에 15625를 더해 15621을 알아내는 풀이법도 있다. ||

4. 관련 문제 1

비슷하게 나머지를 이용해서 푸는 문제들이다. 풀이법도 위 문제와 어느정도 유사성이 있기에 같이 서술.

{{{#!wiki style="border:2px solid #00BFB3;border-radius:0px;padding:12px" 바둑알들이 들어있는 통을 보았다. 바둑알을 세 개씩 나누면 두 개가 남고, 다섯 개씩 나누면 세 개가 남고, 일곱 개씩 나누면 두 개가 남는다. 바둑알의 수는 최소 몇 개일까?

[ 해답 ]: ||<tablebordercolor=#552582>이런 문제에서는 나누는 수가 높은 것 부터 비교해나가면 된다. 7로 나눴을 때 2가 남는 수는 9, 16, 23, 30 ... 순으로 증가하고, 여기서 5로 나눴을 때 3이 남는 수는 23이다. 공교롭게도 23을 3으로 나눴을 때에도 2가 남으므로 정답은 23이 된다.

좀 더 복잡한 풀이법으로는 5와 7의 최소공배수, 3과 5의 최소공배수, 3과 7의 최소공배수와 나머지를 이용해서 푸는 정석적인 풀이법이 있다. 자세한 내용은 중국인의 나머지 정리 참조.||

}}}||

5. 관련 문제 2

{{{#!wiki style="border:2px solid #00BFB3;border-radius:0px;padding:12px" 한 간수가 관리해야 할 죄수는 아주 많았다. 다음은 죄수들의 식사시간에서 지켜야 할 규칙이었다.

1. 테이블 당 죄수의 수는 동일해야 한다.
2, 테이블 수는 홀수여야 한다.

그리고 간수는 이렇고 저렇게 죄수들을 앉히면서 아래와 같은 사실들을 알아냈다.

1. 테이블 당 3명씩 앉히면 두 명이 남고,
2. 5명씩 앉힐 경우 4명이 남고,
3. 7명씩 앉힐 경우 6명이 남고,
4. 9명씩 앉힐 경우 8명이 남으며,
5. 하지만 11명씩 앉힐 경우 한 명도 남김없이 모든 죄수가 앉을 수 있다.

죄수는 모두 몇 명일까?

[ 해답 ]: ||<tablebordercolor=#552582>일단 11명으로 앉았을 때 나누어 떨어지는 것 부터 시작하자. 해당 조건을 만족하는 수는 11, 22, 33 ... 이다. 이제 여기서 9명씩 앉았을 때 8명이 남는 수는 44이다. 이때 9와 11의 최소공배수는 99이므로 44에 99를 몇 번 더하더라도 이 두 조건은 만족시킬 수 있다. 즉, 11명씩 앉혔을 때 남는 죄수가 없고 9명씩 앉혔을 때 죄수 8명이 남는 조건을 만족하는 죄수의 수는 44, 143, 242, 341 ... 이 된다.

이제 다른 조건에서 이 과정을 반복하면 된다.

1. 앞서 언급한 수 중에 7로 나눴을 때 6이 남는 수 : 440 (7×62+6)
2. 7, 9, 11의 최소공배수 : 693
3. 조건을 만족하는 수는 440, 1133, 1826, 2519 ...
4. 여기서 5로 나눴을 때 4가 남는 수는 2519 (5×503+4)
5. 이때 2519를 3으로 나눴을 때도 2가 남으므로 (3×839+2) 2519는 위 조건을 모두 성립한다.

이제 테이블 수가 홀수인지만 판단하면 되는데, (홀수) × (홀수) = (홀수) 이고, (홀수) - (짝수) = (홀수)이기 때문에 굳이 확인할 필요 없이 모든 경우에서 테이블 수는 홀수이다. 죄수 수가 홀수이고 남은 죄수가 모두 짝수라는 점에 주목하면 금방 알 수 있다.

따라서 죄수의 수는 최소 2519명이다.어우

물론 2519에 3, 5, 7, 9, 11의 최소공배수인 10395를 더해도 나머지 조건은 성립한다. 그런데 (홀수) + (홀수) = (짝수) 니깐 테이블 조건을 성립시키려면 실제로는 두 배인 20790을 더해야 한다. ||