1997 Putnam Problems Solutions. Section A

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 ;
Binomial coefficient (ⁿ_k) will be written ⁿC_k.

    A1. A rectangle HOMF has sides HO = 11 and OM = 5. A triangle ABC has H as the intersection of the altitudes, O the center of the circumscribed circle, M the midpoint of BC, and F the foot of the altitude from A. What is the length of BC?
    Solution. A has to lie on FH because H is the orthocenter and AF is an altitude. Therefore BC has to lie on line MF, with M as midpoint. The centroid G has to lie on OH with OG = 1/3 OH, hence A has to lie on ray FH. Triangles AHG and MOG are similar, hence AH = 2 HF = 2 × 5 units = 10 units. Hence AF is 15 units. Let BM = CM = x. Then BF = x - 11, and CF = x + 11. ÐBHF = ÐC because FCB'H is a cyclic quadrilateral. Hence BF/HF = tanÐBHF = tanÐC = AF/FC.
\ (x - 11)/5 = 15/(x + 11). \x² - 11² = 45; \x = 14. Hence BC = 28.

    A2. Players 1,2,3,...,n are seated around a table and each has a single penny. Player 1 passes a penny to Player 2, who passes two pennies to Player 3. Player 3 then passes one penny to Player 4, who passes two pennies to Player 5, and so on, players alternately passing one penny or two to the next player who still has some pennies. A player who runs out of pennies drops out of the game and leaves the table. Find an infinite set of numbers n for which some player ends up with all n pennies.
    Solution. The passing of coins from one person to the next will be called a step. Suppose there are 6 people left in a game, we shall use the notation (n₁, n₂,n₃[2],n₄,n₅, n₆) to denote the state of the game if n_i is the number of coins in Player i, and Player 3 is about to give 2 coins to Player 4, leaving Player 3 with n₃ coins and Player 4 will have n₄+2 coins.
    Let us start a game with 10 persons.
After 10 steps, the state is (0, 0, 2, 0, 2, 0, 2, 0, 2, 0[2]). Then 6 people leaves the game, and the state is (2, 2, 2, 2[2]).
After 4 steps, the state is (1, 3, 1, 3[2]).
After 4 steps, the state is (0, 4, 0, 4[2]) which becomes (4, 4[2]).
After 2 steps, the state is (3, 5[2]), another 2 steps later, (2, 6[2]), another 2 steps later, (1, 7[2]) and so eventually (0, 8[2]), which ends the game with one person getting all the coins.
    Similarly, if we start with n = 2^k + 2 persons, after n steps the state is (0, 0, 2, 0, 2, 0, . . . , 2, 0[2]) which has 2^k-1 persons left. 2 rounds later the state is (0, 4, 0, 4, . . ., 0, 4[2]) which has 2^k-2 persons left, and eventually the game ends with one person getting all the coins.
    Hence n = 1, 2, 3, 4, 6, 10, 18, . . . , 2^k + 2 , ... will give games that lead to one person getting all the coins.

    A3. Evaluete ò₀^¥ ( x - x³ /2 + x⁵ /2.4 - x⁷ /2.4.6 + - . . . ) ( 1 + x² /2² + x⁴ /2²4² + x⁶ /2²4²6² + . . . ) dx.
    Solution. Let u = x²/2, then du = x dx. Then the integral
= ò₀^¥ ( 1 - u + u²/2! +u³/3! + . . . ) ( 1 + u/2 + u²/2²2!² + u³/2³3!² + . . .) du
= ò₀^¥ e^{- u} å_i=0^¥ ( uⁱ/ 2ⁱ i!² ) du .
     Now ò₀^¥ uⁿ e^{- u} du = [ - uⁿ e^-u ]₀^¥ - ò₀^¥ (- e^{- u}) n u^n-1 du = n ò₀^¥ e^{- u} u^n-1 du
= n (n-1) ò₀^¥ e^{- u} u^n-2 du = . . . = n!.
    Hence each term ò₀^¥ e^{- u} uⁱ/ 2ⁱ i!² du = i ! / 2ⁱ i!² = (½)ⁱ / i! .
    Hence the integral is 1 + (½) + (½)² / 2! + (½)³ / 3! + . . . = e ^1/2 = Ö e.

    A4. Let G be a group with identity e and f : G ® G a function such that
f(g₁) f(g₂) f(g₃) = f(h₁) f(h₂) f(h₃) whenever g₁ g₂ g₃ = e = h₁ h₂ h₃ . Prove that there exists an element a in G such that y(x) = a y(x) is a homomorphism (that is, y(x y) = y(x) y(y) for all x and y in G ).
    Solution. Let us denote f(x) by x' for all x Î G.
Let a,b Î G. Since e a a^-1 = e a^-1 a = e, we have e' a' (a^-1)' = e' (a^-1)' a', i.e., we have proved
    Lemma 1: a'and (a^-1)' commute.
     Again, since e e a = e a e, \ e' a' = a' e', \ a' e' ^-1 = e' ^-1 a', which proved
    Lemma 2: e' and e' ^-1 commute with x' for all x Î G.
    Lemma 3 For all a, b Î G, a' b' = e' (a b)'. Proof: Since a b (a b)^-1 = e (a b) (a b)^-1,
\ a' b' (a b)^-1 ' = e' (a b)' (a b)^-1 '. \ a' b' = e' (a b)'. QED
    Now proof of Main Thorem: Let y(x) = x' e' ^-1 for all x Î G. Then y(a b) = (a b)' e' ^-1 = e' ^-1; (a b)'
