불모지의 탐험가들
1. 개요
도중에 돌아가는 인원이 생길 시 필요한 인원(자원)을 구하는 문제.
2. 문제 1
| 탐험가 세 명이 불모지를 지나 사람이 살 수 있는 땅을 개척하기 위한 준비를 하고 있었다. 아직 차량이 다닐 수 있는지 판단이 되지 않았기에 우선 걸어서 도착하기로 했으며, 근처 지도와 기록을 통해 계산한 결과 불모지를 지나 목표지점까지 가는 데에는 최대 12일이 걸릴 것이라고 판단했다. 더불어 목표 지점에 도착하면 본부에 연락하여 헬리콥터를 통해 돌아가기로 했다. 탐험가들은 각종 장비들을 넉넉히 챙기고, 식량은 짐꾼을 고용해 같이 동행하기로 하였다. 그런데 짐꾼 한 명당 옮길 수 있는 식량의 최대치는 1인당 열흘 치를 먹을 양이기 때문에 12일이 걸릴 수 있는 탐험 시간에 비해 부족했다. 더구나 불모지의 특성상 헬리콥터나 차량 등을 통해 탐험 중간에 식량을 보급받는 것도 불가능하다는 본부의 답변을 받았다. 탐험가들은 고민 끝에 적당한 때가 되면 돌아가는 짐꾼을 정해 해당 짐꾼이 갖고 있는 식량을 나머지 짐꾼들에게 나눠주고 돌아가기로 했다. 물론 돌아가는데에도 왔을 때랑 같은 시간이 걸리기에 돌아가는 짐꾼의 식량도 고려해야 한다. 또한 돌아갈 때를 정하는 것은 하루 단위로 끊어서 계산한다. 예를 들어, 짐꾼 두 명이 각자 10일치의 식량을 갖고 불모지를 지나기 시작하면 사흘이 지나갈 때 짐꾼 하나가 3일치 식량을 다른 짐꾼에게 주고 돌아간다. 그러면 남은 짐꾼은 혼자서 10일을 더 가서 총 13일치의 탐험을 할 수 있고, 돌아가는 짐꾼은 4일치의 식량을 갖고 왔던 3일동안 돌아가는 식이다. 불모지 탐험에 동행할 정도의 실력있는 짐꾼을 구하기에는 시간과 돈이 들었기에 탐험가들은 최대한 짐꾼을 효율적으로 다루려고 한다. 12일 동안 짐꾼과 탐험가들의 식량 걱정 없이 불모지를 지나는 데에 필요한 짐꾼은 최소 몇 명일까? |
[ 해답 ] 일단 짐꾼이 첫 날이 지나고 돌아갈 경우 1일치의 식량만 남기고 나머지는 전부 배분하고 돌아갈 수 있으므로 8일치의 식량을 나눠줄 수 있다. 같은 방식으로 둘째날이 지나면 6일치, 셋째날에는 4일치, 넷째날에는 2일치, 닷새가 지나면 주는 식량 없이 돌아가야 한다. 따라서 엿새가 시작될 때 돌아갈 짐꾼을 정해 돌려보내고 그때부터는 남은 짐꾼들과 함께 7일동안 끝까지 가야 한다.
탐험가 3명에 닷새가 지나고 남은 짐꾼을 x라 했을 때 7일동안 필요한 총 식량의 양은 7(x+3)이다. 이때 짐꾼이 가질 수 있는 최대 식량의 양은 10x이므로 7(x+3)은 10x보다 작거나 같아야 한다. 방정식을 풀면 x=7임을 알 수 있고 닷새가 지났을 때 짐꾼 7명이 남도록 식량을 채우면서 짐꾼을 돌려보내면 된다.
이제부터는 거꾸로 계산하면 된다. 닷새가 지났을 때 돌아간 짐꾼을 a라 하고, 돌려보내는 것을 감안해서 당시의 식량은 70+5a가 남아있어야 한다. 닷새가 시작되었을 때로 돌아가면 식량은 80+6a(돌아가는 짐꾼과 남은 10명의 식량을 더하면 된다)가 되고, 그때 짐꾼이 가질 수 있는 최대 식량은 10(a+7)이다. 따라서 10(a+7) >80+6a가 되어야 하므로 이때 최소가 되는 a는 3명이어야 한다.
이제 4일이 지났을 때 돌아간 짐꾼을 b라고 하자. 당시의 식량은 98+4b가 되고, 4일이 시작할 때로 돌아가면 그 식량은 111+5b가 된다. 10(b+10) > 111+5b에서 b가 최소가 되려면 b는 3명이어야 한다. 3일이 지났을 때 돌아간 짐꾼을 c로 했을 때 필요한 식량은 126+3c이고 돌아가면 142+4c이다. 10(c+13) >= 142+4c 에서 필요한 짐꾼의 수는 최소 2명이다. 같은 방식으로 구하면 d=3, e=3도 구할 수 있다.
따라서 필요한 짐꾼의 수는 총 21명이 되며, 필요한 식량의 수는 최소 204일분이 정답이 된다. 또한 첫 날이 지났을 때 짐꾼 세 명을 돌려보내고, 2일이 지나면 3명, 3일이 지나면 2명, 4일이 지나면 3명, 5일이 지나면 3명의 짐꾼을 돌려보내야 하는 것을 알 수 있다.
3. 문제 2
| 탐험에 성공한 탐험가들은 탐험 도중 차량이 다닐 수 있을만한 곳을 표시해 두었고, 이번에는 차량을 타고 목표 지점까지 가는 길을 개척하려고 하였다. 차량을 타고 본부에서 목표 지점까지 가려면 총 300km를 운전해야 했는데, 차량에 넣을 수 있는 최대 연료의 양은 150km를 운행할 수 있는 양이었다. 차량 안에는 탐험장비들이 있어 추가 연료를 넣기는 어려웠다. 본부는 이번에도 다른 차량을 통해 중도에 연료를 공급하기는 어렵지만, 본부에서 연료는 얼마든지 줄 수 있다고 한다. 그래서 탐험가들은 일단 적당한 거리까지 간 다음 거기에 거점을 두어 차량에 남은 연료 일부를 남겨두고, 본부 또는 연료가 있는 거점으로 돌아가서 연료를 공급받아 더 먼 곳까지 가는 방법을 쓰기로 했다. 예를 들어 차량에 연료를 가득 채우고나서 연료를 1/4분의 거리를 가고 남은 3/4분의 연료 중 1/2를 거점에 남겨둔 다음 돌아간다. 그리고 본부로돌아가서 차량에 연료를 다시 채우고 거점으로 가면 차량에 연료가 3/4가 남아있으니 거기서 거점에 있던 1/2분의 연료 중 1/4를 채워서 갈 수 있는 식이다. 증발 등 연료의 자연손실이 없다고 가정했을 때 필요한 연료의 양은 최소 차량 몇 대분일까? |
[ 해답 ] 이번엔 반대로 차량 2대분으로 어디까지 갈 수 있을지 생각하고 3대분, 4대분으로 늘려서 계산하는 것이 좋다. 언제나 마지막 거점에서는 차량 1대분의 연료로만 갈 수 있다는 사실에 주의하자.
먼저 차량 2대분일 경우 최대로 갈 수 있는 방법은 아래와 같다는 사실을 알 수 있다.
1. 처음 1대분으로 일단 50km(1/3분)를 가서 50km어치의 연료를 남겨둔다.
2. 본부로 돌아간 다음 다시 1대분을 채워서 거점으로 가고, 거기서 남겨둔 1/3분의 연료를 다시 채우면 150km를 갈 수 있다.(총 200km)
차량 3대분일 경우 조금 복잡해지는데, 처음 만드는 거점에 연료 2대분을 남길 수 있도록 하면 그 다음부터는 위의 2대분일때와 같아지는 것을 이용하면 된다.
1. 1/5를 소모해서 30km 지점까지 가고, 거기서 3/5대분의 연료를 남긴 다음 다시 돌아간다.
2. 1번을 반복한다. 그럼 거점에는 6/5대분의 연료가 남아있다.
3. 다시 본부에 연료를 채워서 거점에 가면 처음 거점에서 차량 2대분의 연료가 남은 것이 되므로(차량에 남은 연료 4/5, 거점의 연료 6/5) 위의 2대분일 경우를 반복하면 된다.
이런식으로 처음 만드는 거점에 차량 n대분을 남길 수 있도록 행동을 반복하면 된다. 같은 방식으로 차량 4대분이면 1/7대분씩 소모하여 연료를 처음 거점에 15/7대분을 남기면 3대분 분량을 남길 수 있다는 것을 알 수 있다.
차량 한 대분당 150km를 갈 수 있으므로 연료가 몇 대분이냐(n)에 따라 갈 수 있는 거리(x)는 다음과 같다.
$$\displaystyle X = 150(1 + \frac{1}{3} + \frac{1}{5} + \cdot \cdot \cdot + \frac{1}{2n-1})$$
필요한 거리는 300km이므로 1/15까지 더해서 곱했을 때 300이 넘는 것(303.27)을 알 수 있다. 따라서 필요한 최소 연료는 차량 8대분이며, 연료를 둘 거점은 7개 만들어야 한다.