Transcript Finding the Odd Ball


There are 12 balls; 11 physically identical
balls and 1 that is a different
weight/density. You have a scale
balance that can be used three times.
Your goal is to identify the odd ball, and
determine whether it is heavier or lighter
than the other 11.

First, list all of the 3 digit combinations of
0,1 and 2
› 3 digits represent 3 uses of the balance.
› 33 = 27 possible combinations where a
combination = 3 digit numbers of {0,1,2}.
› There are 9 combinations with a 0 in the first
place, 9 with a 1 in the first, and 9 with a 2 in
the first, and so forth for the next 2 places.
› Thus we effectively are determining the
grouping of balls for each weighing.
000
001
002
010
011
012
020
021
022
100
101
102
110
111
112
120
121
122
200
201
202
210
211
212
220
221
222
By grouping the balls with the 3 digit
numbers, we ensure that the groups of
balls for each weighing will be
constructed in such a way as to exclude
all balls but one by the end of the 3
balances.
 This is difficult to see/understand until the
end of the process, so we will return to
this concept later in detail.


We have a list of 27 combinations giving 3 groups of 9 for
each weighing – but we need 12 combinations that give
3 groups of 4 for each weighing, and we need to do this
in a way that leaves ordering we can use to identify the
odd ball.

From the list of 27 cross out 15
 000, 111, and 222 (scale gives same reading regardless
of other 3 balls in group).
 Numbers whose first digit change is not 01, 12, or 20
(ensures 4 balls in all 3 groups for all 3 weighings)
 Example of accepted: 011, 112, 200
 Example of rejected: 211, 021, and 101
Ball ‘A’
001
‘B’
010
‘C’
011
‘D’
012
‘E’
112
‘F’
120
‘G’
121
‘H’
122
‘I’
200
‘J’
201
‘K’
202
‘L’
220

Weigh all balls with a 0 in the first position
against the balls with a 2 in the first
position
› ABCD vs. IJKL
If the 0 side is heavier write 0, if the 2 side
is heavier write 2, and if the scale is
balanced write 1
 We assume the odd ball is heavier, but a
later step will correct for this if it is lighter.


Weigh the balls with 0 in the second
position against the balls with 2 in the
second position.
› AIJK vs. FGHL

Write 0 if the 0 side is heavier, 2 if the 2
side is heavier, or 1 if the scale is
balanced.

Weigh the balls with 0 in the third position
against the balls with 2 in the third
position.
› BFIL vs. DEHK

Write 0 if the 0 side is heavier, 2 if the 2
side is heavier, or 1 if the scale is
balanced.
If a number is not on the list of 12 change
the 0’s to 2’s and 2’s to 0’s
 This indicates the ball is lighter, so the
numbers must be flipped

 Originally getting 020 means that ball K is
lighter (202)
 This happens because throughout the problem
you are assuming the odd ball is heavier

(3^N-3)/2; N= number of weighings
› This equals the maximum number of balls that
can be solved per N weighings
› Subtract three because 3 impossible
combinations
› Divide by 2 because we cannot directly
differentiate heavier and lighter on a balance.

Can solve
› 3 balls in 2 weighings
› 39 balls in 4 weighings
› 120 balls in 5 weighings




We have solved the problem using a
technique called enumeration-an ordered
listing of the elements of the indexed set.
The restrictions and structure-criteria we place
on the set and its elements ensure a ‘wellordered set’, which in this case meant a set
that grouped itself into 9 unique subsets.
‘unique’ is used to mean exclusionary, such
that the groups are ordered so that only one
possible ball can be present in all 3 that weigh
heavier.
Not only way to solve
http://mathforum.org/library/drmath/vie
w/56766.html
 http://www.mathsisfun.com/pool_balls_s
olution.html
