Le 4 mai 2021, la plateforme Yahoo Questions/Réponses fermera. Elle est désormais accessible en mode lecture seule. Aucune modification ne sera apportée aux autres sites ou services Yahoo, ni à votre compte Yahoo. Vous trouverez plus d’informations sur l'arrêt de Yahoo Questions/Réponses et sur le téléchargement de vos données sur cette page d'aide.
Weighted balls in bins strategy?
Here's a rather simple problem, but it's fairly cute and open to a whole gamut of possible extension problems.
Consider three bins. Each bin contains many balls. In one of the bins, each ball weighs 2, in another bin each ball weighs 3, and in the last each weighs 5 [units are arbitrary]. We don't know which bin is which.
Find a way to take determine which bin is which with only one weighing. You may take as many balls from as many bins as you wish.
Bonus: since that should be fairly easy, can you find a description of ALL such strategies?
A couple examples are probably in order.
If I take x balls from one of the bins, I find weight 2x, 3x, or 5x; then I know the weight in the bin which I chose from, but not which of the other two bins is which. So this won't work.
If I take one ball from each bin, I get a weight of 10, but this doesn't help at all.
But not any prime number of balls will work; for instance here 3,1 doesn't work (3*3+2*1=3*2+1*5). It isn't hard to argue that we need to choose x balls from one bin and y from another (and none from the last); for which pairs (x,y) does this work?
The generalizations to multiple bins and with different weights of balls is interesting, but I'm more interested presently with a general solution to this case.
2 réponses
- ☮ VašekLv 5il y a 1 décennieRéponse favorite
The condition is that ax + by + cz must be unique for any permutation (a,b,c) of (2,3,5). x, y and z denote the number of balls taken from each bin. This makes 15 inequalities. However, we don't need to list them all because many of them will be obtained by permutation of letters in some partial result. For this purpose, it is sufficient to select one fixed variant of the LHS of the inequality, say 2x + 3y + 5z:
2x + 3y + 5z ≠ 2x + 5y + 3z
2x + 3y + 5z ≠ 3x + 2y + 5z
2x + 3y + 5z ≠ 3x + 5y + 2z
2x + 3y + 5z ≠ 5x + 2y + 3z
2x + 3y + 5z ≠ 5x + 3y + 2z
Next, we'll cancel the maximal common coefficient of each unknown in each inequality (e.g., we'll subtract 2x + 3y + 3z from the first inequality and so on):
2z ≠ 2y
y ≠ x
3z ≠ x + 2y
y + 2z ≠ 3x
3z ≠ 3x
Simplifying further, no two unknowns can be equal. There is one and only one more condition,
z ≠ 1/3*x + 2/3*y (including all permutations).
This condition means that no unknown can lie between the other two exactly in the point where it splits their difference in a 1:2 ratio. This excludes combinations like (0,1,3) (which you also found not to work) or (0,2,3).
If you fix z = 0, as you wrote in the Additional details, the solution rewrites to
x ≠ 0, y ≠ 0, x ≠ y,
y ≠ 3x, x ≠ 3y.
- Anonymeil y a 1 décennie
Take two from one bin and one from another. I won't bore you with all of the combinations.
As long as the bins have balls whose weight is a prime number this generalizes - assuming that you take a prime number of balls from all but one of the bins..
Source(s) : Gerry
