19 balls and a scale [duplicate]

Question

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)

Answer 1

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

Answer 2

Summary : Using the first 2 weighings, find out whether the odd ball is heavier or lighter than the rest. Also, with the help of these 2 weighings, narrow down the candidates which contain the odd ball to 9 or less. It is then easy to find out which is the odd ball using 2 more weighings.

Now the details : We have one odd ball. Let us call the rest of the balls, normal balls.

Put 5 balls on one pan , 5 balls on the other pan and keep the rest of the 9 balls out and make the first weighing .

Case 1) The scale is in balance. We now know that the odd ball is among the 9 balls that have been kept outside and all the 10 balls that have just been weighed are normal balls and have the same weight.

Now, take any 9 balls from these 10 balls that were just weighed and put them on the left pan. Take the 9 balls that were kept outside and put them on the right pan. Now, do the second weighing. If the right pan goes down then we know that the odd ball is heavier than the rest. If the right goes up then we know that the odd ball is lighter than the rest.

We now know whether the odd ball which was present on the right pan is heavier or lighter than the normal balls. We now have to identify which one is the odd ball among these 9 balls. This can be done in just 2 more weighings using this method. Thus, a total of 4 weighings are needed for case 1.

Case 2) Scale is not in balance. Odd ball is among these 10 balls and the 9 balls that were kept outside during the first weighing are all normal balls. Take the 9 balls that were kept outside during the first weighing and put them in the left pan. Take any 9 balls from the 10 balls that were weighed during the first weighing and put them on the right pan. We now have 18 balls on the scale and one outside.

Possibility 1: Scale is in balance. This means that the odd ball is the one that was kept outside. Put this ball on one pan of the scale and put a normal ball on the other pan. If the odd ball pan is below the pan containing the normal ball then the odd ball is heavier than the normal ball. If the odd ball pan is above the pan containing the normal ball then the odd ball is lighter than the normal balls.

Possibility 2: Scale is not in balance. If the right pan is above the left pan then the odd ball is lighter than the normal ball. If the right pan is below the left pan then the odd ball is heavier than the normal balls. We now know that the odd ball is heavier/ lighter than the normal balls and we also know that it is among the 9 balls on the right pan. Again, using this method , we can, using 2 more weighings, identify the odd ball from among these 9 balls.