SOLUTIONS

No problem is ever permanently closed. Any comments, new solutions, or new insights on old problems are always welcomed by the problem editor.

81. [1995, 87] Proposed by J. Sriskandarajah, University of Wisconsin Center– Richland, Richland Center, Wisconsin.

Let ABC be a triangle with sides a, b, and c. Let K be the area of triangle ABC and s be the semi-perimeter of ABC.

(a) Prove that

\frac{K}{tan \frac{A}{2}} + K tan \frac{A}{2} = bc.

(b) Prove that

\frac{K}{s tan \frac{A}{2}} + s = b + c.

Solution by Bob Prielipp, University of Wisconsin–Oshkosh, Oshkosh, Wisconsin.

We begin by noting that

tan \frac{A}{2} = \frac{r}{s − a} = \frac{rs}{s(s − a)} = \frac{K}{s(s − a)}

where r is the inradius of triangle ABC.

(a) Thus, by Heron’s Formula and some algebra,

\frac{K}{tan \frac{A}{2}} + K tan \frac{A}{2} = s(s − a) + \frac{K^{2}}{s(s − a)}

= s(s − a) + \frac{s(s − a)(s − b)(s − c)}{s(s − a)}

= s(s − a) + (s − b)(s − c) = 2s^{2} − s(a + b + c) + bc

= 2s^{2} − s(2s) + bc = bc.

(b) Also,

\begin{aligned}\frac{K}{s tan \frac{A}{2}} + s & = (s − a) + s = 2s − a \\ & = (a + b + c) − a = b + c. \end{aligned}

Also solved by Russell Euler, Northwest Missouri State University, Maryville, Missouri; Herta T. Freitag, Roanoke, Virginia; Kandasamy Muthuvel, University of Wisconsin–Oshkosh, Oshkosh, Wisconsin; Joseph B. Dence, University of Missouri–St. Louis, St. Louis, Missouri; Jayanthi Ganapathy, University of Wisconsin–Oshkosh, Oshkosh, Wisconsin; Joe Howard, New Mexico Highlands University, Las Vegas, New Mexico; Donald P. Skow, University of Texas–Pan American, Edinburg, Texas; Joseph Wiener, University of Texas–Pan American, Edinburg, Texas; and the proposer.

82. [1995, 87] Proposed by Curtis Cooper and Robert E. Kennedy, Central Missouri State University, Warrensburg, Missouri.

Evaluate

lim_{k→∞} \frac{log \frac{10^{10^{k}} ((10^{k−1})!)^{10}}{(10^{k})!}}{k} ,

where log x denotes the base 10 logarithm of x.

Solution by Joseph B. Dence, University of Missouri–St. Louis, St. Louis, Missouri and the proposers.

Let 10^{k−1} = x and c = 1/ ln 10. Then

\frac{log \frac{10^{10^{k}} ((10^{k−1})!)^{10}}{(10^{k})!}}{k} = \frac{log \frac{10^{10x}(x!)^{10}}{(10x)!}}{1 + log x}

= \frac{10x + 10 log(x!) − log((10x)!)}{1 + log x}

= \frac{10x + c(10 ln(x!) − ln((10x)!))}{1 + c ln x}.

For large integral n we have [G. H. Hardy, Divergent Series, Oxford University Press, 1949, p. 334]

ln(n!) = (n + \frac{1}{2}) ln(n) − n + \frac{1}{2} ln(2π) + O(n^{−1}).

Substitution in the above expression gives

\frac{10x + c(\frac{9}{2} ln x + \frac{9}{2} ln(2π) − (10x + \frac{1}{2}) ln 10) + O(x^{−1})}{1 + c ln x}

and thus, by simplification and l’Hôpital’s Theorem,

lim_{k→∞} \frac{log \frac{10^{10^{k}} ((10^{k−1})!)^{10}}{(10^{k})!}}{k} = lim_{x→∞} \frac{log \frac{10^{10x}(x!)^{10}}{(10x)!}}{1 + log x}

= lim_{x→∞} \frac{10x + 10 log(x!) − log((10x)!)}{1 + log x}

= lim_{x→∞} \frac{\frac{9}{2}c ln x + \frac{9}{2}c ln 2π − \frac{1}{2}}{1 + c ln x}

= \frac{9}{2}c lim_{x→∞}(x^{−1}/cx^{−1})

= \frac{9}{2}.

