밖으로 이상한 공 찾기 $18$ 공, 어디 $17$ 같은 무게.
이 문제에는 여러 가지 변형이 있습니다. 내가 함께 일하는 사람은
있습니다 $17$ 무게가 같은 공, $1$무게를 달 수 있습니다 볼 중 하나를 다른 것보다 더 무거운 또는 가벼운$17$. 밸런싱 스케일에서 얼마나 많은 무게를 측정해야 이상한지, 더 무거운 지 가벼운 지 결정해야합니까?
이상한 공이 더 무겁거나 가벼운 지 아는 더 간단한 경우는 다음에서 찾을 수 있습니다. $3$무게. 아이디어는$18$ 공을 그룹으로 $6$, 말하십시오, $6A$, $6B$, $6C$. 달다$6A$ 과 $6B$규모. 그들이 서로 균형을 이루면$6C$이상한 것이 있습니다. 서로 균형이 맞지 않으면$6A$ 규모가 더 낮 으면 $6A$ 더 무거운 공을 가지고 있습니다. $6B$. 따라서 최대$1$ 그룹을 결정하기 위해 무게 $6$더 무거운 공으로. 그런 다음이 그룹을$6$ 으로 $3$ 그룹 $2$, 같은 아이디어를 사용하여 이상한 그룹을 찾을 수 있습니다. $2$ 최대 $1$달다. 그런 다음 그룹이 남았습니다.$2$ 그리고 걸립니다 $1$무게가 더 무거운 공을 결정합니다. 따라서 전체적으로$3$ 이 경우에 대한 무게.
그러나이 문제의 더 어려운 변형은 홀수 공이 더 무겁거나 가벼운 지 알 수없는 경우입니다. 이 경우에는 최대$5$ 이상한 것을 찾아 내고 그것이 더 무겁거나 더 가벼운 지 결정하려고 시도하지만 이것이 올바른지 또는 이것이 최대 시도 횟수라는 것을 정당화하는 방법을 모릅니다.
아이디어는 이전 문제와 유사합니다. 나누기$18$ 공에 $6A$, $6B$, $6C$. 이번에는 최대$2$ 그룹을 찾으려고 $6$. 즉, 무게$6A$ 과 $6B$ 규모에 따라 일치하면 $6C$이상한 그룹입니다. 만약$6A$ 과 $6B$일치하지 않으면 이상한 것을 결정하기 위해 추가 가중치가 필요합니다. 그 후,$2$ 시도합니다.
이제 이상한 그룹을 발견하면 $6$, 우리는 동일한 아이디어를 적용합니다. $2$시도 (최대). 그런 다음 우리는$2$. 정확히 걸립니다$1$ 당신이 걸릴 수 있기 때문에 무게 $1$ 그룹에서 공 $2$ 다른 한쪽으로 무게를 재세요 $16$우리가 아는 공이 있습니다. 이 공이 같으면 나머지 공은 홀수 공입니다. 따라서 최대$2+2+1 = 5$이 이상한 공을 찾으려고합니다. 남은 공이 더 무겁거나 가벼운 지 판단하기 위해 추가 계량이 필요하지 않습니다.
이것은 우리가 그룹을 발견했을 때 $6$및 후속 그룹 $2$, 우리는 $2$시도합니다. 걸리는 경우$2$ 이상한 그룹을 찾으려고 $6$ 밖으로, 그러면 두 번째 무게를 의미합니다 $2$ 시도를 통해이 홀수 공이 더 무겁거나 가벼운 지 결정할 수 있습니다.
예를 들어 $6A$, $6B$, $6C$다시. 먼저 체중을 측정한다고$6A$ 과 $6B$무게가 같지 않다는 것을 알게됩니다. 그런 다음 우리는 무게$6C$ 어느 쪽이든 $6A$ 또는 $6B$. 무게가 나가면$6A$ 와 $6C$ 그리고 그것을 찾아 $6A$ 일치하지 않습니다 $6C$, 다음 $6A$ 이상한 것입니다. $6A < 6C (6A > 6C)$, 그러면 우리는 $6A$ 무게가 더 적은 공이 있습니다.
이것이 가장 최적의 접근 방식입니까 아니면 $4$무게? 내 직감은$4$ 무게 측정.
그만큼 $12$-볼 변형 문제와 그 해결책은 http://www.mytechinterviews.com/12-identical-balls-problem. 당신은 그들이 유사한 접근 방식을 적용하는 것을 볼 수 있습니다$12$ 공에 $3$ 그룹 $4$, 그러나 그들은 흥미로운 믹스와 매칭을 적용하여 이상한 것을 찾습니다. $3$ 이동합니다.
답변
클래식에 대한 솔루션을 확인하지 않았습니다. $12$ 공 버전 http://www.mytechinterviews.com/12-identical-balls-problem. 그러나 그것이 작동한다면, 그것은 사소하게$4$ 계량 솔루션 $18$ 공 케이스.
실제로 클래식을 고려할 때 할 일이 거의 없습니다!
먼저 체중 $3A$ vs $3B$. 균형이 맞지 않으면 다음과 같이 말하십시오.$3A > 3B$, 당신은 $3A$ vs $3C$ (모두 $3C$좋은) 나쁜 공이 더 무거운 지 가벼운 지. 그럼 확실히 당신은 그룹에서 범인을 찾을 수 있습니다$3$한 번만 더 칭량하면됩니다. 합계$3$ 무게.
그리고 만약 $3A = 3B$, 그러면 당신은 고전으로 축소됩니다 $12$-해결 될 수있는 공 문제 $3$ 추가 계량, 총 $4$.
추가 생각 : 사실, $4$ 계량으로 해결할 수 있습니다. $30$ 공,뿐만 아니라 $18$.
위의 $3A \neq 3B$ 분기는 항상 $3$총 계량은 낭비입니다. 당신이 가지고 있다고 상상해보십시오$9+9+12 = 30$불알. 첫 번째 계량은$9A$ vs $9B$. 균형이 맞지 않으면 다시 한 번$9A$ vs $9C$ (all good) 나쁜 것이 무겁거나 가벼운 지 알려주고 다음을 사용할 수 있습니다. $2$ 범인을 찾기 위해 더 많은 무게 측정 $9$ (삼진 검색), 총 $4$ 무게.
더 나아가, 몇 년 전에 나는 고전적인 것의 확장판 인 사건을 해결했습니다. $13$ 공 (알 수없는 무거운 / 경량)은 다음으로 해결할 수 있습니다. $3$ 좋은 것으로 알려진 추가 볼에 액세스 할 수있는 경우 계량-필요한 IIRC $2$좋은 엑스트라. 이것은$9+9+13 = 31$ 로 해결할 수 있습니다 $4$ 무게, coz에 $9A=9B$ 당신이 정말로 남아있는 경우 $13$ 용의자이지만 좋은 것으로 알려진 많은 추가 공.
나는 심지어 의심한다 $31$ 한계가 아닙니다 ( $4$무게). 몸무게 할 때$9A$ vs $9C$, 두 가지 결과 만 발생할 수 있습니다 ( $9A > 9B$). 이것은 매우 비효율적이며 추가 악용이 가능할 수 있습니다.
당신은 아마 고전적인 경계를 알고있을 것입니다 $n$ 무게는 $3^n$ 가능한 결과, 그래서 $n=4, 3^n = 81$, 당신은 해결할 수 없습니다 $\ge 41$ 공 ($\ge 82$결과). 나는 말하지 않는다$40$ 달성 할 수 있지만 $31$ 과 $40$...
계량 1 : 계량$1$-$6$ 대 $7$-$12$. 결과가 균형을 이루면 세트에 홀수 공이 있음을 알 수 있습니다.$13$-$18$, (실제로) $3$총 4 개의 칭량에 대한 더 많은 측정 .
첫 번째 계량이 불균형 한 경우 일반성이 부족하지 않고$1$-$6$ 보다 무겁다 $7$-$12$. 그런 다음 수행 ...
계량 2 : 계량$1$-$3$ 대 $7$-$9$. 결과가 균형을 이루면 홀수 공이$\{ 4, 5, 6, 10, 11, 12 \}$, 실제로 걸립니다 $3$더 많은 계량, 총 5 회 계량.
그 대신 결과가 불균형 이라면 일반성을 잃지 않고$1$-$3$ 보다 무겁다 $7$-$9$. 그런 다음 우리는 이상한 공이 6 개 세트에 있다는 것을 압니다 . 총 5 개의 무게를 측정하려면 실제로 두 번 더 무게를 측정해야합니다 .