Java Reference
In-Depth Information
(a) Prove the Pigeonhole Principle using proof by contradiction.
(b) Prove the Pigeonhole Principle using mathematical induction.
2.31 For this problem, you will consider arrangements of infinite lines in the plane
such that three or more lines never intersect at a single point and no two lines
are parallel.
(a) Give a recurrence relation that expresses the number of regions formed
by n lines, and explain why your recurrence is correct.
(b) Give the summation that results from expanding your recurrence.
(c) Give a closed-form solution for the summation.
2.32 Prove (using induction) that the recurrence T(n) = T(n 1) +n; T(1) = 1
has as its closed-form solution T(n) = n(n + 1)=2.
2.33 Expand the following recurrence to help you find a closed-form solution, and
then use induction to prove your answer is correct.
T(n) = 2T(n 1) + 1 for n > 0; T(0) = 0:
2.34 Expand the following recurrence to help you find a closed-form solution, and
then use induction to prove your answer is correct.
T(n) = T(n 1) + 3n + 1 for n > 0; T(0) = 1:
2.35 Assume that an n-bit integer (represented by standard binary notation) takes
any value in the range 0 to 2
n
1 with equal probability.
(a) For each bit position, what is the probability of its value being 1 and
what is the probability of its value being 0?
(b) What is the average number of “1” bits for an n-bit random number?
(c) What is the expected value for the position of the leftmost “1” bit? In
other words, how many positions on average must we examine when
moving from left to right before encountering a “1” bit?
Show the
appropriate summation.
2.36 What is the total volume of your body in liters (or, if you prefer, gallons)?
2.37 An art historian has a database of 20,000 full-screen color images.
(a) About how much space will this require? How many CDs would be
required to store the database? (A CD holds about 600MB of data). Be
sure to explain all assumptions you made to derive your answer.
(b) Now, assume that you have access to a good image compression tech-
nique that can store the images in only 1/10 of the space required for
an uncompressed image. Will the entire database fit onto a single CD
if the images are compressed?
