무게가 서로다른 128개의 물건은 양팔저울로 몇번만에 세번쩨로 무거운물체를 알아낼수 있나요?

댓글1

• 0

  세상의모든계산기

  2015.07.27 - 17:40 2015.02.12 - 13:42 #4664

  제가 생각한 방법

  
  

  1. 1차전

  128개를 토너먼트 방식으로 붙여서  가장 무거운 것을 찾습니다. 

  http://ko.wikipedia.org/wiki/싱글_엘리미네이션_토너먼트

  
  

  이해하기 쉽게 사람이 경기를 하는 것으로 바꾸어 생각해 보겠습니다.

  이 때 필요한 경기의 수는 

   64+32+16+8+4+2+1 = 127 경기

  
  

  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+2+1 = 6경기를 치루어야 합니다. 

  
  

  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번째 무거운 돌을 구별해낼 수 있다.

  Attached file

  K-58.png 38.8KB 127

  댓글