= (e' ^-1)² e' (a b)' = (e' ^-1)² a' b' = a' e' ^-1 b' e' ^-1 = y(a) y(b), QED

    A5. Let N_n denote the number of ordered n-tuples of positive integers (a₁, a₂, . . . , a_n) such that 1/a₁ + 1/a₂ + . . . + 1/a_n = 1. Determine whether N₁₀ is even or odd.
    Solution. For each 10-tuple T = (a₁, a₂, ..., a₁₀) whose reciprocals add up to 1, there may be repetitions, so that the a_i's are made up of distinct integers 1 < b₁ < b₂ < . . . < b_k each repeated n₁, n₂, . . . , n_k times respectively, and n₁ + n₂ + . . . + n_k = 10. Then the 10-tuple can be permuted p(T) = 10! / n₁! n₂ . . . n_k ways into distinguishable 10-tuples.
    Lemma 1. p(T) is even unless k = 2 and a₁ and a₂ are 2 and 8 .
Proof: Let f (m) denotes the maximum integer m' such that 2^m' divides m.
In order for p(T) to be odd, then f (10!) must = f (n₁) + f (n₂) + ... + f (n_k).
Now f (10!) = f (2)+f (4)+f (6)+f (8)+f (10) = 1 + 2 + 1 + 3 + 1 = 8.
Without loss of generality, we can ignore cases where some of the n_i = 1, and we can count the combinations of n_i's by listing them with 1 < n₁ £ n₂ £ . . . £ n_k , that meet the requirement of their sum being 10. They are:
Case 1: f (2! 2! 2! 2! 2!) = 1 + 1 + 1 + 1 + 1 = 5.
Case 2: f (2! 2! 2! 4!) = 1 + 1 + 1 + 3 = 6.
Case 3: f (2! 2! 3! 3!) = 1 + 1 + 1 + 1 = 4.
Case 4: f (2! 2! 6!) = 1 + 1 + 4 = 6.
Case 5: f (2! 3! 5!) = 1 + 1 + 3 = 5.
Case 6: f (2! 4! 4!) = 1 + 2 + 2 = 5.
Case 7: f (2! 8!) = 1 + (1 + 2 + 1 + 3) = 8.
Case 8: f (3! 3! 4!) = 1 + 1 + 2 = 4.
Case 9: f (4! 6!) = 3 + 4 = 7.
Case 10: f (5! 5!) = 3 + 3 = 6.
    Thus the only case where p(T) can be odd is Case 7 where 10! / 2! 8! = 45. QED for lemma.
     Now we look for possible cases of x, y such that 1 = (1/y + 1/y +1/y + 1/y +1/y + 1/y +1/y + 1/y) + (1/x + 1/x).
\ x y = 8 x + 2 y, or x = 2 y / (y - 8) . . . . (1). \ y > 8. Similarly y = 8 x / (x - 2), so x > 2.
Using (1), we can have (x, y) = (18, 9) or (10, 10) or (6, 12), or (4, 16) or (3, 24).
Each of these 5 cases gives rise to 45 permutations of the a_i's as ( x, x, y, y, y, y, y, y, y, y ). 5 × 45 is an odd number 225.
Conclusion. N₁₀ , the total number of 10-tuples whose reciprocals add up to 1, is an odd number.
    A6. For a positive integer n and any real number c, define x_k recursively by x₀ = 0, x₁ = 1, and for k ³ 0,
x_k+2 = ( c x_k+1 - (n - k) x_k ) / (k + 1) .
Fix n and then take c to be the largest value for which x_n+1 = 0. Find x_k in terms of n and k, 1 £ k £ n.
    Solution. Rewrite the recurrence relation as (k + 1) x_k+2 + (n - k) x_k = c x_k+1. . . . (1), Then
let k = 0, \ x₂ + n x₀ = c x₁ ;
let k = 1, \ 2 x₃ + (n - 1) x₁ = c x₂ ;
let k = 2, \ 3 x₄ + (n - 2) x₂ = c x₃ ;
. . . . .
let k = n-2, \ (n - 1) x_n + 2 x_n-2 = c x_n-1 ;
let k = n-1, \ n x_n+1 + x_n-1 = c x_n .
    Adding up, assuming x₀ = x_n+1 = 0, we get
(n - 1)å_i=1ⁿ x_i = c å_i=1ⁿ x_i . \ c = n - 1.
    Rewrite (1) as (k + 1) x_k+2 = c x_k+1 - (c - k + 1) x_k . . . . (2),
    Therefore x₂ = c x₁ - n x₀ = c ,
x₃ = (1/2) (c x₂ - c x₁) = c (c - 1) / 2, = Binomial coefficient ^c C₂ .
x₄ = (1/3) (c x₃ - (c - 1) x₂) = (1/3) c ((½) c(x₂ - x₁) - (c - 1)) = ^c C₃
x₅ = (1/4) (c x₄ - (c - 2) x₃) = (1/4) (c (c-1) (c-2) / 3 - (½) (c-1) (c-2)) = ^c C₄
We now assume x_k = ^cC_k for cases k and k+1.
Then for case k+2,     (RHS of equation (2))_/(k+1) = ( c x_k+1 - (c - k + 1) x_k ) /_(k+1)
= (c . c (c-1) ... (c-k+1)/ _k! - (c-k+1) c (c-1) ... (c-k+2) / _{(k - 1)!}) / (k+1)
= (c . c (c-1) ... (c-k+1) - k (c-k+1) c (c-1) ... (c-k+2)) / _{k! (k+1)}
= c (c-1) ... (c - k + 2) (c - k + 1) (c - k) /_{(k + 1)!}, = ^c C_k+1, which proves the assumption for case k+2.
Therefore by induction, it is true for all integer k > 0, that x_k = ^c C_k = ^n-1 C_k .