Intereting Posts

Distinguishing between symmetric, Hermitian and self-adjoint operators
find the value of limit
How do “Dummy Variables” work?
Two questions regarding Ordinal Numbers.
Countably compact paracompact space is compact
How to Solve Boolean Matrix System?
Why are real numbers useful?
Show that $p$ is prime if the following limit property holds
Is the number of prime ideals of a zero-dimensional ring stable under base change?
Definition of “Parallel along a curve” and “geodesic” in Chern's Lectures on Differential Geometry
A characterisation of quadratic extensions contained in cyclic extensions of degree 4
Group structure on pointed homotopy classes
Expected Ratio of Coin Flips
$F:C\to D$, $G:D\to E$, $G$ has an adjoint, $F$ is fully faithful and for each $Z$ there is $X$ s.t. $F(X) = H(G(Z))$: Does $F$ has an adjoint?
Closed subsets of $\mathbb{R}$ characterization

Possible Duplicate:

Optimal algorithm for finding the odd spheres

You have 12 balls and you know that they all weigh the same except for 1 which is heavier or lighter than all the others (you don’t know which though). How can you make sure you know which ball is the heaviest/lightest in only 3 weighings?

The way I approached it was to split up the 12 balls into three sets of 4 and weigh two of the sets. If the sets balanced the scale, then I know the ball I am looking for must be in the set of 4 balls not weighed, else, I disregard said set and arbitrarily choose the heaviest set of 4 (as opposed to choosing the lightest set). I split the heaviest set of 4 balls into 2 and weigh that… etc.

- What three odd integers have a sum of 30?
- What would have been our number system if humans had more than 10 fingers? Try to solve this puzzle.
- Chameleons Riddle
- What's the smallest number that we can multiply with a given one to get the result only zeros and ones?
- A Nim game variant
- Understanding Strategy:Minimum number of weighing to find the faulty bag

Repeating this process until all 3 tries have been “used up”, even if everything just so happened to be in your favor (the arbitrary choice you have in choosing the heaviest or lightest set happens to be the correct choice) in the end you still end up having to choose between 2 balls. A 50% chance is good, but I am wondering, is there a way to make sure 100%?

- How to solve 5x5 grid with 16 diagonals?
- Predicting Real Numbers
- Famous puzzle: Girl/Boy proportion problem (Sum of infinite series)
- Fun Geometric Series Puzzle
- How to check if a 8-puzzle is solvable?
- How Strong is an Egg?
- Putnam 1990: Problem A-4
- How many bananas can a camel deliver without eating them all?
- Square covered with tiles
- What is the name of the logical puzzle, where one always lies and another always tells the truth?

It’s hard to believe this classic puzzle isn’t already documented in MSE, but FWIW, here’s one of the standard “static” solutions. “Static” means that the weighings are fixed in advance – we know which coin (or ball, or whatever) goes on which arm of the balance at each step regardless of the outcomes of previous weighings. This seems like a harder problem to solve, but in fact, it makes the process of finding a solution somewhat easier than the more natural case-by-case analysis.

Create a 3-by-12 matrix. The rows correspond to weighings, the columns correspond to coins. Each entry in the matrix is either L (the coin goes on the left of the scale in this weighing), R (the coin goes on the right) or O (the coin is left out in this weighing).

Now if a coin is heavy, it will make all the weighings in which it has L to be left-heavy, all those in which it is R to be right-heavy, and all the ones where it’s O to be balanced. For a light coin it’s the other way around. So each pair of (coin, weight bias) creates a sequence of results, and you just need to make sure that all those sequences are different for all the (coin, bias) combinations. In other words, the columns of the matrix must all be different, and moreover, none of them should be inverses of each other (since if coin x is the inverse of coin y, you can’t tell a heavy coin x from a light coin y).

Here’s an example solution (I use +, – and blanks here instead of R, L and O since it’s easier to grasp I think) which has a little bit of structure making it easy to verify the requirements.

```
1 2 3 4 5 6 7 8 9 A B C
+ + - + - - + -
+ + + - - - - +
+ - + + - - - +
```

EDIT: to explain once again what all this means, in the first weighing we pit coins 1, 4, 6 and 10 against coins 5, 7, 9 and 12. The second weighing has 2, 4, 5, 11 against 6, 7, 8, 10 and the last one has 3, 5, 6, 12 against 4, 8, 9, 11. So the weighings are always 4 against 4, and as mentioned, the result of weighing #1 don’t matter at all for how we choose to handle the other weighings. It’s all static.

If coin 1 is heavy, for example, we’ll get “Left, balanced, balanced”. No other coin can do that by being heavy (there’s no other column like this one) and no other coin can do that by being light (since there’s no column that goes “- blank blank”).

Here is the first solution I came up with. There may be a cleaner one to be found.

Weigh four against four to start. If they are equal, you can easily find the odd ball from the remaining four by weighing against two known balls, then one known ball.

If the scales are uneven, let us call the lighter one scale 1 and the heavier scale 2. Keep three balls on scale 1, then exchange the fourth with a ball from scale 2. Remove the remaining three balls on scale 2 and replace them with known balls.

If the scales now balance, you know that the odd ball was removed from scale 2, and is heavier than the others. If scale 1 is still lighter, you know that the odd ball is one of the three kept balls on scale 1, and is lighter than the rest. If scale 2 is lighter, the odd ball must be one exchanged between the two scales.

In all three cases, you can determine the odd ball in one more weighing.

Alon’s answer is a good one, but it set me puzzling as to why it is that we can deal with 13 balls and not 14. After all, in three weighings there are 27 possible combinations (the scales can go either way, or be level). The answer for 13 balls allows us to discover the bad ball (13 options) and for twelve of these to say whether it is heavy or light – a total of 25 possibilities – what has happened to the missing two?

The problem is that we are constrained to use eight balls in each weighing – if we could use nine balls we would be able to use all the possibilities. This can be achieved if we have an extra ball, X, which we know to have the correct weight. With balls ABCDEFGHIJKLMN and X weigh as follows:

- ABCDX v IJKLM
- AEFIX v CDHLM
- CGIJL v FHKMX

This scheme enables us to identify whether any of the balls ABCDEFGHIJKLM is the bad one, and if so whether it is heavy or light. If all the weighings come out level, then N is the bad one, but we don’t know whether it is heavy or light.

- If $a^2+b^2+c^2+d^2=4$ so$\sum\limits_{cyc}\frac{a^3}{b^2+c^2}\geq2$
- How to prove that Lebesgue outer measure is translation invariant?
- Structure Theorem for abelian torsion groups that are not finitely generated
- Relations between the maximum matching, minimum vertex cover, maximum independent set, and maximum vertex biclique for a bipartite graph
- Pairs of points exactly $1$ unit apart in the plane
- Induction: $\sum_{k=0}^n \binom nk k^2 = n(1+n)2^{n-2}$
- The Hodge $*$-operator and the wedge product
- Are there mathematical objects that have been proved to exist but cannot be described in words?
- How to verify this limit?
- A generalization of a divisibility relation for Fibonacci numbers
- How is the value of $\pi$ ( Pi ) actually calculated?
- Are all solutions to an ordinary differential equation continuous solutions to the corresponding implied differential equation and vice versa?
- Proof of $m \times a + n \times a = (m + n) \times a$ in rings
- Convergence of the series $\sqrtn-1$
- Proving the Möbius formula for cyclotomic polynomials