2
$\begingroup$

You are given 19 identical-looking balls and a two-sided scale. One of the balls is different, either lighter or heavier than the others. Using 4 weighings of the scale, how can you determine which ball is odd and whether it's lighter or heavier?(in a systematic way)

$\endgroup$
5
$\begingroup$

Here is one obvious strategy

Choose any twelve balls, divide them into two groups of six and compare the two groups using the scales. If the scales tips one way (is not balanced) then we know that this group of 12 contains the odd ball and we can use any of the strategies detailed in the answers to this question to deduce the odd ball and its relative weight in three more weighings.

Otherwise, if the scale is balanced then we know the odd ball is one of the remaining 7. In this case, we can just add 5 balls from the first group to make 12 and then repeat one of the strategies detailed in the answers to this question.

Note

This quick generalisation gives us a strategy of deducing the odd ball up to a set size of 24.

A very pleasant solution to the 12 balls, 3 weighings question was referenced by Gareth McCaughan here which I have just copied into the spoiler text below for quick reference

Some of the existing answers to this ancient question are excellent, but there's one famous answer that I think deserves mention here. It comes from an article in Eureka, the annual magazine of the University of Cambridge's student mathematical society, written by C A B Smith under the pseudonym of "Blanche Descartes".

It has two very nice features. The first is that it's an "unbranching" solution: you don't need to change what you do on later weighings depending on the results of earlier ones. The second is that once you've seen it it's almost impossible to forget.

Smith's solution is written entirely in verse and includes an explanation of how it all works, but I shall quote only the actual answer. "F" here is our protagonist Professor Felix Fiddlesticks, whose mother has asked him for help with the puzzle. I have made some trifling changes to the original formatting.

F set the coins out in a row
And chalked on each a letter, so,
To form the words: F AM NOT LICKED
(An idea in his brain had clicked.)

And now his mother he'll enjoin:
"MA, DO / LIKE
ME TO / FIND
FAKE / COIN!"

Each of the three lines of F's injunction describes one weighing. When you've done them all, the results uniquely determine which coin is fake and in which way.

Further reference

I think that for 4 weighings we can actually find the odd ball in a set of size $\frac{3^4 - 3}{2} = 39$.
A good discussion of the general problem is given here

| improve this answer | |
$\endgroup$
  • $\begingroup$ Check edit to verify it's what you mean. $\endgroup$ – Chris Cudmore Sep 23 at 16:01
  • 1
    $\begingroup$ @ChrisCudmore Yes, that is what I meant, thanks for the edit. $\endgroup$ – hexomino Sep 23 at 16:02
  • $\begingroup$ @hexomino I needed a solution where I can apply it using truth table. I made it but I had to do two cases(two tables - by dividing the balls into two groups 12-7) I was wondering if I there was a method that can do it using only 1 table? $\endgroup$ – Samo Mo Oct 4 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.