Also solved by Donald P. Skow, University of Texas–Pan American, Edinburg, Texas; Joe Howard, New Mexico Highlands University, Las Vegas, New Mexico; Joseph Wiener, University of Texas–Pan American, Edinburg, Texas; N. J. Kuenzi, University of Wisconsin–Oshkosh, Oshkosh, Wisconsin; and Alan H. Rapoport, Ashford Medical Center, Santurce, Puerto Rico.

83. [1995, 88] Proposed by Donald P. Skow, University of Texas–Pan American, Edinburg, Texas.

(a) Let O_{n} denote the nth octagonal number. Prove that

O_{n}O_{n+2} + 2O_{n+1} − 1

is a perfect square.

(b) Let N_{n} denote the nth nonagonal number. Prove that

N_{n}N_{n+2} + N_{n+1} + 3

is a perfect square.

(c) Determine a nontrivial function of three consecutive heptagonal numbers which always produces a perfect square.

Solution to (a) and (b) by Bob Prielipp, University of Wisconsin–Oshkosh, Oshkosh, Wisconsin; Russell Euler, Northwest Missouri State University, Maryville, Missouri; Joe Howard, New Mexico Highlands University, Las Vegas, New Mexico; Joseph B. Dence, University of Missouri–St. Louis, St. Louis, Missouri; Lawrence Somer, The Catholic University of America, Washington, D.C.; Gayla Singleton (student), Southeast Missouri State University, Cape Girardeau, Missouri; J. Sriskandarajah, University of Wisconsin Center–Richland, Richland Center, Wisconsin; Herta T. Freitag, Roanoke, Virginia; and the proposer.

It is known that the nth k–gonal number is given by

\frac{n}{2}(2 + (n − 1)(k − 2)).

Thus,

\begin{aligned}O_{n} & = n(3n − 2), \\ and N_{n} & = \frac{n(7n − 5)}{2}. \end{aligned}

Therefore,

\begin{aligned}O_{n}O_{n+2} + 2O_{n+1} − 1 & = [n(3n − 2)][(n + 2)(3n + 4)] + 2(n + 1)(3n + 1) − 1 \\ & = 9n^{4} + 24n^{3} + 10n^{2} − 8n + 1 = (3n^{2} + 4n − 1)^{2} \end{aligned}

and

\begin{aligned}N_{n}N_{n+2} + N_{n+1} + 3 & = \frac{n(7n − 5)}{2} \frac{(n + 2)(7n + 9)}{2} + \frac{(n + 1)(7n + 2)}{2} + 3 \\ & = \frac{49n^{4} + 126n^{3} + 25n^{2} − 72n + 16}{4} = (\frac{7n^{2} + 9n − 4}{2})^{2}. \end{aligned}

If H_{n} denotes the nth heptagonal number, then

H_{n} = \frac{n(5n − 3)}{2}.

Solution to (c) by Russell Euler, Northwest Missouri State University, Maryville, Missouri; Joseph B. Dence, University of Missouri–St. Louis, St. Louis, Missouri; Lawrence Somer, The Catholic University of America, Washington, D.C.; J. Sriskandarajah, University of Wisconsin Center, Richland Center, Wisconsin; Herta T. Freitag, Roanoke, Virginia; and the proposer.

H_{n}H_{n+2} + H_{n+1} = (\frac{5n^{2} + 7n − 2}{2})^{2}.

Note that (5n^{2} + 7n − 2)/2 is an integer since

5n^{2} + 7n − 2 ≡ n^{2} + n ≡ n(n + 1) ≡ 0 (mod 2).

Solution to (c) by Joe Howard, New Mexico Highlands University, Las Vegas, New Mexico and Herta T. Freitag, Roanoke, Virginia.

H_{n}H_{n+2} + 3H_{n+1} − 3 = (\frac{5n^{2} + 7n}{2})^{2}.

Solution to (c) by Bob Prielipp, University of Wisconsin–Oshkosh, Oshkosh, Wisconsin and Herta T. Freitag, Roanoke, Virginia.

H_{n}H_{n+2} − H_{n+1} + 5 = (\frac{5n^{2} + 7n − 4}{2})^{2}.

One incorrect solution to part (c) was also received.

Herta T. Freitag has generalized this problem. Her generalization can be found in this issue of the Missouri Journal of Mathematical Sciences in her article entitled “From the Legacy of Pythagoras.”

84. [1995, 88] Proposed by W. F. Wheatley and James Ethridge, Jackson, Mississippi.

Let n be a positive integer.

