1. 21g, 22g, 23g, 24g, 25g, 26g짜리 동전이 있다. 양팔저울을 이용하여 각 동전의 무게를 알려면 최소 몇 번의 저울질이 필요한가?
2. 1g, 2g, 3g, 4g, 5g, 6g짜리 동전이 있다. 양팔저울을 이용하여 각 동전의 무게를 알려고 할 때 필요한 저울질 횟수는 1번의 경우와 같을까? 아니라면 최소 몇 번의 저울질이 필요한가?
좋아요
0
글쎄요
0
어려워요
2
-
어렵네요 일단 부분적인 알고있는 바를 적어보겠습니다.
양팔 저울에 언제나 양 쪽에 각각 한 개씩만의 동전을 올려놓는다고 하면 10번이 필요합니다. 10번으로 하는 방법은 각 동전에 임의의 라벨을 붙이고 https://en.wikipedia.org/wiki/Merge-insertion_sort 를 하면 됩니다. 10번이 필요한 이유는 임의의 라벨을 붙였을 때 가능한 가짓수가 6! = 720이고 가능한 관측결과는 양쪽 중 한 쪽이 무거운 경우뿐이므로 2가지이기 때문에 9번 이하의 관측으로는 512개 초과의 가짓수를 가지는 경우를 분류할 수 없어서 최소 10번이 필요합니다.
하지만 실제 양팔 저울에는 여러 개의 동전을 올려놓을 수 있으니까 비교를 했을 때 양쪽의 무게가 같을 수도 있고 따라서 실제 답은 10번보다 적을 수도 있겠네요.
1번은 무게 상 양쪽의 동전 개수가 다르면 더 많은 쪽이 무거우므로 언제나 같은 개수를 올려놓고 하는 경우만 생각해도 됩니다.
2번은 1번과 마찬가지 방법을 사용해도 풀리지만 서로 다른 개수를 올려놓는 가능성도 있으므로 최소 회수가 같거나 적겠네요.
저도 10번 안에 할 수 있는 방법을 찾았지만, 9번 안에 할 수 있는 방법은 찾지 못 했습니다. 안 된다는 증명도 쉽지 않더라고요... 시간 날 때 함께 도전해봅시다!
