3방법 ②: 반씩 그룹으로 나누어 비교하기

 

프로그램 17-1의 방법으로도 가짜 동전을 쉽게 찾아낼 수 있습니다. 하지만 저울질을 훨씬 덜 하고도 가짜 동전을 찾아낼 수 있는 방법이 있습니다. 아이디어는 바로 동전을 절반씩 나눠서 무게를 재보는 것입니다.

주어진 동전을 절반씩 두 그룹으로 나눠서 양팔 저울에 올렸을 때 한쪽이 가볍다면 그 가벼운 쪽에 가짜 동전이 있다는 뜻입니다. 따라서 반대쪽에 있는 절반의 동전은 더는 생각할 필요가 없습니다. 가벼운 쪽에 있는 동전만을 대상으로 다시 가짜 동전을 찾으면 됩니다. 이렇게 하면 저울질 한 번으로 남은 동전 절반이 후보에서 탈락합니다. 저울질 한 번에 동전 한 개만 후보에서 탈락되던 방법 ①과 비교하면 필요한 저울질의 횟수가 눈에 띄게 줄어듭니다.

남은 동전의 개수가 홀수일 때는 어떻게 반으로 나눌까요? 예를 들어 가짜 동전 후보로 동전이 일곱 개 남아 있다고 가정해 봅시다. 7은 홀수이므로 동전 일곱 개를 똑같은 수의 두 그룹으로 나누는 것은 불가능합니다. 하지만 세 개, 세 개, 나머지 한 개 이렇게 세 그룹으로 나눌 수는 있습니다. 세 그룹으로 나눈 후 개수가 세 개로 같은 두 그룹만 저울에 올려 보겠습니다.

왼쪽이 가볍다면 왼쪽에 올린 동전 세 개 중에 가짜 동전이 있을 것이고, 반대로 오른쪽이 가볍다면 오른쪽에 올린 동전 세 개 중에 가짜 동전이 있을 것입니다. 두 그룹의 무게가 같다면 저울에 올리지 않은 나머지 동전 하나가 가짜 동전이라는 뜻이 됩니다.