(a) How many n–digit base 10 numbers are there whose digits from left–to–right are nondecreasing?

(b)^{∗} Consider a 2 × n array with base 10 digits in each entry of the array. Suppose that the 2 rows form n–digit base 10 numbers whose digits from left–to– right are nondecreasing and that the n columns form 2–digit base 10 numbers whose digits from bottom–to–top are nondecreasing. How many such arrays are there?

Solution I to part (a) by Ronald K. Smith, Graceland College, Lamoni, Iowa.

The answer is

\binom{n + 8}{n}.

There is a 1–1 correspondence between the sets A, B, and C where

A = {n − digit base 10 numbers whose digits

from left–to–right are nondecreasing},

B = {(x_{1}, x_{2}, …, x_{n}) | 1 ≤ x_{1} ≤ x_{2} ≤ ⋯ ≤ x_{n} ≤ 9},
C = {(y_{1}, y_{2}, …, y_{n+1}) | y_{1} + y_{2} + ⋯ + y_{n+1} = 8, y_{i} ≥ 0}.

To show that B is equivalent to C, set y_{1} = x_{1} − 1, y_{i} = x_{i} − x_{i−1} for i = 2, …, n and y_{n+1} = 9 − x_{n}. Then

∑_{i=1}^{n+1} y_{i} = 8, and y_{i} ≥ 0 for i = 1, 2, …, n + 1.

This is clearly reversible: x_{1} = 1 + y_{1}, x_{i} = x_{i−1} + y_{i} for i = 2, 3, …, n. The number of elements in C is

\binom{n + 8}{n}.

To see this, take a row of n + 8 1’s in parentheses. Choose n of them and convert to ,’s. Replace the string in each of the resulting n + 1 slots with the number of 1’s there (with any empty strings being replaced by 0). Since there were 8 1’s, the sum is clearly 8, and each slot is non-negative.

To count the number of elements in A directly, follow this algorithm. We will do an example with n = 5.

1. Put n + 8 1’s in parentheses: (1111111111111)

2. Choose n of them to convert to ,’s: (,111,,111,11,)

3. Treat as n + 1-tuple, replacing each string with the number of 1’s: (0,3,0,3,2,0)

4. Convert to n digits: d_{1} = y_{1} + 1, d_{i} = d_{i−1} + y_{i} for i = 2, … n: (1,4,4,7,9)

5. Treat as an integer in A: 14479 To reverse the procedure

4’. Convert an element of A to digits: (1,4,4,7,9) 3’. Convert to n+1-tuple: y_{1} = d_{1}−1, y_{i} = d_{i}−d_{i−1} for i = 2, …, n, y_{n+1} = 9−d_{n}:

(0,3,0,3,2,0) 2’. Replace numbers with strings of 1’s: (,111,,111,11,) 1’. Replace n commas with 1’s: (1111111111111)

Solution II to part (a) by N. J. Kuenzi, University of Wisconsin–Oshkosh, Oshkosh, Wisconsin.

The solution is based upon the following identity.

∑_{j=0}^{m} \binom{n − 1 + j}{n − 1} = \binom{n + m}{n}.

For d = 1, 2, …, 9, let A(n, d) be the number of n–digit base 10 numbers satisfying the left–to–right nondecreasing condition and having right digit d. Note for n ≥ 2 the right digit of such a number cannot be 0. For n = 1,

A(1, d) = 1 = \binom{d}{0}.

For n = 2,

A(2, d) = d = \binom{d}{1}.

For n ≥ 2, consider A(n + 1, d). With right digit d the n leftmost digits can be any of the n–digit numbers satisfying the left–to–right condition and having rightmost digit 1 through d. So,

A(n + 1, d) = ∑_{j=1}^{d} A(n, j).

Using this summation, we have

A(3, d) = ∑_{j=1}^{d} A(2, j) = ∑_{j=1}^{d} \binom{j}{1} = \binom{d + 1}{2}.

Suppose

A(n, d) = \binom{n − 2 + d}{n − 1}

for d = 1, 2, …, 9. Then

\begin{aligned}A(n + 1, d) & = ∑_{j=1}^{d} A(n, j) = ∑_{j=1}^{d} \binom{n − 2 + j}{n − 1} \\ & = ∑_{k=0}^{d−1} \binom{n − 1 + k}{n − 1} = \binom{n − 1 + d}{n}. \end{aligned}

So by the principle of mathematical induction

