| [ QuizWit ] in KIDS 글 쓴 이(By): outsider (하얀까마귀) 날 짜 (Date): 2007년 2월 7일 수요일 오후 10시 04분 14초 제 목(Title): Re: 이거 어떻게 풀죠? 가능한 최대 갯수의 upper bound만이라면 3진법으로 증명이 가능하죠. a1 a2 a3 ... a13 의 동전이 있다고 하면 가능한 상태는 전부 26가지입니다. (a1이 무거운 가짜, a1이 가벼운 가짜, a2가 무거운 가짜, ..., a13이 가벼운 가짜) 여기서 저울을 한번 사용할 때마다 저울은 '왼쪽이 무겁다', '같다', '오른쪽이 무겁다'의 세 가지 답중에 하나를 주기 때문에 저울에 동전들을 다는 것은 저울에게 질문을 하는 것과 같습니다. 그래서 예를 들어서 3번 질문을 한다면 최대 3^3=27가지의 상태를 판별하는 것이 upper bound 입니다. 문제에서는 동전의 갯수x2 의 상태가 존재하니까 n번의 저울질로 잴 수 있는 절대적인 상한은 3^n-1/2개 입니다. 질문하는 방식이 무제한이라면 14개(28가지의 상태)의 동전 중에서도 하나를 골라내는 게 가능하겠지만 저울로 재는 방법에는 제한이 있어서 그렇게는 안 되지요. -- @< //) `//<_ 하얀까마귀 - http://outsider.egloos.com |