구슬이야기
구슬이야기
  • 김인수
  • 승인 2011.08.25 15:08
  • 댓글 0
이 기사를 공유합니다

머리는 쓸수록 더 명석해진다는 이른바 용불용설이 적용된다고 한다. 이 더위에 머리를 회전시킴으로 피서해보면 어떨까 생각하며 오늘은 구슬이야기로 수학이야기를 전개해 보려한다. 겉모양은 같지만 유리로 만들어진 구슬과 수정으로 만들어진 구슬은 무게가 다르다고한다. 유리구슬보다는 수정구슬이 더 무겁다고 한다. 그리고 유리 구술들의 각각의 무게는 모두 같고 수정구슬도 각각의 무게는 모두 같다고 하자. 이런 구술이 24개가 혼합되어 있는데 양팔저울을 몇 번 이용하면 유리구슬은 유리구슬끼리 모이고 수정구슬은 수정구슬끼리 모일 수 있는가? 한 것이 오늘의 문제이다.

이 문제는 지난주의 문제보다는 훨씬 복잡하지만, 그러나 차근차근 생각해 보면 그리 어려운 것만도 아니다. 일단 하나의 구슬을 골라 시험구슬(test marble)로 정해서 계속해서 다른 구슬과 무게를 비교하는 방법을 사용한다. 만일 시험구슬과 무게가 다른 구슬이 k-번째에 처음으로 나왔다고 가정해 보자 만약 처음 몇 개의 구슬은 시험구슬과 무게가 같았지만, k-번째 구슬이 시험구슬보다 무거웠다면 k-번째 구슬이 유리구슬이다. 그리고 (k-1)번째 구슬을 포함하여 무게를 비교했던 모든 구슬은 수정구슬이다. 이제 (k+1) 번째, (k+2) 번째 구슬의 무게를 계속해서 시험구슬과 무게를 비교할 수 있다. 이 중에서 시험구슬보다 무거운 것은 유리구슬이고 시험구슬과 무게가 같은 것은 수정구슬일 것이다. 따라서 양팔 저울을 23번 사용한 후에 모든 구슬을 수정구슬과 유리구슬로 분류할 수가 있을 것이다. 그리고 만약 무게가 같지 않은 첫 번째 구슬이 시험구슬보다 가벼웠다면 우리는 쉽게 그 구슬이 유리구슬이라는 것을 알 수 있고, 이때도 역시 앞에서와 마찬가지의 결론이 나온다.

지금까지의 풀이에서는 어떤 창의성이나 아이디어를 찾아 볼 수 없다. 따라서 좀 더 효율적인 알고리즘이나 아이디어가 있는지 알아보는 것이 우리의 과제가 될 것이다. 그래서 우리는 앞에서와 마찬가지로 두 개의 구슬을 골라 서로 무게를 비교해 보자. 그러면 두 가지 가능성이 생긴다.

첫 번째 가능성은 두 구슬의 무게가 서로 다른 경우이다. 서로 무게가 다른 경우에는 무거운 것이 유리구슬이고 가벼운 것은 수정구슬이다. 이제 두 개의 구슬을 양팔저울 한 쪽에 올려놓고 새로운 두 개의 구슬을 택해 나머지 한쪽에 올려놓는다. 이 경우에는 양쪽이 같은 경우, 먼저 올려놓은 쪽이 가벼운 경우와 무거운 경우 3가지 가능성이 나온다. 같은 경우에는 유리구슬과 수정구슬이 있는 경우요, 가벼운 경우는 두 개 모두 수정구슬이요, 무거운 경우는 두 개 모두 유리구슬이다. 따라서 우리는 세 가지 경우 중 어떤 경우라도 새로운 두 개의 구슬 중에서 유리구슬과 수정구슬이 몇 개인지 알 수 있다. 따라서 우리는 새로 택한 구슬 중에서 유리구슬과 수정구슬의 개수를 종이에 적은 후 따로 구분해 놓으면 된다. 그리고 다시 새로운 두 개의 구슬을 더 택해 양팔저울의 한쪽에 올려놓고 처음 두 개의 구슬의 무게와 비교한다. 이 방식으로 계속해 나가면 양팔저울을 1+=12 번 사용하여 무게를 비교하면 전체 구슬 중에서 수정구슬과 유리구슬의 개수를 알 수 있다. 이 방법은 앞에서의 방법보다 훨씬 발전된 방법이다.

두 번째 가능성은 두 구슬의 무게가 같은 경우일 것이다. 이 경우에는 모두 수정구슬이거나 모두 유리구슬이다. 그러나 이 경우에도 첫 번째 경우처럼 두 개를 모두 시험구슬 한 쌍으로 사용하자 그리고 다른 두 개의 구슬을 택하여 무게를 비교해 보자. 새로 택한 구슬의 무게가 같다면 유리구슬이던지 아니면 수정구슬이던지 처음 시험구슬의 쌍과 같은 종류의 구슬일 것이다. 하지만 아직은 그것이 유리구슬인지 아닌지 알 수 없다. 하지만 무게가 다른 두 개의 구슬이 나타날 때 까지 계속해서 같은 방법으로 시행한다. 만일 k-번째로 택한 두 개의 구슬의 무게가 달랐다고 가정해 보자. 만약 k-번째로 고른 두 개의 구슬의 무게가 무거웠다면 시험구슬을 포한한 지금까지의 구슬은 모두 수정구슬이고 가벼웠다면 모두 유리구슬이라는 결론에 이른다.

예를 들어 k-번째로 택한 두 개의 구슬이 무거웠다고 가정해보자. 이제 k-번째로 택한 이 두 개의 구슬의 무게를 서로 비교해 보자. 이 두 개의 무게가 같다면 모두 유리구슬일 것이고, 무게가 다르면 이 중 한개는 어느 것이 유리구슬인지 알 수 있다. 어느 경우든지 k-번째로 택한 두 개의 구슬 중에서 유리구슬을 고르고 처음 두 개의 시험구슬 중에서 수정 구슬을 한 개 고를 수 있으며 이 두 개를 새로운 시험구슬로 사용하여 첫 번째의 경우에서와 같이 마찬가지 방법으로 나머지 구슬의 무게를 비교한다. 그러면 결국 양팔저울은 1+(k-1)+1+=13번 사용하여 유리구슬과 수정구슬의 개수를 찾아낼 수 있다.

만약 구슬을 3개씩, 또는 4개씩 모아서 시험구슬로 사용한다면 좀 더 효율적이지 않을까? 또 어떻게 하면 양팔저울을 13번 보다 적게 사용하는 정교한 방법을 없을까? 독자들이 생각해 보기 바란다.


댓글삭제
삭제한 댓글은 다시 복구할 수 없습니다.
그래도 삭제하시겠습니까?
댓글 0
댓글쓰기
계정을 선택하시면 로그인·계정인증을 통해
댓글을 남기실 수 있습니다.