Biola Home Page
Math Faculty
Math Curriculi
Math Careers
Comp.Sci.Careers
Woopy Math Papers
Woopy Home Page
Putnam Papers

1997 Putnam Problems Solutions. Section B

by Peter Y. Woo, Biola University.

As of 12/15/97, I have solved 11 problems out of 12.
Note: I introduced some modifications to problem statements, due to limitations of HTML.
Notation: a / b . c shall mean a / ( b . c), not (a / b) . c

Soln97.B1     B1. Let {x} denote the distance between the real number x and the nearest integer. For each positive integer n, evaluate S_n = å_m=1^{6 n-1} min ( {m/6n}, {m/3n} ). [ min (a,b) means the minimum of a and b.]
    Solution: Divide the unit circle in the complex plane into 6 n equal arcs, with points P₀ to P_6n Each point P_k represents the numbers k/6n and (k+6n)/6n etc. The point P₀ represents the integers 0, 1, -1, 2, -2, etc. The points P_2n and P_4n represents the points at 120° and 240°. Let f (k) = min ({k/6n}, {2k/6n}). Then f (0) = f (3n) = f (6n) = . . . = 0 . It is seen easily from the diagram that:
    For 0 £ k £ 2n, f (k) = k/6n.
    For 2n £ k £ 3n, f (k) = 2(3n-k)/6n.
    For 3n £ k £ 4n, f (k) = 2(k-3n)/6n.
    For 4n £ k £ 6n, f (k) = (6n-k)/6n.
    Then å_{k = 1}^{6n - 1} f (k) = 2 å_{k = 1}^{3n - 1} f (k) = å_{k = 1}²ⁿ f (k) + å_{k = 2n+1}^{3n - 1} f (k)
= 2 [ n (1 + 2n) /6n + (½)(n - 1) (2 + (2n - 2)) /6n ]
= (1 / 3 n) [ n + 2 n² + n(n - 1)] = n. QED
    B2. Let f be a twice-differentiable real-valued function satisfying f (x) + f ''(x) = - x g(x) f '(x), where g(x) ³ 0 for all real x. Prove that | f (x)| is bounded.
    B3. For each positive integer n write the sum å_m=1ⁿ (1/m) in the form p_n / q_n where p_n and q_n are relatively prime positive integers. Determine all n such that 5 does not divide q_n .
    Solution: Notation: variables are all rational numbers. Names with i,j,k,l,m,n,p,q are integers. n always ³ 0. "a . b / c . d" means (a . b) / (c . d), not a . (b/c) . d
