COS 341, November 5, 1997Midterm SolutionsHandout Nomver 12
Problem 1 There are four ways to cut off three corners of the board. Whether the resulting board can be covered perfectly does not depend on which way one chooses (any one can be rotated into another). Thus, it suffices to prove it for any particular choice of three corners.
Label the 81 cells as
cell-(i,j) with 
, with the SW-corner cell as the
origin cell-(0,0). We show that if cut off all the four corners
except cell-(8,8), the resulting board cannot be covered
perfectly.
Color the cells with three colors 0,1,2, with cell-(i,j)
in color 
. Then there are exactly
27 cells of each color. If we cut off the three corners
cells-(0,0), (0, 8), (8,0), the resulting board will have
26 cells of color 0, 27 cells of color 1, and
25 cells of color 2. Since each trimino must occupy
one cell of each color, this board cannot be covered perfectly.
Problem 2 From binomial theorem,
Let 
. Then
(a) The sought-after answer is by (1) equal to
(b) Let A be the answer. Let g(x) = xf(x). Then from (1)
and hence
Thus,
Now by definition
This, together with (2), implies
Problem 3
Solution 1 (a) From the recurrence, 
. Let 
for 
. Then 
, and
for n>1 we have the recurrence 
. This leads
to
It follows that for we have 
.
(b) From the recurrence, 
, and 
.
The recurrence gives for n>0
Let 
for . Then
, and
for 
we have the recurrence 
. This leads
to
It follows that for we have 
.
Solution 2 (a) Calculate the first
few 
, and see a pattern 
.
Conjecture that 
for , and then prove by
induction as follows. The base case n=1 is clearly true since
we have calculated 
. For the inductive step let m>1 and assume
that we have proved for all 
. Then the
recurrence gives 
.
This completes the induction.
(b) Calculate the first
few , and see a pattern 
.
Conjecture that 
for , and then prove by
induction as follows. The base case n=2 is clearly true since
we have calculated
. For the inductive step let m>2 and assume
that we have proved for all 
. Then the
recurrence gives 
.
This completes the induction.