/퍼즐-몇번물어봐야하나

P, Q, R, S의 네 명이 경주를 하여, 1위부터 4위까지의 순위를 매겼다.
이 중 2명에게 「너희들 두 명 중, 누가 빠르지?」라고 몇 번인가 반복하여 질문하고,
네 명 전원의 순위를 추리하는 콘테스트를 생각한다.
1회 질문할 때 마다 득점이 1점씩 내려가기 때문에, 가능한 한 질문의 횟수를 적게 하며,
또한 4인 전원의 순위를 확실히 추리하고 싶다.

P, Q,  R, S의 4인이 질문에 정확히 대답한다고 하면, 질문의 횟수는 최저 몇 번, 최고 몇 회인가? 

4명 중에 3명을 골라서 그 3명의 순위만 먼저 결정합니다.
이것은 운이 나쁘면 3번만에 되고 (P-Q, P-R, Q-R 순으로 물었을때) 운이 좋으면 2번만에 됩니다 (P-Q, Q-R 순으로 물었을때)

1) 3번만에 결정된 경우에는, 욕심을 버리고 남은 한 명을 2등과 비교. (4번째) 
1-1) 2등보다 크면 1등과 비교하여 5번만에 끝 
1-2) 2등보다 작으면 3등과 비교하여 5번만에 끝 

2) 2번만에 결정된 경우에는 남은 한 명을 1등과 비교. (3번째) 
2-1) 운이 좋아 1등보다도 빠르면 3번만에 끝. 
2-2) 1등보다 느리면 그 다음은 2등과 비교. (4번째) 
2-2-1) 2등보다 빠르면 4번만에 끝. 
2-2-2) 2등보다 느리면 3등과 비교. 5번만에 끝.

• gear : 이런 평범한 저의 방법으로는 4번이네요. A,B 비교 후 승자를 Q, 패자를 W, C,D 비교후 승자를 E, 패자를 R로 놓으면 (여기까지 2번비교), 승자 Q,E 비교, 패자 W,R 비교 (4번 비교) 이렇네요 ㅎㅎ - 2006-11-17 1:42 pm
• gear : 이제 봣더니 문제의 요지가 최저 몇번, 최고 몇번이였군요 ㅡㅡ;; - 2006-11-17 1:43 pm
• Raymundo : gear/ 안녕하세요. AB의 승자가 CD의 패자보다도 더 느릴 수도 있고, C와D의 중간일 수도 있습니다. 그렇게 비교하시려면 6가지 조합을 다 하셔야만 합니다. - 2006-11-17 3:05 pm
• Raymundo : 아 6번이 아니라 5번이네요. Q와E (승자전)의 패자와 W와R (패자전)의 승자를 비교하는 것만 추가하면 되겠네요. - 2006-11-17 3:12 pm
• 일일공이 : 맞혔어요~ ㅋㅋㅋ - 2006-11-20 11:42 am