퀴즈 435 25개의 구슬
눈으로는 구별이 안 가게 생긴 구슬 25개가 있다.
물에 담긴 그릇에 구슬을 동시에 넣었을 때, 어느 구슬이 더 무거운지는 가라앉는 속도로 알 수 있다.
단 한 번에 구슬 5개만 넣을 수 있다고 할 때, 이 25개의 구슬 중 첫번째, 두번째 ,세번째로 무서운 구슬을 찾아내려면 최소한 몇번을 그릇에 넣어보아야 할까?
풀이
한번 측정할 때 5개 무게의 순서를 알 수 있다는 것이 이 문제의 핵심이다.
[내 기억에 이런 비슷한 문제를 냈었는데 검색이 잘 안된다 ㅠㅠ 그 때 썼던 전략은 일단 몇개씩 재고 거기서 무거운 것들끼리 또 재서 순서를 정하는 것이다. 이런 문제는 다 이런 방식이다.]
자 일단 25개니까 5개씩 나누어서 5번 실험을 해보자 그러면
그리고 가장 무거운 것들끼리 한번 돌리자. 그럼 여기서 가장 무거운 구슬은 전체 중에서 가장 무거운 구슬이다.
그 다음은 가장 무거운 구슬이 나왔던 회차에서 두번째, 세번재 무거웠던 구슬과 6번째에서 두번째 구슬이 나왔던 회차에서 무거운 구슬과 그 다음 무거운 구슬, 그리고 6번째의 3번째 구슬을 비교하면 된다.
7번째에서 25개 구슬 중 2번째와 3번째 구슬이 나온다는 것을 보이자. 다른 말로 쓰자면 왜 7번째 set 를
가장 무거웠던 구슬이 있던 곳에서 뽑아온 e4 와 e3 두번째 무거웠던 것에서 뽑아온 d5, d4, 그리고 c5
왜 이렇게 뽑아야 되는지 알아보자.
사실 이는 두번째 무거운 구슬이 나오는 경우를 생각하고 거기서 어떻게 3번째 구슬을 보일 수 있을까를 생각하면 된다.
먼저 두번째 무거운 것을 찾아보자 두번째 무거운 것은 d5 와 e4 를 비교하면 된다. (i) d5> e4 라면 두번째 무거운 것은 쉽게 찾아진다. 이 때 3번째 무거운 것을 어떻게 알 수 있을까? 3번째 무거운 것을 보려면 d4, e4, c5 의 대소관계를 알아야 한다. 즉 적어도 d5, d4, e4, c5 가 필요하다. (ii) e4> d5 라면 두번째 무거운 것은 e4 가 된다. 이 때 3번째 무거운 것은 어떻게 찾을 수 있을까? 이를 알기 위해선 e3 와 d5 의 관계를 알아야 한다. 여기서 e3 의 정보가 필요하다.
따라서 총 7번을 하면 3번째 무거운 구슬을 알아낼 수 있다.
c.f) 4번째로 무거운 구슬은?
심심해서 4번째로 무거운 구슬도 한번 찾아봤다.
자 7번째 측정 결과
즉 8번째는 임의의 번호를 가지고 하는게 아니라 그냥 케이스 바이 케이스로 나누어서 해야된다.... 이 때는 경우의 수가 나누어져서 고려해야 하니까 별로군 ㅠㅠ
또 만약 한번에 측정할 수 있는 구슬의 횟수를 증가한다면 또 다른 문제가 되겠다.