Brain teaser: weighing marbles/coins 여러개의 코인중 무게가 다른 하나 찾기

Q: 이번에는 구슬 대신 코인이 90개가 있는데, 89개는 동일하고
    하나만 무게가 다르지만, 그것이 더 무거운지 가벼운지는 모른다.
    저울을 한번 잴 때마다 100달러가 든다고 할 때,
    무게가 다른 코인을 찾고, 그것이 무거운지 가벼운지를 알아내기위해 필요한
    최대 비용을 최소로 하는 방법은 무엇일고, 이 때의 최대 비용은 얼마일까?
 



A:  일반적으로 N개의 구슬중 하나를 가려내는 문제를 생각할 때,
      저울질을 최소로하는 가능한 최선의 전략이 무엇인지를 알 수 있을까?
     솔직히 다음의 풀이가 가능한 최선인지는 모르겠다. 누군가 증명할 수 있다면 좋겠다.

     A 와 B를 한번 저울질하는 것으로 알수 있는 정보는 A=B, A>B, A<B 의 세가지이므로
    언제나 이 3가지 경우가 다른 결론을 주도록 하는 것이 최선일 것으로 보인다.

    (0)먼저,  무게가 다른 하나가 더 무거운지 더 가벼운지를 알고 있는 경우를 생각해보자.
    구슬의 갯수가 3 개인 경우는 1번의 저울 질로 무게가 다른 하나를 찾을 수 있다.
     9개의 구슬의 경우에는 3개씩 묶음이 3개 있다고 생각할 수 있으므로,
     2번의 저울질이면 충분함을 알 수 있다.  마찬가지로  3^k 의 구슬이 있고,
    무게가 다른 것이 더 무거운지 가벼운지를 안다면 k 번의 저울질로 하나를
    반드시 골라낼 수 있다.  따라서, 어떤 수의 구슬이건 3^k 와 비교하는 것으로
     몇번의 저울질이 필요한지 알 수 있다.
       (예를 들어 구슬이 10개인 경우  3^2  과 3^3  사이에 있으므로,
       최대 3번의 저울질로 무게가 다른 하나를 반드시 골라낼 수 있다.)

 
    이제 무게가 다른 것이 더 무거운지, 가벼운 지 모르는 경우를 생각해보자.
    다음과 같은 전략을 따라보자.

    (1)  구슬을 가능한 같은 수의 구슬로 이루어진 세개의 그룹으로 나누자.
           편의상
           {ㅜn}_A 는 앞으로 n 개의 구슬로 이루어진 그룹을 A라는 이름으로 부른다는 의미로
           사용하자. 그러면, 처음의 세 개의 그룹은 적당한 n 에 대해
            {n}_A, {n}_B, {n}_C 이거나, {n}_A, {n}_B, {n+1}_C 이거나,
            {n+1}_A, {n+1}_B, {n}_C 로 쓸 수 있다.  어느 경우나, A와 B 는 같은 갯수가
            되도록 할 수 있고, 이 때의 개수는  n 이나 n+1 이다.  편의상 A,B 그룹의 구슬의 개수를
            m  이라고 쓰자. 그리고 무게가 다른 하나를  x라고 부르자.
            {m}_A와 {m}_B 를 비교하면,
            {m}_A = {m}_B 즉, 무게가 같거나,
            {m}_A > {m}_B 즉,  A  쪽이 더 무겁거나
            {m}_A < {m}_B , B쪽이 더 무겁거나 중의 하나이다.
         하지만, 무게가 다른 경우 무거운 쪽을 A가벼운 쪽을 B 라고 부르기로 약속하면,
         두가지 경우만 생각하면 된다.

    (2) A와 B의 무게가 같은 경우,  C그룹에 x가 있음에 틀림없다.
                 이로써,   x 의 가능한 범위를 약 1/3 정도로 줄일 수 있게 되었다.
                 하지만, 아직 x 가 더 무거운지 가벼운지는 모르므로, 처음 상황과 비슷하다.
                 따라서, (1) 로 돌아가서 다시 세 그룹으로 나누고 반복한다.

     (3) A 가 더 무거운 경우, x 가 A 에 있고, x 가 더 무거운 것이거나,
                  x가 B에 있고,  x가 더 가벼운 것이거나, 둘 중의 하나이다.
                  다시   A 와 B를 가능한 균등하게 3 부분씩으로 나눈다음,
                  A의 2/3 정도를 {n1}_A 라 부르고 나머지 1/3을 {n2}_A 라 부르자.
                  (정확히 1/3일 필요는 없다.)
                 마찬가지로  B도 {n1}_B, {n2}_B로 나누자. (A와 B는 같은 개수로 이루어 졌으므로
                 똑같은 개수의 작은 그룹들로 나뉜다.) 그리고,  정상적인 C그룹에서 n1 개를 골라서
                 {n1}_C  를 만든다.
           이제, {ㅜn1}_A 와 {n2}_B 를 한 쪽에 {n2}_A 와 {n1}_C를
          반대쪽에 두고 비교하자. 그러면
          (3-1) {ㅜn1}_A + {n2}_B = {n1}_C+ {n2}_A 이거나
          (3-2) {ㅜn1}_A + {n2}_B > {n1}_C+ {n2}_A 이거나
          (3-3) {ㅜn1}_A + {n2}_B < {n1}_C+ {n2}_A 일 것이다.

          (3-1) 의 경우는 {n1}_B에  x 가 있고, x가 더 가벼워야한다.
                   ( {n1}_A, {n2}_A, {n2}_B 는 정상인데,  B가 가벼웠으므로)
                   이제 우리는 x  가 더 가볍다는 것을 알아냈고,
                   {n1}_B중에 있다는 것을 알고 있으므로, (0)의 경우와 같아지게 된다.
                 이 때는 3^k  와 n1 을 비교하는 것으로
                 몇번의 저울질이 필요한지를 알 수 있게 된다.

          (3-2) 의 경우는 {n1}_A에 x가 있고, 더 무거워야 함을 알 수 있다.
                  ( A>B 였므로, {ㅜn2}_B 가 더 무거울 수는 없다.)
                   이제 우리는 x  가 더 무겁다는 것을 알아냈고,
                   {n1}_A중에 있다는 것을 알고 있으므로, (0)의 경우와 같아지게 된다.
                 이 때는 3^k 와 n1을 비교하는 것으로 몇번의 저울질이 필요한지를 알 수 있게 된다.
         (3-3) 의 경우는 {n2}_B 가 가볍거나, {n2}_A 가 더 무겁거나 이다.  이 것은 (3)의
              시작 조건과 같고 단지 개수가 1/3 정도로 줄어든 것과 같다. 따라서,
                (3) 으로 돌아가,  {n2}_A 와 {n2}_B를 다시 두 그룹씩으로 나누고
                비교하는 것을 반복한다.
           