A(n, d) = \binom{n − 2 + d}{n − 1}

for n ≥ 2 and d = 1, 2, …, 9. Now the number of n–digit base 10 numbers which satisfy the left–to–right nondecreasing condition is the same as the number of (n + 1)–digit base 10 numbers satisfying the left–to–right nondecreasing condition and having right digit 9. Thus, the solution is given by

A(n + 1, 9) = \binom{n + 8}{n}.

Solution III to part (a) by N. J. Kuenzi, University of Wisconsin–Oshkosh, Oshkosh, Wisconsin.

Any n–digit base 10 number whose digits from left–to–right are nondecreasing can be thought of as a string of x_{1} 1’s, followed by a string of x_{2} 2’s, etc. with

x_{1} + x_{2} + ⋯ + x_{9} = n

and x_{i} ≥ 0, i = 1, 2, …, 9. For example, the 7–digit number 2355778 has

x_{1} = x_{4} = x_{6} = x_{9} = 0, x_{2} = x_{3} = x_{8} = 1, and x_{5} = x_{7} = 2.

If

x_{1} = 2, x_{2} = 3, x_{5} = x_{7} = 1, and x_{3} = x_{4} = x_{6} = x_{8} = x_{9} = 0,

the 7–digit number is 1122257.

The number of solutions in nonnegative integers to the equation

x_{1} + x_{2} + ⋯ + x_{9} = n

is

\binom{n + 8}{n} = \binom{n + 8}{8}.

(See Theorem 2, page 74, Introduction to Combinatorics, Berman and Fryer, Academic Press, 1972.) Hence, for n ≥ 2, the number of n–digit base 10 numbers whose digits from left–to–right are nondecreasing is

\binom{n + 8}{n}.

Similarly, the number of n–digit base b numbers whose digits from left–to–right are nondecreasing is

\binom{n + b − 2}{n}.

Also solved by Alan H. Rapoport, Ashford Medical Center, Santurce, Puerto Rico and the proposers.

Comment by N. J. Kuenzi, University of Wisconsin–Oshkosh, Oshkosh, Wisconsin.

Suppose the nondecreasing condition is changed to nonincreasing. Then any n–digit base 10 number whose digits from left–to–right are nonincreasing can be thought of as a string of x_{9} 9’s, followed by a string of x_{8} 8’s, etc. with

x_{0} + x_{1} + ⋯ + x_{9} = n

and x_{i} ≥ 0, i = 0, 1, …, 9. The number of nonnegative integer solutions to the equation

x_{0} + x_{1} + ⋯ + x_{9} = n

is

\binom{n + 9}{n} = \binom{n + 9}{9}.

For n ≥ 2, only the solution x_{0} = n does not correspond to an n–digit number satisfying the nonincreasing condition. Hence, for n ≥ 2, the number of n–digit base 10 numbers whose digits from left–to–right satisfy the nonincreasing condition is

\binom{n + 9}{n} − 1.

Similarly, for n ≥ 2 the number of n–digit base b numbers whose digits from left– to–right satisfy the nonincreasing condition is

\binom{n + b − 1}{n} − 1.

Comment on part (b) by Alan H. Rapoport, Ashford Medical Center, Santurce, Puerto Rico. I have found by brute force that the number of 2 × 1 arrays satisfying the condition in part (b) is 45, the number of 2 × 2 arrays is 825, and the number of 2 × 3 arrays is 9075. This suggests the following conjecture. The total number of 2 × n arrays satisfying the condition in part (b) is

\frac{(8 + n)!}{8!n!} · \frac{(9 + n)!}{9!(n + 1)!}.

Furthermore, I would like to offer the following generalization which is a pure guess. The number of 2 × n arrays satisfying the condition in part (b) is

\frac{(8 + n)!}{8!n!} · \frac{(9 + n)!}{9!(n + 1)!} · 1!.

The number of 3 × n arrays satisfying a similar condition to part (b) is

\frac{(8 + n)!}{8!n!} · \frac{(9 + n)!}{9!(n + 1)!} · \frac{(10 + n)!}{10!(n + 2)!} · 1! · 2!.

The number of 4 × n arrays satisfying a similar condition to part (b) is

\frac{(8 + n)!}{8!n!} · \frac{(9 + n)!}{9!(n + 1)!} · \frac{(10 + n)!}{10!(n + 2)!} · \frac{(11 + n)!}{11!(n + 3)!} · 1! · 2! · 3!.

And so on. æ