142 CHAPTER 4 THREE IMPORTANT CROSSOVER TACTICS
In/ 3 J ( )
(c) Find a simple fonnula for the sum � ;..
}=o }
(d) Generalize!
4.3.16 (Leningrad Mathematical Olympiad 1991) A
finite sequence at, a 2 , ... ,an is called p-balanced if
any sum of the fonn ak + ak+p + ak+ 2 p + ... is the
same for any k = 1,2, ... , p. Prove that if a se
quence with 50 members is p-balanced for each of
p = 3,5,7, II, 13, 17, then all its members are equal
to zero.
4.3. 17 Let p( n) denote the number of unrestricted par
titions of n. Here is a table of the first few values of
p(n).n p(n) The different sums
I I
2 2 1+1,2
3 3 1+1+1,1+2,3
4 5 I + I + I + I, I + I +2, I +3,2+2,4
5 7 I + I + I + I + I, I + I + I + 2,
I + I +3, I +2+2,2+3, I +4,5
Let f(x) be the generating function for p(n) [in other
words, the coefficient of x* in f(x) is p(k)]. Explain
why(^00) I
f(x) =
D I-xn·
4.3.18 Show that the number of partitions of a posi
tive integer n into parts that are not multiples of three
is equal to the number of partitions of n in which there
are at most two repeats. For example, if n = 6, then
there are 7 partitions of the first kind, namely
I + I + I + I + I + I, I + I + I + I + 2,
1+1+2+2, 1+1+4, 1+5,
2+2+2, 2+4;
and there are also 7 partitions of the second kind,
1+1+4, 1+1+2+2, 1+2+3,
1+5, 2+4, 3+3, 6.
Can you generalize this problem?
4.3.19 In how many ways can you make change for
a dollar, using pennies, nickels, dimes, quarters, and
half-dollars? For example, 100 pennies is one way;
20 pennies, 2 nickels, and 7 dimes is another. Order
doesn't matter.
4.3.20 The function (l-x-x^2 -x 3 _x^4 - .r; _x^6 )-t
is the generating function for what easily stated se
quence?
4.3.21 A standard die is labeled 1,2,3,4,5,6 (one in
teger per face). When you roll two standard dice, it is
easy to compute the probability of the various sums.
For example, the probability of rolling two dice and
getting a sum of 2 is just 1/36, while the probability
of getting a 7 is 1/ 6.
Is it possible to construct a pair of "nonstandard"
dice (possibly different from one another) with posi
tive integer labels that nevertheless are indistinguish
able from a pair of standard dice, if the sum of the dice
is all that matters? For example, one of these non
standard dice may have the label 8 on one of its faces,
and two 3 's. But the probability of rolling the two and
getting a sum of 2 is still 1/36, and the probability of
getting a sum of 7 is still 1/6.
4.3.22 Alberto places N checkers in a circle. Some,
perhaps all, are black; the others are white. (The dis
tribution of colors is random.) Betiil places new check
ers between the pairs of adjacent checkers in Albertos
ring: she places a white checker between every two
that are the same color and a black checker between
every pair of opposite color. She then removes Alber
tos original checkers to leave a new ring of N checkers
in a circle.
Alberto then perfonns the same operation on
Betiils ring of checkers following the same rules. The
two players alternately perfonn this maneuver over
and over again.
Show that if N is a power of two, then all the
checkers will eventually be white, no matter the ar
rangement of colors Alberto initially puts down. Are
there any interesting observations to be made if N is
not a power of two?