말 25마리 중에서 가장 빠른 말 3마리를 찾기 위한 최소 경주 횟수를 구하는 문제

가장 빠른 말

말이 25마리 있다. 이 중에서 가장 빠른 말을 3마리 찾아야 한다. 그러기 위해서는 "최소" 몇 번의 경주를 하면 알아낼 수 있는지 묻는 문제다. 여기까지는 매우 쉽다. 그냥 달리면 1~3등 말이 나오기 때문. 그래서 이 경주에는 3가지 조건이 있다.  경주의 조건은 다음과 같다.

1. 경주는 한 번에 5마리만 달릴 수 있다.

2. 타이머가 없어 시간을 알 수 없다.

3. 말은 뛸 때마다 순위가 바뀌지 않으며, 몇 번을 달려도 지치지 않는다.

이 조건에 따라 25마리의 말 중 가장 빠른 말 3마리를 찾기 위한 최소 경주 횟수를 알아내야 한다.

5마리씩 경주를 할 수 있고 5번을 해야 25마리가 모두 달리기가 되니 최소 5번 이상이다. 여기서 벌써 답이 나올 수 있는데 1~3등 말을 찾기 위해 최소 6번의 경주만 하면 된다라고 생각할 수 있다. 5번의 경주에서 각각 1등 말이 나올 테고 그 1등 말은 5마리이니 1등끼리 다시 재대결을 하면 결국 1위부터 5위까지 나온다. 순번에 따라 각 조의 1등끼리 달린 결과이니 6번째 1등끼리의 대결에서 1~3위가 가장 빠른 말이라고 단정 지을 수도 있다. 

만약 그런 결과를 냈다면 "하수"다. 첫 번째 조건인 5마리만 달릴 수 있다는 것은 적용되었는데 나머지 2개의 조건과는 무관한 내용이 된다. 2번 조건을 보면 타이머가 없어 시간을 알 수 없다라고 되어 있다. 즉 어떤 기준으로 5개의 조를 만들었다고 해도 각 조의 1등이 전체 5위안에 든다는 보장은 없다.

다시 말해 1조의 2등, 3등 말이 2조의 1등보다 빠를 수 있고 5조의 1등 말이 다른 조의 꼴등 보다도 못할 수 있다는 것이다. 25마리 중에서 가장 빠른 말 1~3위를 뽑는 것이기 때문에 6번의 결과로는 완전하게 찾을 수 없게 된다. 

1조의 1등 20초, 2등이 21초, 3등이 22초, 4등이 23초, 5등이 24초라고 가정했을 경우 2조의 1등이 28초일 수 있고 3조의 1등이 26초일 수도 있다. 각 조에서 1등을 했어도 그 조의 5마리 안에서는 가장 빠르다는 것만 증명되는 것이지 1등끼리 묶는다고 하면 다른 조의 말보다 빠른지 알 길이 없어 결국 정확한 순위를 알아낼 수 없게 된다.

각 조의 1등끼리 묶어 6번째 경주를 한다고 하면 예를 든 1조의 1번 말은 1조보다 못 한 말들과 달리는 꼴이 되기 때문에 오히려 1조의 2등과 3등 말이 더 빠름에도 제외가 된다. 그래서 2번 제한 조건이 붙는 이유다. 타이머가 없고 시간을 알 수 없기 때문에 1등끼리 묶는다는 것과 최소 6번은 결국 아니게 된다.

MC무의 풀이 과정을 한번 참고해 보자

다섯마리씩 5번 경주를 기본으로 우선 하고 그중에서 각 조의 1등 말을 모아 6번째 경주를 한다. 각 조의 1등 묶음 경주에서 다시 1등을 한 말은 전체 1위가 된다는 건 쉽게 알아낼 수 있다. 문제는 두 번째로 빠른 말과 세 번째로 빠른 말을 찾을 수는 없다는 것인데 각 조의 2등 말끼리 다시 묶어서 이번에는 2등끼리 경주를 하게 하고(7번째 경주) 거기서 1등을 한 말이 다시 1등 빈자리로 들어가 2 등계의 1등과 각 조 1위 대결에서 남은 4마리와(1위는 이미 확정) 함께 재대결을 한다는 것이다. (8번째 경주)

MC무의 풀이는 여기까지 나오다가 잠시 멈췄는데 만약 여기서 답을 찾는다고 했다면 실패, 다시 3등끼리 묶어서 또 경주(9번째)를 하고 3등계의 최강자가 다시 2 등계와 자리싸움(10번째)을 하고 거기서 또 승리한 말이 다시 1등끼리 묶은 조와 재대결(11번째)을 한다면 그건 가능성이 높다. 

다섯 마리씩 묶어서 5개의 조를 편성했다고 해도 각 조의 3위권 안에 들지 못하면 전체 3위를 절대로 할 수 없기 때문에 가장 빠른 말을 알아내기 위해서는 3위권 안에 든 말을 상대로 재대결을 해야 하는 건 당연하다. 각 조의 3위안에 든 말 15마리는 이런 과정을 통해 추려 낼 수 있고 10마리는 제외할 수 있게 된다. 

