It's a common
classroom game for gradeschoolers and yet it contains a profoundly
powerful problem solving strategy which can be used to debug software,
troubleshoot equipment and solve problems in business and industry. In
the game one child picks an object and everyone else has 20
questions to identify it. At first the children guess specific items but they soon realize they need to eliminate entire categories
or risk using up their 20 questions before finding the
answer.
The principles of twenty questions are frequently used in
the business world to conduct computerized searches of massive data bases. These
are called a binary searches and are one of the fastest search methods
available. To conduct binary
searches, data
must be sorted in order or alphabetized. The computer determines which
half of the list contains the item. The half containing the item is
divided in half again and the process repeated
until the item is found or the list can no longer be divided.
Just how powerful is 20 questions? The correct
alternative can be identified from among 2^{20} or 1,048,576
different alternatives assuming that a "no" has the same weight as a
"yes" answer. In other words, either answer eliminates half the alternatives on each question. For example,
consider the question, "is the object in this half of the room."
A yes or no question will generally eliminate half of the objects in the
room. (The exceptions are objects which are in both halves such as the
air.)
Is weighting yes
and no answers equally
really the best technique? At first glance it seems
like weighting the yes so that it eliminates 80% of the alternatives would
be even better. True, a no answer would only eliminate 20% of the
alternatives but surely we could ask the questions so that we would get
yes answers at least 50% of the time. Each yes will leave 20%
of the questions remaining. In other words a single yes could identify the
correct choice from a group of five alternatives with only one question as
follows:
where: A1 is
the number of possible alternatives or the power for a single question. For 10 yes
answers the number of alternatives would be:




A_{10 } 
= 1/(0.2)^{10} 





= 9,765,625 



If
we add another 10 no answers, the number of alternatives rises as follows:




A_{20} 
= (1/(0.2)^{10})(1/(0.8)^{10}) 





=90,949,470 



This
is impressive but, unfortunately not attainable. The
probability of getting a yes will not be 50%. It will be 100%  80%
or only 20%. The probability of getting a no will be 80%. Consider an
example: If there were one correct choice among five alternatives and we
asked if a particular one was correct, a yes answer would eliminate 80% of the alternatives.
Unfortunately, the alternative we inquire about has to be the
correct one to get a yes. Hence, the probability of a getting yes answer
is only 1/5 or 20%. The correct way to calculate the
number of alternatives for 20 questions with a yes eliminating 80% of the
alternatives is as follows:




A 
= (0.2)^{(20*.2)}(0.8)^{(20*.8)} 





=
22,204 



In
reality, trying to eliminate 80% of the alternatives with each yes
question is a very poor strategy. We
can write a general purpose expression for calculating the alternative
using various weighting for a yes answer as follows:




A 
= (P_{y})^{(20*Py)}(P_{n})^{(20*Pn)} 



where:
P_{y
}= the probability of getting a yes answer P_{n
}= the probability of getting a no answer P_{n
}= 1  P_{y}
Note
that the above equation will only give meaningful values when P_{y }is
a factor of 1/20. The exponent for either P_{y} or P_{n }represents
the number of questions answered yes and no respectively. Obviously it's
impossible to have a fraction of a question answered yes or no. Hence,
both P_{y} and P_{n} have to be factors of 1/20 to insure
that both exponents represent an integer number of questions.