위의 전략을 반복하면, 매 번 저울을 잴 때마다,  x 의 가능한 범위를 1/3씩 줄이거나
x 의 무게가 더 무거운지 가벼운지를 알 수 있데 되고, 일단  x가 더 무거운지 가벼운지를
알게 되면 (0)의 경우처럼, 앞으로 필요한 최소한의 저울질의 개수를 알 수 있게 된다.

이제 동전이 90개인 경우를 생각해보자. 앞에서 설명한 것처럼
먼저 {30}_A, {30}_B, {30}_C로 나누고, A와 B를 비교한다.

(1) A=B 라면,   C를 {10}_a, {10}_b, {10}_c 로 나누고 다시  a 와 b 를 비교한다.
      (1-1) {10}_a={10}_b 라면, {10}_c 를 {3}_aa, {3}_bb, {4}_cc 로 나누고, aa 와 bb를 비교.
               (1-1) {3}_aa={3}_bb 라면,
                          cc의 4개중 하나가  x 임을 알 수 있고, 두번 더 저울질하는 것으로
                          무게가 다른 하나와 그것이 무거운지 가벼운지를 알아낼 수 있다.
                           따라서, 총 5번의 저울질로 충분하다.
               (1-2) {3}_aa > {3}_bb 라면,  {2}_aa +{1}_bb   와 {1}_aa +{2}_cc  를 비교한다.
                           (1-1-2-1) {2}_aa +{1}_bb = {1}_aa +{2}_cc 인 경우는, {2}_bb중 하나가   x이고,
                                         더 가벼운 것이므로, 한번만 더 저울질하면 x를 찾으 수 있다.
                                          (총 5번의 저울질)
                            (1-1-2-2) {2}_aa +{1}_bb > {1}_aa+{2}_cc  인 경우는
                                           {2}_aa 중 하나가 더 무거운 것이므로   한 번 더 저울질하면 된다.
                                           (총 5번)
                            (1-1-2-3) {2}_aa+{1}_bb < {1}_aa+{2}_cc  인 경우는
                                            {1}_bb 가 가볍거나, {1}_aa 가 무겁거나 이므로,
                                           이 둘을 비교하면 된다. (총 5번)
                (1-1-3) {3}_aa < {3}_bb 라면, 앞의 (1-1-2)에서 a와 b 의 이름만 바꾼 것과 같다.
                            따라서, 이 경우도 총 5번의 저울질 이면 충분함을 알 수 있다.
        (1-2) {10}_a > {10}_b 라면,  {10}_a 를 {6}_a, {4}_a 로 나눈다.
                 마찬가지로,   {10}_b는  {6}_b, {4}_b 로 나눈다. 그리고 처음의 A나 B중에서
                 6개를 골라서 {6}_c를 준비한다.
                 {6}_a+{4}_b 와 {6}_c+{4}_a 를 비교한다.
                (1-2-1) {6}_a+{4}_b = {6}_c +{4}_a 라면, {6}_b 중에 하나가 x 이고, 무게는
                          더 가볍다.  이제, 3^1 < 6 < 3^2  이므로, 두번의 저울질로 x 를 찾아 낼 수 있다.
                           (총 4번)
                (1-2-2) {6}_a +{4}_b > {6}_c +{4}_a 라면, {6}_a 중 하나가 더 무거운 것이다.
                            따라서, 역시 2번만 더 저울질하는 것으로 x 를 찾아낼수 있다.  (총 4번)
                (1-2-3) {6}_a+{4}_b < {6}_c +{4}_a 라면,
                            {4}_b   가 가볍거나, {4}_ a 가 무겁거나 이다. 다시 이 들을 {3}_a,{1}_a
                             {3}_b, {1}_b 로 나누어
                            {3}_ a + {1}_b 와 {3}_c +{1}_a 를 비교한다.
                            이제 앞의 경우처럼 생각하면, 최대 1 번의 저울질을 더 하는 것으로
                           x 를 찾아 낼 수 있다. (총 5번)

등등.....

같은 전략을 반복하는 것으로 90개의 동전의 경우 최대 5번의 저울질이면 충분함을
알 수 있다. 따라서, 답은 $ 500 이다.


글이 너무 길어 졌다. 답을 알아낸 것 같긴 한데, 증명이 부족한 것 같다. 좀 더 우아한
증명이 있으면 좋겠다.