2020년 5월 26일 카트라이더 갤러리에서 누군가가 던진 문제. 그리고 집단 지성이 항상 옳은 결론으로 가지는 않음을 보이는 수많은 예시 중 하나.

문제

누구도 리타이어를 하지 않을 때 카트리그 8인제 개인전 50점/80점 선취제에 필요한 최대 트랙 수는 몇 개인가?

트랙 당 승점은 다음과 같다.

1위	2위	3위	4위	5위	6위	7위	8위	계
10	7	5	4	3	1	0	-1	29

카갤

댓글에 정답을 외친 사람이 있었지만 안타깝게도 글쓴이는 복수의 그리디 알고리즘(greedy algorithm) 풀이와 신기해 보이는 화면 캡처에 낚여 오답으로 이끌렸다고 한다. 그리디 알고리즘은 최적해를 보장하지 않기 때문에 으로 이런 최적화 문제에 그리디 알고리즘을 쓰려면 이 알고리즘이 최적해를 찾는다는 것을 보여야 하는데 코딩을 시도한 사람들은 이 부분을 놓쳤다. 이런 문제에 프로그래머들이 시도해볼만한 다른 방법으로는 동적 프로그래밍(dynamic programming)이 있지만 이 문제에 적용하기에는 너무 시간이 오래 걸린다.

풀이

정답: 14개/22개.

풀이: 일단 정답의 상계 (upper bound)를 하나씩 구하자. 29 * 14 / 8 = 50.75이고 이는 14트랙을 달렸을 때 누군가는 50점에 도달했다는 의미이므로 14트랙은 50점 선취제에서 정답의 상계. 29 * 22 / 8 = 79.75이고 이는 22트랙을 달렸을 때 누군가는 80점에 도달했다는 의미이므로 22트랙은 80점 선취제에서 정답의 상계.

이제 실제로 14트랙/22트랙이 필요한 경우를 찾을 수 있으면 증명 끝. 못 찾으면… 실제로 가능한 모든 경우에 13트랙, 21트랙 안에 50점/80점에 도달함을 증명해야 하니 우리네 인생이 고달파지겠지.

그리고 카갤에 누군가 경로를 찾아 올렸으나 아무 관심도 받지 못했다고 한다. 정리하자면 다음과 같다.

A. 8개 트랙동안 점수를 최대한 골고루 나눠가지는 경우는 모두가 1-8위를 한 번씩 해서 29점씩 똑같이 얻는 경우. 단, 마지막에 8위를 하는 사람은 중간에 30점을 한 번 찍게 되므로 주의.

B. 네 번째 트랙에서 아무도 20점을 찍지 못하고 다섯 번째 트랙에서 아무도 21점을 찍지 못하게 할 수 있음.

트랙	A	B	C	D	E	F	G	H
1	10	7	5	4	3	1	0	-1
2	0	1	-1	3	4	5	7	10
3	10	7	5	4	3	1	-1	0
4	0	-1	1	3	4	5	7	10
5	0	5	10	4	3	7	-1	1
계	20	19	20	18	17	19	12	20

• 50점제에서는 첫 8트랙에서 모두 1-8위를 한 번씩 하고 그 다음 다섯 트랙에서 B. 와 같이 점수를 먹으면 13 트랙을 달리지만 누구도 50점에 도달하지 못함.
• 80점제에서는 첫 16트랙에서 모두 1-8위를 두 번씩 하고 그 다음 다섯 트랙에서 B. 와 같이 점수를 먹으면 21 트랙을 달리지만 누구도 80점에 도달하지 못함.

증명 끝.