Trouvez la balle étrange hors de $18$ boules, où $17$ peser la même chose.
Il existe de nombreuses variantes de ce problème. Celui avec lequel je travaille est
Il y a $17$ balles qui pèsent le même poids, et $1$balle qui pourrait peser plus lourd ou plus léger que l'autre$17$. De combien de pesées sur une balance avez-vous besoin pour déterminer l'étrange et s'il est plus lourd ou plus léger?
Le cas le plus simple où vous savez si la balle impaire est plus lourde ou plus légère peut être trouvé dans $3$pèse. L'idée est de diviser le$18$ balles en groupes de $6$, dire, $6A$, $6B$, $6C$. Peser$6A$ et $6B$sur une échelle. S'ils s'équilibrent, alors$6C$a l'étrange. S'ils ne s'équilibrent pas, et$6A$ est plus bas sur l'échelle, alors $6A$ a la balle la plus lourde, et de manière analogue pour $6B$. Il faut donc un maximum de$1$ peser pour déterminer le groupe de $6$avec la balle la plus lourde. Ensuite, vous pouvez diviser ce groupe de$6$ dans $3$ groupes de $2$, et en utilisant la même idée, vous pouvez trouver le groupe impair de $2$ avec un maximum de $1$peser. Ensuite, il vous reste un groupe de$2$ et il faut $1$peser pour déterminer la balle la plus lourde. Donc, au total, vous avez besoin$3$ pesez ins pour ce cas.
Mais la variante la plus difficile de ce problème est celle où vous ne savez pas si la balle impaire est plus lourde ou plus légère. Dans ce cas, j'ai trouvé que vous avez besoin d'un maximum de$5$ essaie de trouver l'étrange ainsi que de déterminer s'il est plus lourd ou plus léger, mais je n'ai aucune idée si c'est correct, ou comment justifier qu'il s'agit du nombre minimum d'essais maximum.
L'idée est similaire au problème précédent. Diviser$18$ balles dans $6A$, $6B$, $6C$. Cette fois, il faut au maximum$2$ essaie de trouver le groupe de $6$. ie, peser$6A$ et $6B$ sur une échelle, s'ils correspondent, alors $6C$est le groupe étrange. Si$6A$ et $6B$ne correspond pas, alors nous avons besoin d'un poids supplémentaire pour déterminer l'étrange. Par conséquent,$2$ essaie.
Maintenant, une fois que nous avons trouvé l'étrange groupe de $6$, on applique la même idée, ce qui en prend une autre $2$essaie (maximum). Puis nous nous retrouvons avec un groupe de$2$. Il faut exactement$1$ peser parce que tu peux prendre $1$ balle du groupe de $2$ et pesez-le avec l'un de l'autre $16$boules que nous savons sont les. Si cette balle est la même, alors la balle restante est la balle impaire. Il faut donc un maximum de$2+2+1 = 5$essaie de trouver cette balle étrange. Nous n'avons pas besoin d'un poids supplémentaire pour déterminer si cette balle restante est plus lourde ou plus légère.
C'est parce que lorsque nous avons trouvé le groupe de $6$, et le groupe suivant de $2$, nous avons pris le maximum de $2$essaie. Si cela prend$2$ essaie de trouver le groupe impair de $6$ dehors, alors cela signifie la deuxième pesée de la $2$ Les essais nous permettent de déterminer si cette balle étrange est plus lourde ou plus légère.
Par exemple, considérez $6A$, $6B$, $6C$encore. Disons qu'on pèse d'abord$6A$ et $6B$et constatent qu'ils ne pèsent pas le même Puis on pèse$6C$ soit $6A$ ou $6B$. Si nous pesons$6A$ avec $6C$ et trouve ça $6A$ ne correspond pas $6C$, puis $6A$ est l'étrange, mais aussi si $6A < 6C (6A > 6C)$, alors on sait $6A$ a une balle qui pèse moins (plus).
Est-ce l'approche la plus optimale ou existe-t-il une méthode qui ne prend que $4$peser? Mon instinct me dit qu'il devrait y avoir un$4$ approche de pesée.
le $12$-ball variante du problème et sa solution est publiée dans http://www.mytechinterviews.com/12-identical-balls-problem. Vous pouvez voir qu'ils appliquent une approche analogue en cassant le$12$ balles dans $3$ groupes de $4$, mais ils appliquent un mélange et une correspondance intéressants pour trouver l'étrange en seulement $3$ se déplace.
Réponses
Je n'ai pas vérifié la solution pour le classique $12$ version boules http://www.mytechinterviews.com/12-identical-balls-problem. Mais si cela fonctionne, cela conduit trivialement à un$4$ solution de pesage pour $18$ étui à balles.
Vraiment, étant donné le classique, il y a très peu de travail supplémentaire à faire!
Vous pesez d'abord $3A$ contre $3B$. S'ils sont déséquilibrés, dites$3A > 3B$, vous pouvez le découvrir avec $3A$ contre $3C$ (tout $3C$sont bonnes) si la mauvaise balle est plus lourde ou plus légère. Alors vous pouvez sûrement trouver le coupable parmi un groupe de$3$avec juste une pesée de plus. Total$3$ pesées.
Et si $3A = 3B$, alors tu es réduit au classique $12$-bille problème qui peut être résolu avec $3$ pesées supplémentaires, pour un total de $4$.
Autres réflexions: En fait, $4$ les pesées peuvent résoudre $30$ balles, pas seulement $18$.
Dans ce qui précède, le $3A \neq 3B$ la branche mène toujours à $3$pesées totales, ce qui est un gaspillage. Imagine que tu as$9+9+12 = 30$des balles. La première pesée peut être$9A$ contre $9B$. S'ils sont déséquilibrés, encore une seconde$9A$ contre $9C$ (tout bon) vous dira si le mauvais est lourd ou léger, puis vous pouvez utiliser $2$ plus de pesées pour trouver le coupable parmi $9$ (recherche tri-naire), pour un total de $4$ pesées.
Encore plus loin, il y a des années, j'ai résolu un cas (une extension du classique) où $13$ balles (lourdes / légères inconnues) peuvent être résolues avec $3$ pesées, à condition d'avoir accès à des balles supplémentaires connues pour être bonnes - IIRC dont vous avez besoin $2$ces bons extras. Ça signifie$9+9+13 = 31$ peut être résolu avec $4$ pesées, coz dans le $9A=9B$ cas où il vous reste $13$ suspects, mais de nombreuses balles supplémentaires connues pour être bonnes.
Je soupçonne même $31$ n'est pas la limite (pour $4$pesées). Quand tu pèse$9A$ contre $9C$, seuls deux résultats peuvent se produire (puisque $9A > 9B$). C'est très inefficace et une exploitation supplémentaire pourrait être possible ...
Vous connaissez probablement le classique lié avec $n$ pesées il n'y a que $3^n$ résultats possibles, donc avec $n=4, 3^n = 81$, tu ne peux pas résoudre $\ge 41$ des balles ($\ge 82$résultats). je ne dis pas$40$ est réalisable, mais il existe un écart important entre $31$ et $40$...
Pesage 1 : Peser$1$-$6$ contre $7$-$12$. Si le résultat est équilibré , alors nous savons que la balle impaire est dans le set$13$-$18$, qui prend (en effet) $3$plus de mesures pour un total de 4 pesées.
Si la première pesée est déséquilibrée , supposons sans manque de généralité que$1$-$6$ est plus lourd que $7$-$12$. Puis effectuez ...
Pesage 2 : Peser$1$-$3$ contre $7$-$9$. Si le résultat est équilibré , la balle impaire est$\{ 4, 5, 6, 10, 11, 12 \}$, qui prend en effet $3$plus de pesées, pour un total de 5 pesées.
Si au contraire le résultat est déséquilibré , supposons sans perte de généralité que$1$-$3$ est plus lourd que $7$-$9$. Ensuite, nous savons que la balle impaire est dans cet ensemble de six, ce qui nécessite en effet deux pesées supplémentaires pour un total de 5 pesées.