무게가 서로다른 128개의 물건은 양팔저울로 몇번만에 세번쩨로 무거운물체를 알아낼수 있나요?
-
- *.78.140.87
- 2015.10.16 - 09:30 2015.02.12 - 12:49 744 1
출처 : http://kin.naver.com/qna/detail.nhn?d1id=11&dirId=1113&docId=218014324&page=1#answer2
네이버 지식인에서 본 문제입니다.
재밌는 것 같으니, 같이 함 풀어봅시다.
제가 생각한 방법
1. 1차전
128개를 토너먼트 방식으로 붙여서
가장 무거운 것을 찾습니다.
http://ko.wikipedia.org/wiki/싱글_엘리미네이션_토너먼트
이해하기 쉽게 사람이 경기를 하는 것으로 바꾸어 생각해 보겠습니다.
이 때 필요한 경기의 수는
2. 2차전
1차전 우승자를 제외시키고,
나머지 중에서 가장 무거운 것을 찾는 2차전을 엽니다.
이 때 참가할 자격이 있는 선수는
1차전 우승자에게 1차전에서 떨어진 자 가 됩니다.
1차전에서 우승자는 결승전 포함하여 총 7경기를 치루어 모두 이겼으니까(7전 7승 무패) 7명이 후보가 있겠고,
각 후보의 전적은 '1전0승1패', '2전1승1패', '3전2승1패', '4전3승1패', ..., '7전6승1패=(1차전 준우승자)'가 됩니다.
이 7명의 후보를 먼저 떨어진 순서대로 묶어 토너먼트를 치루고, 가장 무거운 돌을 찾습니다.
(1차전 준우승자는 1R 부전승)
3. 3차전
이제 드디어 세번째 무거운 돌을 가릴 차례가 되었습니다.
3차전 참가자격이 있는 선수는
조건 a = 2차전 우승자(=준우승자)에게 1차전에서 떨어진 자
조건 b = 2차전 우승자(=준우승자)에게 2차전에서 떨어진 자
3 - 경우1. 2차전 우승자가 1차전 준우승자(1차전 전적 7전6승1패)인 경우
a. 1차전 준우승자는 1차전에서 총 7경기를 하였는데, 6번 이기고, 1번(결승전)은 졌으므로, 후보 6명.
b. 2차전에서 (부전승을 제외하고) 2 경기를 하였으므로 후보 2명.
총 후보 8명
경기수 7회
3 - 경우2. 2차전 우승자가 4강에서 1차전 우승자에게 떨어진 자일 경우(1차전 전적 6전5승1패)
a. 후보 5명
b. 후보 3명 (총 3경기)
총 후보 8명
경기수 7회
3 - 경우 3. 2차전 우승자가 1차전 전적 5전4승1패인 경우
a. 후보 4명
b. 후보 3명
총 후보 7명
경기수 6회
3 - 경우 4. 2차전 우승자가 1차전 전적 4전3승1패인 경우
a. 후보 3명
b. 후보 3명
총 후보 6명
경기수 5회
3 - 경우 5. 2차전 우승자가 1차전 전적 3전2승1패인 경우
a. 후보 2명
b. 후보 3명
총 후보 5명
경기수 4회
3 - 경우 6. 2차전 우승자가 1차전 전적 2전1승1패인 경우
a. 후보 1명
b. 후보 3명
총 후보 4명
경기수 3회
3 - 경우 7. 2차전 우승자가 1차전 전적 1전0승1패인 경우
a. 후보 0명
b. 후보 3명
총 후보 3명
경기수 2회
4. 결론
따라서 총 저울로 재야하는 횟수는 1차전 횟수 + 2차전 횟수 + 3차전 횟수가 되고
127 + 6 + (2~7) = 135~140 회
최소 135경기, 최대 140경기를 통해 3번째 무거운 돌을 구별해낼 수 있다.