Q1: 12개의 똑같아 보이는 구슬이 있는데, 오직 하나만이 무게가 살짝 다르다.
더 무거운지 더 가벼운지는 모른다. 저울을 오직 3번만 재서, 무게가 다른 하나를 찾고,
더 무거운지 가벼운지를 알아내라.
There are 12 marbles which have the same look. Among them, only one have
different mass but it is not known whether it is heavier or lighter.
Find odd one by only weighing balance up to 3 times and find out
whether it is lighter or heavier.
A1: 먼저 12 개의 구슬을 3개의 그룹(구슬 4개씩)
A(a1,a2,a3,a4), B(b1,b2,b3,b4) ,C(c1,c2,c3,c4) 로 나누고,
A,B를 비교한다. (저울 사용1)
무게가 다른 하나를 x라고 부르자.
3가지 경우, A=B, A> B, A<B 경우를 생각하자.
(1) 만약, A=B라면, 나머지 C중 하나가 x 이다.
이제 C 중에서 (c1,c2,c3)와 A를 비교한다. (저울 사용2)
(1-a) 만약, (c1,c2,c3) = A라면 c4 가 바로 x 이다.
c4 와 아무 구슬 하나를 비교하면, 가벼운지 무거운지 알 수 있다. (저울 사용3)
(1-b) 만약, (c1,c2,c3) > A라면 c1,c2,c3 중 하나가 무겁다.
그러면, c1 과 c2 를 비교하여 (저울사용3)
(1-b-1) c1=c2 라면, c3 가 무겁다.
(1-b-2) c1> c2 라면, c1 이 무겁다.
(1-b-3) c1< c2 라면, c2 가 무겁다.
(1-c) 만약 ( c1,c2,c3) < A 라면, c1,c2,c3중 하나가 가볍다.
c1과 c2 를 비교하면, 셋 중 어느 것이 가벼운지 알 수 있다.
(2) 만약, A>B 라면, C 는 정상임을 알 수 있다.
이제 A를 (a1,a2) 와 a3, a4 로 나누고, B를 (b1,b2)와 b3, b4로 나누자.
이제 (a1,a2)+(b1,b2) 와 (c1,c2)+a4+b4 , 즉 저울 양쪽에 4개씩을 놓고,
무게를 비교하자. (저울 사용2)
(2-a) (a1,a2)+(b1,b2) = (c1,c2)+a4+b4 라면,
a3가 무겁거나 b3가 가볍거나이다.
이제 a3를 c1과 비교하자. (저울 사용3)
(2-a-1) a3=c1 이라면, b3 가 가벼운 것이다.
(2-a-2) a3> c1 이라면, a3 가 무거운 것이다.
a3 < c1 은 불가능.
(2-b) (a1,a2)+(b1,b2) > (c1,c2) +a4+ b4 라면,
(a1, a2) 가 무겁거나, b4 가 가벼운 것이다.
(A>B 이므로, a4 가 가볍거나, (b1,b2)가 무거울 수 없다.)
a1 과 a2 를 비교한다.
(2-b-1) a1= a2 라면, b4 가 가벼운 것.
(2-b-2) a1 > a2 라면, a1 이 무겁다.
(2-b-3) a1 < a2 라면, a2 가 무겁다.
(2-c) (a1,a2)+(b1,b2) < (c1,c2)+ a4+ b4 인 경우는
(b1, b2)가 가볍거나, a4 가 무거운 경우다.
역시 b1 과 b2 를 비교하면, 어느 경우 인지 알 수 있다.
(3) 만약, A<B 라면, 위의 경우에서 a와 b 를 뒤집어서 생각하는 것과 같다.
따라서, 어느 것이 무겁거나, 가벼운지 결정된다.
이 문제를 풀면서 의문이 생겼다.
구슬의 갯수가 3개일때는? 4 개일때는?
일반적으로 N개의 구슬 중 하나가 다를 경우,
이것을 알아내기 위해 필요한 저울질의 최소한의 횟수는 얼마일까?
댓글 없음:
댓글 쓰기