By 이 문제는 제가 대학교 다닐 때 하이텔의 수학동호회에서 접한 문제입니다.
이후 어떤 커뮤니티 사이트에서 이 문제를 다시 발견했습니다.
제가 푼 풀이도 밑에 있습니다. 커뮤니티 사이트에서 풀었던 답변입니다.
제 풀이를 보기 전에 우선 스스로 풀어보시기 바랍니다.
참고로 이 문제를 저에게 낸 분은 1시간 안에 풀면 천재라고 했었습니다.
하지만 사실 10분만에 풀리는 문제였습니다.
물론 모든 분이 다 1시간 안에 풀 수 있지는 않을 것입니다.
단지 1시간 안에 푼다고 천재도 아니란 말씀이죠. ^^
이 글을 다시 올려야 하다니……^^;;
다사리 님의 글이 틀린 부분이 있는 것 같아서 이 글을 올려봅니다…
처음 풀 때는… 15분 걸렸는데… 다시 풀려니까… 시간 단위로 나오는군요..
예전에 푼 기억이 새로 푸는데 방해가 되는 것 같습니다…^^
문제 ) 똑같이 생긴 구슬 12개가 있는데 그것 중에 불량품 1개가 있어서 그것은
무게가 틀리다.. 이것을 눈금이 없는 양팔저울을 최소한 사용해서 찾아라.
(단 불량품 무게는 무거운지 가벼운지 알 수 없다.)
[#M_풀이 보기|풀이 접기|풀이 )
음..문제 풀이에 앞서서…
두 번으로 몇 개의 구슬을 확인할 수 있는지 한 번 보죠…
우선 한 번으로 확인하는 것은 두 개죠..^^;;(비교 대상이 없으므로…^^)
그리고 무겁다 가볍다가 있으면 세 개까지 가능합니다…
그렇담….
두 번으로는….
음…구슬이 a,b,c,d가 있다면…^^
우선 a,b를 저울에 올여놓구여….
기울어진다면 a,c를 비교해 보면…a,b,c중에 답이 어느것인지는 쉽게 알 수
있고, 결과적으로 나머지 하나인 d를 포함 4개의 구슬을 두 번 저울 사용으로
불량구슬을 알 수 있다는 것입니다.
위에서 안 기울어진다면 역시나 똑같이 a,c를 비교하면 역시 알 수 있죠…^^;;
세 번을 사용하는 방법에서..^^;;
음냐…
다사리님처럼 세 그룹으로 나눠서 A,B,C라고 하면… 한 그룹이 4개죠..^^
A=B라 하면 당연 C에 불량이 있고, 그럼 C 안에서는 두 번이면
불량을 찾을수 있으므로 결국 3번으로 찾습니다..
A ≠ B 인 경우에는…
우선 기울어진 쪽을 기억해야 합니다…
우선 A쪽이 내려간다면….
A에서 2개+1개, B에서 2개를 뽑죠……
그래서 C의 3개와 A에서 뽑은 1개를 저울 한 쪽에 놓구서
반대쪽에 위에서 뽑은 A에서 뽑은 2개와 B에서 뽑은 2개를 놓습니다.
경우1, C3+A1쪽이 내려간다면….. 불량품은 무게가 무거우며 A에서 뽑은 1개이거나
가벼우며 B에서 올려놓은 2개 중의 한 개가 불량이다…
→ 1번 더 사용으로 알 수 있죠..(B에서 뽑은 두 개를 재보면….)
경우2, A2+B2쪽이 내려간다면…. 불량품은 무게가 무거우며 여기서 A에서
올려놓은 2개 중에 답이 있다…(이것은 1번으로 알 수 있다.)
경우3. 저울이 기울지 않았다면…….
나머지 저울에 올리지 않은 A에서의 1개와 B에서의 2개 중에 답이 있으며
이중에서 B에 있는 2개를 저울에 올리면 불량품을 알 수 있다…
_M#]
이렇게 해서 답을모두 할 수 있습니다…^^
아~ 여기 12개짜리문제 있네요. 제블로그에서도 dlimpid 님께서 12개짜리 문제에 대한 해법이 소개된 사이트를 댓글로 알려주신적이 있어서 잠깐 봤었어요. 13개중에 하나 찾아내는 것도 재미있답니다. 그리고 저도 이쪽으로 트랙백 날려요~*
음. 이제 일반적으로 n개의 구슬이 있고 그중 k개가 불량일 때 저울을 써야 하는 최소 횟수 P(n, k)를 찾아내는 규칙을 찾아보아요. ㅋㅋ
아니여…. 그거 예전에 수학과 사람이 푼 거 봤는데, 제가 손댈 수준을 넘더라구요. ㅎㅎㅎ
재미있네요..^^ 구슬이 많이지고 복잡한 저울문제 일수록 주먹구구식으로 풀기에는 시간이 많이 걸립니다….. 무엇인가 전략이 필요한데 이런 것은 어떨까요..? 예를 들어 9개의 구슬이 있는데 이중 2개가 무게가 다르다(겨벼울수도 혹은 무거울 수도).. 저울은 오른쪽 왼쪽으로 기울 수 있고 평형할 수도 있으므로 3가지 경우가 있을 수 있습니다. 문제에서 구슬이 가질 수 있는 총 경우는 9C2 *2 = 72 아마도 저울을 잘 이용하면 저울을 4번 이용하면(3^4) 답을 찾을 수 있겠네요…
만약 첫번째 시도에서 양팔저울에 각각 한개씩 양쪽에에 올린다면… 저울이 평행이 되면 이것은 이두개가 무게가 다른 두개거나 나머지 7개 중에 무게가 다른 2개가 있다는 뜻이 되므로 7C2*2 + 1 *2 = 44가지 경우가 되므로 이 다음에 아무리 잘 해도 나머지 3번으로는 해결 불가합니다…
양팔 저울에 구슬을 2개씩 올릴 경우 저울이 평행한 것은 양쪽 저울에 무게가 다른 구슬 하나씩 올라가거나 다른 5개중 2개가 무게가 다른 경우 (2C1*2C1*2 + 5C2 = 28가지 >3^3) 이 경우도 해결 불가 합니다… 이쯤이면 이 풀이가 어떤 전략인지 잘 알 수 있을 겁니다… 저울의 어떤 결과도 (평형,오른쪽으로 기울어짐,왼쪽으로 기울어짐) 경우의 수가 3^남은 저울 회수 이상이면 잘 못된 방법이란 뜻입니다….
이보다 훨씬 복잡하답니다. ㅜㅜ
이보다 훨씬 복잡하다는 게 무슨 뜻인지.. 저는 위의 전략으로 본문의 문제를 풀 수 있었는데요… 저울질 3번이면 찾을 수 있죠.. 물론 저울질 2번에 찾는 방법이라면 모를까.. 저는 2번으로는 불가능 하다고 생각합니다. 구슬이 가능한 경우는 24가지이니까요
아…이 문제는 이렇게 풀 수 있지만, 일반적인 풀이방법(n개 중에 k 개라거나… 할 때의 풀이방법)은 이렇게 쉽게풀리지는 않더라구요. ^^
풀이에 어떤 원칙이 있을까요..? 사실 저 앞의 원칙도 n개중 k개 같은 저울문제를 일반화 시킨 문제 풀이할 때 적용할 원칙은 없을까.. 해서 생각해본 것 입니다. 어짜피 오른쪽으로 기울 든 왼쪽으로 기울든 대칭적이나까 저울이 평형인 경우의 수만 계산하면 가우려 졌을 때 경우의 수도 계산 가능하고요… 사실 제가 위에 언급한 원칙은 모든 해결가능한 양팔저울 문제에 다 적용가능한 . 어쩌면 당연한 원칙일 겁니다… 역설적으로 이런 범용성은 그만큼 반짝 빛나는 묘수같은 그런 것이 없다는 뜻이기도 하겠죠… 더 좋은 전략은 어떤 것들이 있는지… 궁금하고… 배워보고 싶네요… (참.. n 개중 k개가 무게가 다른 구글을 찾는 문제를 일반적으로 푸는 것도 가능하다고 생각됩니다… 물론 번거로운 계산이 필요하겠지만요….)
이런 문제는 수학과에서 해결해줘야 할 문제가 아닐까 합니다만…
근데 수학과에선 제 블로그에 방문하질 않네요. ㅎ
구글이 n개씩이나 있으면 지구정복도 꿈은 아니겠네요 :D
n=1이다 반전이…ㅋㅋㅋ
원래 이렇게 답이 간단히 나오는 문제가 아닙니다. 1시간 이내에 풀면 천재라는 말이 괜히 나온게 아니죠.
원 문제는 불량구슬을 찾을 뿐만 아니라, 그 불량구슬이 다른 구슬들보다 무거운지 가벼운지까지 밝혀야 하는 문제입니다.
그건 풀이과정 중에 자연스럽게 나오는 결과인데요. ^^