For each integer n > 0, let S_n = 1 + 1/2 + 1/3 + . . . + 1/n.
For each rational number x = p/q where gcd(p,q)=1, we say x has order -k (k > 0) if 5^k is the highest power of 5 dividing q, otherwise x has order k if 5^k is the highest power of 5 dividing p. The problem then is to find all n for which S_n has order ³ 0. Obviously, n = 1, 2, 3, 4 are some solutions, because S₁ = 1, S₂ = 3/2, S₃ = 3/2 + 1/3 = 11/6, S₄ = 11/6 + 1/4 = 25/12, all have order ³ 0.
    Lemma 1. For any n ³ 0, 1/(5n+1) + 1/(5n+4) and 1/(5n+2) + 1/(5n+3) have order 1, and å_i=1⁴ 1/(5n+i) has order 3 if 2n+1 is a multiple of 5, otherwise 2. Proof: Straightforward algebra. The last sum of 4 terms = 25 ( 2n+1) (10 n² + 10 n + 2) / (5n+1) (5n+2) (5n+3) (5n+4).
    Lemma 2. Let x have order i, and y have order j, then x + y has order min (i,j). Proof. Obvious.
     Given any n > 1, let 5^k be the hightest power of 5 < n. Then S_n = x₀ + x₁ + . . . + x_k where each x_i for 0 £ i £ k is the sum of terms whose denominators are multiples of 5ⁱ. Obviously, x₀ has order ³ 0, x₁ has order ³ -1, etc., and x_i has order ³ -i. If x_k has order exactly k, then S_n will have order -k, because of lemma 2. Also x_k = 5^-k x'_k, where x'_k = either 1 or 1 + 1/2 or 1+1/2+1/3 or 1+1/2+1/3+1/4, i.e., x'_k is either 1 or 3/2 or 11/6 or 25/12, which have orders 0, 0, 0, 2 respectively. This proved
     Lemma 3. If S_n = x₀ + x₁ + . . . + x_k as defined above, and x_k = 5^-k x'_k where x'_k = 1 or 3/2 or 11/6, then x_k and S_n both have order -k.
     Corollary. If S_n has order ³ 0, then either k = 0 or x_k = 5^-k (25/12) = 1/12(5^k-2).
     Lemma 4. If n ³ 5³, then S_n has order < 0. Proof. Due to the Corollary, we need to consider only the case x_k = 1/12(5^k-2. Assume S_n has order ³ 0. Then
x_k + x_k-2 = 5^{-(k - 2)} [1/12 + (1+1/2+1/3+1/4) + (1/6 + 1/7 + 1/8 + 1/9) + . . . + (1/101 + 1/102 + 1/103 + 1/104) + ... + (1/(5m+1) + 1/(5m+2) + . . . + 1/(5m+i) ) ] where
20£m£24, 1£i£4. m³ 20 because S_n contains the terms 5^-k(1 + 1/2 + 1/3 + 1/4), i.e., 5^{-(k - 2)} (1/25 + 1/50 + 1/75 + 1/100). Each of the parenthesized 4-term expressions have order ³ 2, hence 5^{-(k - 2)} [ 1/12 + 1/(5m+1) + . . . + 1/(5m+i)] must have order ³ 0.
     However, for i=4, the bracketed expression = [1/12 + 25 p/q} for some p,q, with q being a non-multiple of 5, thus having order 0.
     Similarly, for i=3, it is [1/12 + 1/(5m+1) + 1/(5m+2) + 1/(5m+3)] = [(5m+13)/ 12(5m+1) + 5 p / q] where q is a non-multiple of 5, hence having order 0.
     Similarly, for i=2, [1/12 + 1/(5m+1) + 1/(5m+2)] = (25 m² + 135 m + 38) / 12 (5m+1) (5m+2), which has order 0,
     and, for i=1, [1/12 + 1/(5m+1)] is similar to case i=3, with order 0.
     The conclusion from these 4 cases is then the only way for x_k + x_k-2 to have order ³ 0 is to have k £ 2. This means we must have n < 125. (QED for lemma 4.)
    Final Proof. If n < 125 and x_k has order ³ 0, we still must have x_k-1 having order ³ 0.
Case 1: n ³ 25. Then n must ³ 100, and then x₁ must = (1/5) [ (1 + 1/2 + 1/3 + 1/4) + (1/6 + 1/7 + 1/8 + 1/9) + . . . + (1/21 + 1/22 + 1/23 + 1/24)],
or = (1/5) [ (1 + 1/2 + 1/3 + 1/4) + (1/6 + 1/7 + 1/8 + 1/9) + . . . + (1/16 + 1/17 + 1/18 + 1/19)], so that either 100 £ n £ 104 or 120 £ n £ 124
Case 2: 5 £ n <25. Then x₂ = 0, and so x₁ must = (1/5) [1 + 1/2 + 1/3 + 1/4], so that 20 £ n £ 24.
     So all the solutions for n are: 1, 2, 3, 4, 20, 21, 22, 23, 24, 100, 101, 102, 103, 104, and 120, 121, 122, 123, 124.
    B4. Let a_m,n denote the coefficient of xⁿ in the expansion of (1 + x + x²)^m. Prove that for all k ³ 0,
0 £ å_i=0^{[ 2 k / 3]} (-1)ⁱ a_{k - i, i} £ 1, where [x] denotes the largest integer £ x for each real number x.
    Solution: Let A be the infinite matrix (a_m,n), then the first few rows of the matrix are:

For  n:   0   1   2   3   4   5   6   7   8   9  10  11  12
          ----------------------------------------------------
(m = 0:)  1
(m = 1:)  1   1   1
(m = 2:)  1   2   3   2   1
(m = 3:)  1   3   6   7   6   3   1
(m = 4:)  1   4  10  16  19  16  10   4   1
(m = 5:)  1   5  15  30  45  51  45  30  15   5   1
(m = 6:)  1   6  21  50  90 126 141 126  90  50  21   6   1

    We shall define a_m,n = 0 for n < 0 and n > 2 m.
    Lemma 1. a_m,n = a_{m-1, n-2} + a_{m-1, n-1} + a_{m-1, n}, so that the non zero elements of A is like a Pascal's triangle. Proof: By induction on m, and the obvious fact that the power of xⁿ in the m-th row is obtained by multiplying 3 terms of the previous row with x², x, 1 and added together. QED
    Define D_m as the diagonal {a_m,0, a_m-1,1, a_m-2,2, ..., a_0,m). Let S_m be the alternate sum of its elements, i.e., a_m,0 - a_m-1,1 + - . . .
    Let d_m be the number of nonzero elements of D_m. Let n be the maximum value so that the element a_m-n,n still > 0, then n £ 2 (m - n), so that 3 n £ 2 m, hence the conclusion that d_m = maximum integer £ 2 m / 3.
    By inspection, the sequence (S_m: m = 0, 1, 2, . . . ) = (1 1 0 0 1 1 0 0 . . .). This will be proved by induction. Assuming S_m = Ö2 sin ((2 m + 1)p/4) for the cases m-2, m-1, m, we shall prove the formula holds for the case m + 1:
Now S_m+1 = a_m+1,0 - a_m,1 + a_m-1,2 - + . . . by Lemma 1,
= (a_m,-2 - a_m,-1 + a_m,0) - (a_m-1,-1 - a_m-1,0 + a_m-1,1) + (a_m-2,0 - a_m-2,1 + a_m-2,2) - + . . .
= S_m - S_m-1 + S_m-2 .
\If (S_m-2, S_m-1, S_m) = (1, 1, 0), then S_m+1 = 0;
if (S_m-2, S_m-1, S_m) = (1, 0, 0), then S_m+1 = 1;
if (S_m-2, S_m-1, S_m) = (0, 0, 1), then S_m+1 = 1; and
if (S_m-2, S_m-1, S_m) = (0, 1, 1), then S_m+1 = 0. Thus the formula for S_m = Ö2 sin((2 m + 1)p/4) holds for all m.
    B5. Let f (1) = 2, f (2) = 2 ^{f (1)}, . . . , and f (n) = 2 ^{f (n-1)} for integers n > 1. Prove that for n ³ 2, f (n) - f (n-1) is a multiple of n.
    Solution: All variables unless otherwise stated will be integers. We shall write "x =_n y" instead of "x º y (mod n)". If further 0 £ y < n, we say "x mod n is y". We shall sometimes write n ^ m instead of n^m, [due to limitations of HTML]. Let f(n) be the Euler function, = the number of integers £ n that are relatively prime to n. Then f(n) = n - 1 iff n is a prime number.
    Two theorems are useful from Number Theory:
    Thm. 1 (Fermat). p is prime iff 2^p-1 =_p 1.
    Thm. 2 (Euler). If n = p₁^k p₂^k' ... p_m^k''' where 1 < p₁ < p₂ ... are prime numbers, then f(n) = n (1 - 1/p₁) (1 - 1/p₂) ... (1 - 1/p_m).
    We now prove a lemma:
    Lemma 1. Let f¹(n) = f(n), fⁱ(n) = f(f^i-1(n)) for i > 1, then for all n > 2, if n £ 2ⁱ, then for some K < i, f^K(n) is a power of 2.
    Proof: Let p(n) denote the greatest prime divisor of n. WLOG assume n is not a power of 2. Then for each odd prime p_i dividing n, the factor (1 - 1/p_i) in Thm. 2 increases the power of 2 dividing f(n) and decreases the power of p_i dividing f(n). Thus if K = max { k, k', ... k'''}, then f^K(n) has to be a pure power of 2. Also if n < 2ⁱ, then obviously K < i. QED
    Thm 3. (This is a stronger theorem than the problem statement). For each n, f(n) =_n f(n-1) =_n(n-2) = ... =_n f(k) for some k < n.
    Proof: Strangely enough, we cannot do induction on n. Then the sequence 2 mod n, 2² mod n, 2³ mod n, ... , soon will recurse, i.e., 2ⁱ =_n 2^i+j for some minimal i and j > 0. If n = 2^i' n' where n' is an odd integer, then i = i', and j divides f(n'), hence j divides f(n). Define the function q on all integers by q(n) = j. We shall write q_n for q(n), q²_n for q(q(n)), and qⁱ_n for q(q^i-1(n)) for i > 2.
    Then for all m, 2 ^ m =_n 2 ^ (m mod q_n) .
    \ 2 ^ (2 ^ m) =_n 2 ^ (2^m mod q_n) =_n 2 ^ ((2 ^ (m mod q²_n)) mod q_n)
    \ 2 ^ (2 ^ (2 ^ m)) =_n 2 ^ ((2 ^ ((2 ^ (m mod q³_n)) mod q²_n)) mod q_n)
     . . .
    By Lemma 1, after some K steps, where K < n, q^K_n is a pure power of 2, and then (2 ^ m) mod q^K_n = 0 for sufficiently big m. That means under modulo n, the sequence f(1), f(2), f(3), ... after at most K terms, will stabilize to a constant value. QED
     This solves the problem.
     Remark. This problem is interesting because f(5) = 2⁶⁵⁵³⁶ is already more than the number of electrons that can fill up the size of the known universe, and has over 20000 digits in decimal. f(6) in decimal, if printed in a book with 8 point font on thin paper, will have the book exceeding the size of the universe.
Soln97b6

    B6. Let ABC be a triangle, A', B', C' being the midpoints of BC, CA, AB respectively. Let lengths AB = 4, BC = 3, AC = 5. For each possible dissection D of triangle ABC into 4 parts, define the diameter d(D) be the least upper bound of the distances between pairs of points belonging to the same part. Then the line segments C'B', BB', A'B' subdivides triangle ABC into 4 triangles, and the dissection has a diameter = 2.5 . Find the least diameter of all dissections of the triangle into 4 parts.
    Solution: Let r be the minimum possible upperbound of the diameters of the 4 pieces. Then r < 2.5. Thus A,B,C must belong to 3 different pieces, namely S_A, S_B, S_C. Therefore the 4th piece is smallest possible when the 3 other pieces are largest possible, namely, as circular sectors of radius r centered at A, B, C. The resulting partition will be as shown in the diagram, where the 4th piece will have P, Q, R, S, T as corners. The boundary between S_B and S_C can be any curve joining S to any point between D and E. The arcs PQ, RS, ST can be replaced by line segments or other curves in between, because such liberties will not affect the diameters of the 4 pieces.
    Of the 4th piece, we want its diameter = r. Choose x-axis and y-axis so that B is the origin, C is (3,0), A is (0,4). Since the y-coord of R < that of T, PR > TR. Assuming PR is the diameter, and requiring PR = r, then we get some equation to solve for r.
    P is (0, 4-r), Q is (0.6 r, 4 - 0.8 r), R is (3-0.6 r, 0.8 r), T is (0, 4). S is (1.5, Ö(r²-2.25)). Hence r² = PR² = (3 - 0.6 r)² + (4 - r - 0.8 r)².
    Simplifying, we get 0 = 125 - 90 r + 13 r² = (13 r - 25) (r - 5), so that r = 25/13. It is a mundane exercise to verify PS and QS both < r.

You can go Up or Prev section.
Direct comments or questions to: Dr Peter Y. Woo, woopy@isaac.biola.edu