25마리의 말 경주 문제

인터넷에 떠도는 유명한 문제로.

 

25마리의 말이 있다.

5마리씩 경주할 수 있다.

가장 빠른 3마리 말을 찾기 위해 몇 번의 경주를 해야 하나?

 

풀이는?

 

사실 해법이 맞는지 모르겠다.

딱히 깔끔한 해법으로 보이지도 않고, 논리도 보이질 않아서.

 

그나마 가까운 게 7번의 경주란 답 아닌가 싶다.

 

1. 5마리씩 5개의 조를 짜서 5번의 경주를 한다.

2. 각 조의 1위 말을 모아서 6번째 경주를 한다.

 

그러면 6번째 경주의 1위 말은 전체 1위가 확정이다.

그러면 남은 전체 2, 3위를 확정하기 위해 가능성이 있는 말을 골라 경주를 시키는 일만 남았다.

 

3. 1위 말이 있는 조의 {2, 3}위, 2뮈 말이 있는 조의 {1, 2}위, 3위 말이 있는 조의 {1}위,

이렇게 5마리를 모아 7번째 경주를 시킨다.

 

그러면 6번째 경주에서 1위한 말이 1위, 이후로 7번째 경주의 결과로 2위부터 3위까지의 순위가 매겨진다.

참고로, 7번째 경주는 전체 3위 이내 가능성의 말들만 포함한 경주이기에 1, 2위 두 마리의 성적만 의미가 있다.

 

즉 7번의 경주로 상위 3개의 말을 찾을 수 있다.

정확히는, 7번의 경주로 1~3위의 순위까지 알아낼 수 있다.

 

왜 답안이 깔끔하게 보이지 않는 것일까?

 

위 답은 상위 3마리를 골라내는 답안을 넘어 순위까지 찾아낸다.

문제가 요구하는 바와 답안이 효율적으로 맞아 떨어지진 않는다는 말이다.

 

그리고 원리가 확장되는 것이 아닌,

각 케이스를 생각하고 최선의 케이스를 찾아내는 "노가다성" 답안이니 말이다.

 

물론 비슷한 방식으로 문제를 확장할 수는 있다.

하지만 형태의 제약이 큰 형태로 확장을 하니 답답한 면도 있는 것이다.

 

사족으로 이해를 위해서 그림을 더하면 아래와 같이.