Solutions to the 2003 POW Problems
Week
#1 Mon. Aug. 25 – Wed. Sept. 3
Problem
1 (5 points): Find the exact sum of
the following infinite series, 13/1! + 23/2! + 33/3!
+ … n3/n! + … .
Solution:
We know that ex = 1 + x1/1! + x2/2! + … + xn/n!
+ … . Differentiating and then
multiplying by x, we obtain xex = 1×x1/1!
+ 2×x2/2!
+ … + n×xn/n!
+ … . Repeating this process we
find x(x+1)ex = 12×x1/1!
+ 22×x2/2!
+ … + n2×xn/n!
+ … . Finally we get x(x + 3x +
1)ex = 13×x1/1!
+ 23×x2/2!
+ … + n3×xn/n!
+ … . Substituting x = 1 we find
that 5e = 13/1! + 23/2! + 33/3! + … n3/n!
+ … .
Fall
2003 SJSU Problem of the Week
Competition
Week
#3 Mon. Sept. 8 – Wed. Sept. 17
Problem
3 (7 points): a) Do there exist 14
consecutive integers each of which is divisible by one or more of the primes p =
2,3,5,7,11?
b)
Do there exist 21 consecutive integers each of which is divisible by one or more
of the primes p = 2,3,5,7,11,13?
Solution: a) No. Any set of 14 consecutive integers contains 7 odd integers, say x,x+2,…,x+12. At most 3 are divisible by 3, at most two are divisible by 5, at most one is divisible by 7, and at most one is divisible by 11. But to have three of these divisible by 3, they must be x,x+6, and x+12. Then no two of the remaining odd integers x+2,x+4, x+8,x+10 can both be divisible by 5. Thus not all of x,x+2,…,x+12 are divisible by 3,5,7, or 11.
b)
Yes. If n is divisible by 2×3×5×7
= 210 then of the 21 consecutive integers n-10,n-9,…,n+9,n+10, all but n-1 and
n+1 are divisible by 2,3,5 or 7. Choose
n so that n-1 is divisible by 11 and n+1 is divisible by 13.
Then 9440,9441,…,9460 are all divisible by 2,3,5,7 or 11.
Fall
2003 SJSU Problem of the Week
Competition
Week
#5 Mon. Sept. 22 – Wed. Oct. 1
Problem
5 (9 points): Prove that the roots
of the polynomial p(x) = x5 + ax4 +bx3 +cx2
+dx + e = 0 cannot all be real if 2a2 < 5b.
Solution:
Suppose that that there are 5 real roots r1, r2, … , r5.
We have –a = S
ri and b = S
ri rj , i ¹
j. Then 2a2 – 5b <
0 is equivalent to 2{S
ri }2 – 5(S
ri rj ) < 0 or {S
(ri - rj)2 }/2 < 0.
This is a contradiction, therefore, the roots cannot all be real.
Posted
Mon. Oct. 20
Week
#7 Mon. Oct. 6 – Wed. Oct. 15
Problem
7 (11 points): In an election to
recall the dogcatcher Davis Gray there are 1002 yes votes and 1001 no votes.
The votes are counted one at a time in a random order and a subtotal is
computed after each vote is tallied. What
is the probability that the yes votes always outnumber the no votes in each
subtotal?
Solution:
An election result is any of the C(2003,1002) sequences of 1002 Y’s and 1001
N’s. An election result is good,
if the Y’s always lead the N’s, otherwise it is bad.
There are C(2002,1002) bad results that start with an N.
There is a 1-1 correspondence between the bad election results starting
with a Y and the set of sequences with 1002 N’s and 1001 Y’s that start with
a Y. The correspondence is obtained
by replacing Y’s with N’s and vice versa after the first spot where the #
Y’s is equal to the # N’s. Thus there are also C(2002,1002) bad results that start with
a Y. Therefore the probability of a
good result is [C(2003,1002) – 2C(2002,1002)]/C(2003,1002) = 1/2003.
Posted
Mon. Oct. 20
Week
#9 Mon. Oct. 20 – Wed. Oct. 29
Problem
9 (13 points): For each positive
decimal integer with n2 digits (no leading zeros) we take the
determinant of the matrix obtained by writing the digits in order across the
rows. For example, we associate the
det é
4 3 ù
= -2, to the
ë
2 1 û
integer
4321. Define f(n) to be the sum of
all the determinants associated with the n2-digit integers.
Which is larger f(9) or f(10)?
Solution:
For n > 2 we see that f(n) = 0. For
any nxn matrix M in the sum associated with f(n) either row 2 and row 3 are
equal or M can be paired with a matrix M’ obtained from M by interchanging
rows 2 and 3. In the first case det
M = 0 and in the second case det M + det M’ = 0.
Thus we see that f(n) = 0, for all n > 2. Therefore f(9) = f(10) = 0.
Week
#11 Mon. Oct. 20 – Wed. Oct. 29
Problem
11 (15 points): Consider cards 1,2,
… ,n in a pile. When the top card
is m, we reverse the order of the first m cards.
The process stops only when card 1 is at the top of the pile.
Prove that the process always stops after a finite number of steps,
regardless of the initial order of the cards.
Solution:
Let Fn be the maximum number of steps in any process for an n-card
stack. In general, we show that Fn
£
2n – 1, for all n ³
1. The result is true for n = 1
since F1 = 0 = 20 – 1.
Consider a process for some n+1-card stack.
1) If card n+1 never reaches the top, the bottom card never moves.
Relabeling card n+1 with the label of the bottom card, we see that the
number of steps in the process is at most Fn .
2) If card n+1 reaches the top during the process then the number of
moves required to move card n+1 to the top is at most Fn (relabel
card n+1 with 1, relabel card 1 with the label of the bottom card).
The next step in the process takes card n+1 to the bottom of the stack
where it remains. After that at
most Fn steps are required in the process.
In either case we see that Fn+1 £
2Fn + 1 £
2(2n – 1) + 1 £
2n+1 –1.
Posted
Fri. Dec. 5 Final Problem!!!
Week
#13 Mon. Nov. 17 – Mon. Dec. 1
Problem 13 (25 points): Let S be any set of 2003 distinct positive integers, none of which have a prime divisor greater than 23. Prove or disprove:
1)
There exist 2 distinct integers in S whose product is the square of an integer.
2)
There exist 4 distinct integers in S whose product is the fourth power of an
integer.
3)
There exist 5 distinct integers in S whose product is the fifth power of an
integer.
Solution: There are 9 primes 2,3,5,…,23 less than or equal to 23. Each integer in the set S has the form i = 2j13j25j3 … 23j9, for some integers j1,j2, … ,j9. To i we associate the vector (j1 mod 2, j2 mod 2, … ,j9 mod 2). For two integers i1,i2 which have the same associated vector, their product is a square. Thus if we have at least 29 + 1 = 513 integers in S, there will exist two integers whose product is a square. As long as we have at least 3(29)+1 = 1537 integers in S, then we can have pick 29 + 1 pairs of integers whose products are squares (Pick one pair as above and remove them from S, and continuing picking another pair until there are fewer than 513 integers remaining in S). To each pair we associate the vector corresponding to the square root of their product. Thus two products will have the same square root and their product will be a fourth power. Thus if we have at least 1537 integers in S, there will exist four integers whose product is a fourth power. On the other there is a set of 2048 integers such that no five have a product that is a fifth power. Let S be the set {i = 25k2j13j25j3 … 23j9 | k=0,1,2,3; j1,j2, … ,j9 = 0,1} The product of any 5 different integers from S will always have one exponent in its prime factorization whose remainder mod 5 is greater than 0, thus the product is not a perfect fifth power. Note that the problem of choosing a 3-subset whose product is a perfect cube is quite difficult. But evidently there is a set of 2016 integers such that no three have a product that is a cube. The construction of this set is too complex to explain here.