Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.



Re: 12 billiard ball problem
Posted:
Jan 4, 2013 12:07 PM


Determining the number of the item and whether it is lighter or heavier out of a group of twelve. This problem is for those appreciate mental challenge. While serving as the Guided Missile Systems Officer in the USS Boston (CAG1), the world?s first guided missile cruiser, Homeport Boston, Massachusetts, I was approached by one of my crew, a Missile Technician with a question and him asking for a solution to the problem: Given twelve items of similar dimension and weight, one of which is measurably lighter or heavier than the others you are also given a set of balance scales. You are then permitted to make three separate measurements of combinations of the various items, and at the end of the three tests, tell whether the defective item is either lighter or heavier and the number of the items which must identify by number assigned. While I was able to demonstrate a solution by relying on a bookkeeping system (I can provide that system for anyone interested) that allowed me to positively do so, I was intrigued by the fact that I could not solve the problems mathematically where I didn?t have to utilize a bookkeeping system whatsoever. After some months of working on the problem (one has quite a bit of free time to think on problems while steaming all over the Mediterranean on a Navy Ship) I was able to come up with the below solution and I will demonstrate this solution. First I will define the three measurements of the items by placing the numbered items on the balance scales as follows: Test group one 1 4 3 5 VS 6 8 7 2 (where items 1, 4, 3, and 5 are on the left side of the scale and 6, 8, 7, and 2 are on the right). Test group two 6 7 8 1 VS 2 10 12 9 Test group three 3 8 12 2 VS 5 9 11 6 Now the fun part. As you make the three measurements, assign the results to A, B , C. For example if we select 4 (light) as the example item, the results using ABC (down on the right is 2, down on the left is 0 and balanced result is 1). Thus if item 4 is light, the result (ABC) would be 2 1 1. Now we need to interpret the results while hopefully identifying the correct item number and whether it is light or heavy compared to the other 11 items.. Don?t let the following scare you off; it is quite simple and requisite to analyzing the resulting number resulting from the weighing and as assigned to ABC . That number is 211 in our example. To do this we must utilize the base 3 number system, which is called the Ternary numbering system. You can Google it if need be and you will find the following to be true. Here is the number 1 through 12 in the Decimal system converted to Ternary. 1 = 1 2= 2 3= 01 4= 11 5=2 1 6=20 7=21 8=22 9=100 10=101 11=102 12=110 Since you have now become an expert in Ternary Arithmetic, lets reinforce our learning by reviewing Binary (base 2 arithmetic). 1 = 1 2=10 3=11 4=100. Now you get the idea. I would challenge the reader (learner) to develop for themselves a table of the numbers decimal 1 ? 10 and convert them to the Quaternary system base 4 system. If you can do that, then I do believe you are on the right track to understanding numbering systems. The following link http://core.ecu.edu/csci/wirthj/Basen/basenc.html will take you to the definition of a numbering system that will make you an expert on numbering systems in general plus info on the various conversion techniques. After all that, let?s get back to our problem. Given that ABC is 211 in our example we are immediately frustrated because the base 3 number, 211 converted to decimal is 2 + 3 +9 which is 14 in decimal and we only have 12 possibilities within our group of 12 items. That is easily resolved. When it is a ternary number ABC is greater than 12 decimal, convert it as follows: Change all zeros to two and all twos to zero. Now our number becomes 011 which since you are now a number expert you recognize as the number in ternary equal to 4 in decimal. Thus the answer is 4 and it is light. Course we knew that because we had assigned the number 011 ternary as being decimal 4. Last but not least is the figuring out if the ball is light or heavy. We must define a good number as contrasted to a bad number. This is accomplished by evaluating ABC. We are looking for one of the following progressions 01 or 12 or 20. Any of these three are good progressions. Note that when we find the progression being good we can stop. Such as 001 is good 002 is bad. We ignore the pairs that are equal. After determining whether the ABC is a good or bad progression we can then state whether the ball is light or heavy. For example, 021 is bad (light) and 120 is a good (heavy) progression. Thus if the number is greater than twelve TERNARY then convert the zeros to twos and twos to zeros and evaluate the result to determine the number of the item. Evaluate the unconverted number for the proper progression. If it is a good progression it is heavy, if the progression is bad, then it is light. As a last example let us take the ball number 10 and assume that it is heavy and see what we find. Again, using the scales, and assigning numbers to ABC the result will be 1 2 1. It is larger than 12 decimal, so we convert it to 101 (9 + 1 = 10) to find the number of the ball. Looking at ABC, which is 121 (base 3), 12 of the 121 is a good progression so it defines the item to being heavy. No explanation to as why, merely that we have defined the progressions as defining whether an item is light or heavy. Are you sufficiently confused. Pick a number of a ball, do the measurement assign the number to ABC and do the above tests to see if the answer does or does not give you the proper result. Don?t get a headache over it. Raymond C Phillips, LT USN Retired



