Information Technology Reference
In-Depth Information
With statements 1, 2, and 3 of the opening true/false quiz being
true, it may be easy to believe that statement 4 must be true as well.
After all, if computing technology continues to improve at a rapid
rate, it can solve many more problems—right?
Before you get carried away, consider the following illustrative
fable.
A Fable: A King Meets the Combinatorial Explosion
Once upon a time, a king needed a great task performed. In response, a clever young
man named Paul agreed to do the work, if the amount of payment was adequate. When
the king asked Paul about his requirements for compensation, Paul responded that the
king might choose between two options:
Option 1.
Payment could consist of onefifth of the crops produced in the kingdom for
each of the following five years, or
Option 2.
Payment could be made as follows:
One kernel of corn would be given for the first square of a chess board.
Two kernels of corn would be paid for the second square.
Four kernels (twice the previous amount) would be paid for the third square.
Eight kernels (again twice the previous) would be paid for the fourth square.
This counting would continue, with successive doubling for each square, until pay
ment was made for each square of a chess board.
When the king considered these choices, the first option seemed justified for the great
service required, but the king liked the sound of the second option better. After all, the
king reasoned, how could a few kernels of corn compare to a full fifth of the crops har
vested for each of five years, as offered in Option 1? With this, the king contracted with
Paul for the work using Option 2 as the form of payment.
A year went by, Paul completed the work, and it was time for payment. The king or
dered baskets of grain to be brought, and the process was begun of counting kernels of
corn. For the first row of the chess board (eight squares), the payment involved 1 2
2
2
2
3
2
4
2
5
2
6
2
7
or 1 2 4 8 16 32 64 128 255 kernels
of corn, much less than a bushel. (The USDA and the University of Illinois have devel
oped a measure, called the Corn Yield Calculator, to determine quantities of corn.
According to this measure, a bushel averages 72,800 kernels of corn.)
For the next row, the payment was
2
8
2
9
2
10
2
11
2
12
2
13
2
14
2
15
or 65,280 corn kernels. Since a bushel of corn typically contains about 72,800 kernels,
this payment was still less than a bushel of corn.
With the next row, however, the king became uneasy. The payment for this row was
2
16
2
17
2
18
2
19
2
20
2
21
2
22
2
23