또한 3등계와 2 등계끼리 재대결을 해서 3 등계는 최강자는 2 등계와 다시 붙고 2 등계 최강자는 다시 1 등계와 붙기 때문에 가장 빠른 말 3마리는 찾을 수 있다. 1조의 다섯 마리가 모든 조보다 빠르다고 가정해도 1조에서 3위안에 들지 못하면 결국 전체 3위안에도 못 든다. 결국 어떤 조든 4위, 5위를 한 말은 전체 3위안에 들 수가 없기 때문에 4등 말과 5등 말은 모두 제외가 된다. 

11번의 경주가 답일까? 하지만 정답은 아니다 땡!. 찾을 수 있지만 문제의 핵심은 "최소" 즉, 이 보다 더 적은 수로도 가장 빠른 말을 찾을 수 있기 때문에 정답이 아니다. 찾을 수 있냐 없냐가 아니라 최소 몇 번의 경주로 알아낼 수 있느냐가 문제이기 때문에 최소 경주수가 아니라면 틀린 답이 된다.

이번 문제도 6명의 뇌섹남이 모여 1시간 동안 풀지 못했던 문제 중 하나다. 물론 결국에는 답을 찾았지만 머리에 쥐나게 만든 건 분명하다. 정답은 아래부터 공개한다. 

다섯 마리씩 묶어서 5개 조를 만들고 각각 경주를 벌인다 (5 경주), 그리고 각 조의 1등 말을 모아 재대결을 한다 (6 경주), 6 경주에서 4위와 5위는 어차피 전체 3위안에 들지 못하기 때문에 제외가 되고 그 제외가 된 1등 말이 속한 조 전체도 제외가 된다. 나머지 조는 3개가 남고 그 안에서도 각각 4위와 5위 말들은 전체 3위안에 들지 못하기 때문에 모두 제외, 결국 남은 3개 조의 3위권 안에 드는 9마리가 6 경주만으로도 추려질 수 있다.

여기서 각 조마다 1위한 말끼리 재대결(6 경주)을 했을 때 1 등계에서도 이미 1위, 2위, 3위는 우선적으로 나온 상태이기 때문에 각 조의 경주마 속도는 유추가 가능하다. 1 등계 3위가 속한 조의 2등과 3등 말은 역시 전체 3위에 들 수 없다. 1등끼리 재대결을 했을 때 2위를 했던 조에서도 제외수가 생기는데 전체 1위와 자신(2위)이 나온 상황이기 때문에 다른 나머지 한 조에서 한 마리가 나오거나 자신의 조에서 한 마리가 나올 수 있다. 

자신의 조에서 한 마리만 나올 수 있다는 건 결국 1등간 대결에서 2위를 했던 조의 3등 말도 전체 3위안에 절대 들지 못한다. 결국 제외가 자동으로 된다. 아직 6경주만 한 상태에서 계산만으로 9마리에서 3마리가 추가 제외를 할 수 있게 된다. 남은 마리는 총 6마리

1등계에서 1위를 한 말은 6 경주에서 바로 전체 1위로 확정이 되기 때문에 나머지 5마리, 전체 1위를 한 말이 속한 조의 2등과 3등, 1 등계에서 2위를 했던 조의 1등 말과 2등 말, 그리고 1 등계에서 3위를 했던 남은 한 조의 마지막 말을 묶어서 모두 달리게 하면 결국 그 안에서 순위가 나오고 거기서 1등이 전체 2위, 2등이 전체 3위가 된다.

결국 6경주에서 딱 한번 더 총 7번 만의 경주만으로 25마리 중에서 가장 빠른 말 세 마리를 찾을 수 있다. 복잡한 문제일 수 있지만 충분히 풀 수 있는 문제로 꽤 재미있고 즐길만한 문제로 보인다. 

 

[국가/자주국방] - 양심적 병역거부 위헌이 안겨준 숙제와 논란, 그리고 더 많은 문제점

[교육/문제풀이] - 헤어짐을 부를 수 있는 남자친구에게 특화된 일본 창의력 문제 (오빠 나 오늘 어때?)

[교육/문제풀이] - 직선 4개로 11개의 구역을 만들고 각 구역 안의 숫자 합이 10이 되게 하는 문제

[교육/훈육보육] - 내 아이 낯선 사람 따라가지 않게 반복 학습으로 교육하는 방법 - 제복 인식 훈련

[교육/문제풀이] - 문제적 남자 역대 최고 난이도(?)의 시청자 퀴즈 (124-479-462-586-248-2X1-355)

[문화예술/영화리뷰] - 타임 패러독스(프리 데스티네이션) 별 다섯개 추천

[교육/토론학습] - 닭과 알 중에 무엇이 먼저냐 그것이 문제로다.