| [ QuizWit ] in KIDS 글 쓴 이(By): semi (고봉균 ;-�) 날 짜 (Date): 1994년04월22일(금) 05시44분59초 KST 제 목(Title): Re:속이 빈 총알 골라내기 이거 참.. 여러 사람 허무하게 만들어 버릴 것 같은데.. 천칭 문제는 접해볼 기회가 여러번 있을 것 같은데요.. 지금 총알 문제처럼 어느 하나가 가볍다(혹은 무겁다)고 못박아놓은 경우라면 n번의 저울질로 밝힐 수 있는 원래 총알 갯수의 최대치는 3^n입니다. 그러니까 2번으로는 9개 중에서도 골라낼 수 있다는 얘기죠. 이의 증명은 쉬우므로 생략하겠습니다. 또 하나가 다른 것은 아는데 다른 것 보다 무거운지 가벼운지는 모르는 경우 두 가지의 문제가 있을 수 있습니다. 한 가지는 그 다른 것 하나를 찾아내라는 것이고, 또 한 가지의 문제는 그 다른 것 하나를 찾아내고 나머지보다 무거운지 혹은 가벼운지도 밝히라는 것입니다. 예를 들어 12개의 상품 중에 무게가 다른 하나의 불량품이 섞여 있는데 3번의 저울질로 그 하나를 찾아내고 나머지들보다 무거운지 가벼운지도 밝혀낼 수 있습니다. 만만치 않으니 시도해 보시길. 여기에 대해서도 증명이 되어 있는데, 무게를 가벼운지 무거운지 밝혀낼 필요가 없는 경우라면 n번의 저울질로 (3^n-1)/2개까지를 가려낼 수 있습니다. --약간 재미있는 증명기술이 사용되는데 여러분도 증명을 한번 시도해 보시길-- 또 가벼운지 무거운지까지 밝혀내야 한다면 n번의 저울질로 (3^n-1)/2-1개까지를 가려낼 수 있습니다. 즉, n이 4이면 이 값은 12가 되죠. 또, 가벼운지 무거운지를 밝혀내야 하는 경우라도 이미 표준 상품임을 알고 있는 상품이 몇 개 더 주어져 있으면 n번의 저울질로 최대 (3^n-1)/2개까지를 가려낼 수 있습니다. 이는 역시 3진수에 관계가 있습니다.(증명에 3진수를 도입할 필요는 없지만) 무거운지 가벼운지 판별해 내야 하는데, 표준 상품이 몇 개 더 주어져 있는 경우를 예로 삼아 대충 생각해봅시다. m개의 총알이 있을 때 각각이 가벼운가 무거운가에 따라 총 결과로 나타날 수 있는 경우의 수는 2m가지입니다.(하나의 총알에 대해 무거울 수도 있고 가벼울 수도 있고 해서 2가지씩 나타나므로) 근데, 한번의 저울질로 나타나는 현상은 3가지입니다.(왼쪽으로 기울어졌느냐, 오른쪽으로 기울어 졌느냐, 기울어지지 않느냐) 즉, n번의 저울질로 판별할 수 있는 총 경우의 수가 3^n가지가 됨을 의미합니다. 즉 우리가 가려내야 할 경우의 수가 우리가 가려낼 수 있는 최대의 경우의 수보다 크면 곤란하므로, 2m <= 3^n을 만족하여야 합니다. 근데 3^n은 홀수이므로 m의 최대 가능한 수는 (3^m-1)/2가 됩니다. 물론 실제로는 이것보다 작을 수도 있습니다. 따라서 우리는 바로 이 수에서 m번의 저울질로 그 하나를 찾아낼 수 있는 방법을 증명에서 제공하여야 합니다. 여기서 위에서 말한 재미있는 증명기술이 사용되는데, 아주 길어질 것이므로 또 여러분의 도전의욕을 꺾어놓고 싶지가 않으므로 여기서 쉬잇!하겠습니다. 그럼 이만. -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- KIT Mathematics Problem-Solving Group(과기대 수학문제연구회) 사는 셈이이어요. |