| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 1994년03월29일(화) 01시54분44초 KST 제 목(Title): Re: 6개짜리도 두번으로 안될꺼 같은데요. 6개는 당연히 안되죠... 5개도 도저히 두번만에 어떤 것이 다른 무게인지를 알아낼 수 없습니다. (Lemma 1) 임의의 N개의 돌이 있고, 그중 한개의 무게가 다르다고 할 때, 그하나를 찾고, 그것이 무거운지 가벼운지도 알 기 위해서는 적어도 log 2N 회의 저울질이 필요하다. 3 Proof) 저울(정확히는 천칭)의 상태는 왼쪽이 무겁다. 오른쪽이 무겁다. 양쪽의 무게가 같다 는 세 가지 정보중의 한가지를 나타낼 수 있습니다. 여기서 우리가 결정해야 하는 것은 N개중의 어느 것이 가벼운/무거운지를 알아내는 것이므로, 2N가지중의 한가지 결론을 내려야 합니다. 따라서 위의 bound 이하의 비교를 써서는 도저히 최종 답을 알아낼 수 없습니다. 즉, 5개의 돌의 경우, log_3 10 = 2.09... 이므로, 적어도 3번의 비교가 필요해집니다. (Lemma 2) 임의의 4개의 돌이 있고, 그중 한개의 무게가 다르다고 할 때, 그하나를 찾고, 그것이 무거운지 가벼운지도 알 기 위해서는 적어도 3회의 저울질이 필요하다. 이 증명은 직접 해 보십시요.. 재미있을겁니다. 단, 정상 무게를 가지는 제 5의 돌을 가지고 있다면, 저울질은 2번으로 족합니다. (12개에서 3번만에 찾는 경우, 첫 저울질이 평형이 된 경우..) 또, 무게가 다른 돌이 무엇인지만 궁금하다면, 이 경우에도 2번만에 무게가 다른 돌을 찾을 수 있습니다. (무거운지, 가벼운지는 모름..) 따라서, 돌이 3개 있는 경우에만 저울질 2번에 원하는 돌과 그 다른 것이 무엇인지를 찾을 수 있습니다. -- 씨디팍 박종대 |