Solutions

276.

Let a, b, c be the lengths of the sides of a triangle and let s = ¹/₂(a + b + c) be its semi-perimeter and r be the radius of the inscribed circle. Prove that

(s - a)^-2 + (s - b)^-2 + (s - c)^-2 ³ r^-2

and indicate when equality holds.

Solution 1. Let the angles of the triangle at A, B, C be 2 a, 2 b, 2 g, respectively, Then (s - a)^-1 = (tana) /r, etc., and the ineqaulity is equivalent to

tan² a+ tan² b+ tan² g ³ 1 .

Since a+ b+ g = 90^°,

= tanatanb+ tanbtang+tang+ tana

tan² a+ tan² b+ tan² g

tan² b+ tan² g+ tan² a

by the Cauchy-Schwarz Inequality. Equality occurs if and only if tana = tanb = tang = 1/Ö3, i.e., when the triangle is equilateral.

Solution 2. Let u = (s - a)^-1, v = (s - b)^-1 and w = (s - c)^-1. Then (u - v)² + (v - w)² + (w - u)² ³ 0 implies that u² + v² + w² ³ uv + vw + wu. Hence

(s - a)²

(s - b)²

(s - c)²

(s - a)(s - b)

(s - b)(s - c)

(s - c)(s - a)

(s - a) + (s - b) + (s - c)

(s - a)(s - b)(s - c)

Since the area of the triangle is rs = Ö{s(s - a)(s - b)(s - c)}, we have that (s - a)(s - b)(s - c) = r²s, and the desired result follows. Equality occurs if and only if u = v = w Û a = b = c.

Comment. We can also use the Arithmetic-Geometric Means Inequality to obtain that

(s - a)²

(s - b)²

(s - a)(s - c)

2(s - c)

(s - a)(s - b)(s - c)

etc., and add the inequalities to get the result. Many solvers neglected to mention when equality occurred.

277.: Let m and n be positive integers for which m < n. Suppose that an arbitrary set of n integers is given and the following operation is performed: select any m of them and add 1 to each. For which pairs (m, n) is it always possible to modify the given set by performing the operation finitely often to obtain a set for which all the integers are equal?

Solution. If the task can be completed, then it can be completed in particular when the sum of the integers in the set is equal to 1 (for example, if there is one 1 and the rest all 0). Suppose that the operation is performed x times, so that the sum is increased by m each time, until all the numbers are equal to y. Then we must have 1 + mx = ny, from which it follows that the greatest common divisor of m and n is equal to 1.

Conversely, suppose that the greatest common divisor of m and n is equal to 1. Then it is possible to find positive integers u and v for which mu = nv + 1. For convenience, let us suppose that the numbers in the set are arranged in a ring. We show that it is possible to increase any of these numbers by one more than we increase the rest of the numbers if the operation is repeated suficiently often. Suppose the numbers are a₁, a₂, ¼, a_n in order around the ring, and we wish to increase a₁ by one more than the rest. Begin by adding 1 to each of a₁, a₂, ¼, a_m; then add 1 to each of a_m+1, a_m+2 and so on for m numbers. Each time, increase a run of m numbers by 1, starting off immediately after the last number increased on the previous round. Doing this u times, we find that each number is increased by v except for a₁ which is increased by v + 1.

To achieve our task, begin with a sequence of operations, each of which increases the minimum number of the set by one more than each other number. After a finite number of times of doing this, the difference between the maximum and minimum numbers of the set will be reduced by 1. Eventually, this difference will be reduced to zero and the job will be done.

Comment. One approach is to increase the smallest m numbers of the set by 1 each time around. This looks as though it should succeed, but it seems difficult to establish that this is so.

278.: (a) Show that 4mn - m - n can be an integer square for infinitely many pairs (m, n) of integers. Is it possible for either m or n to be positive?

: (b) Show that there are infinitely many pairs (m, n) of positive integers for which 4mn - m - n is one less than a perfect square.

Solution. (a) Two possible solutions are (m, n) = (-(5k² ±2k), -1) and (m, n) = (-a², 0). Suppose, if possible, that 4mn - m - n = x² with at least one of m and n, say m, positive. Then (4m - 1)(4n - 1) = 4x² + 1. There must be at least one prime q congruent to -1 modulo 4 which divides 4m - 1 and so 4x² + 1. Therefore, (2x)² º -1 (mod q), whence (2x)⁴ º 1 (mod q). By Fermat's Little Theorem, (2x)^q-1 º 1 (mod q). Observe that neither 2x nor (2x)³ is congruent to ±1 (mod q), so that 4 is the minimum positive value of r for which (2x)^r º 1 (mod q). Let q = 4s + 3. Then

(2x)^q-1 = (2x)^4s ·(2x)² º (2x)² \not º 1

(mod q), which contradicts the Fermat result. Hence, it is not possible for either m or n to be positive.

(b) One set of solutions is given by (m, n) = (3k², 1).

279.: (a) For which values of n is it possible to construct a sequence of abutting segments in the plane to form a polygon whose side lengths are 1, 2, ¼, n exactly in this order, where two neighbouring segments are perpendicular?

: (b) For which values of n is it possible to construct a sequence of abutting segments in space to form a polygon whose side lengths are 1, 2, ¼, n exactly in this order, where any two of three sucessive segments are perpendicular?

Solution. (a) Since the direction of the sides alternates around the polygon, n must be even. Let n = 2k. Suppose that the odd sides of the polygon are parallel to the x-axis and the even sides to the y-axis. Then along each odd side, the abscissa of the vertices increases or decreases by an odd integer, and for all the sides, the net increase of the abscissae is zero. In other words, modulo 2,

0 = ±1 ±3 ±5 ±¼±(2k -1) º 1 + 3 + 5 + ¼+ (2k - 1) = k² ,

whence k is even, and n is a multiple of 4. Similarly, consideration of the ven sides leads to, modulo 4,

0 = 2(±1 ±2 ±3 ±¼±k) º 2(1 + 2 + ¼+ k) = k(k+1)

from which we infer that k must be a multiple of 4. Hence, it is necessary that n is a multiple of 8.

Now, suppose that n is a multiple of 8. For n = 8, we can construct the octagon with vertices (0, 0), (1, 0), (1, 2), (-2, 2), (-2, -2), (-7, -2), (-7, -8), (0, -8), corresponding to the sums

1 - 3 - 5 + 7 = 2 - 4 - 6 + 8 = 0 .

In general, for n = 8r (r ³ 1), we can take the polygon corresponding to the sums

1 + 3 + ¼+ (2r - 1) - (2r + 1) - ¼- (6r - 1)+ (6r + 1) + ¼+ (8r - 1) = 0

and

2 + 4 + ¼+ 2r - (2r + 2) - ¼- (6r) + (6r + 2)+ ¼+ 8r = 0 .

(b) By the condition of the problem, the sides of the parallelogram must cycle through the three coordinate directions in turn, so n must be a multiple of 3, say n = 3k. As in (a), we can argue that, for some choice of signs, with the congruence taken modulo 2,

0 = ±1 ±4 ±¼±(3k - 2) º 1 + 4 + ¼+ (3k - 2) =

k(3k - 1)

0 = ±2 ±5 ±¼±(3k - 1) º 2 + 5 + ¼+ (3k - 1) =

k(3k + 1)

0 = ±3 ±6 ±¼±3k º 3(1 + 2 + ¼+ k) =

3k(k+1)

Hence, k(3k - 1), k(3k + 1) and 3k(k+1) are all divisible by 4. This is possible if and only if k is a multiple of 4, say 4r, so that n = 12r is a multiple of 12.

On the other hand, suppose that n = 12r, for r ³ 1. We can construct polyons corresponding to the sums

1 + 4 + ¼+ (3r - 2) - (3r + 1) - ¼- (9r - 2)+ (9r + 1) + ¼+ (12r - 2) = 0 ,

2 + 5 + ¼+ (3r - 1) - (3r + 2) - ¼- (9r - 1)+ (9r + 2) + ¼+ (12r - 1) = 0 ,

3 + 6 = ¼+ 3r - (3r + 3) - ¼- 9r + (9r + 3)+ ¼+ 12r = 0 ,

for the lengths of the sides in the three respective coordinate directions.

280.: Consider all finite sequences of positive integers whose sum is n. Determine T(n, k), the number of times that the positive integer k occurs in all of these sequences taken together.

Solution. Each ordered partition of n corresponds to a placement of vertical lines between certain adjacent pairs of dots in a line of n dots. For example, the sequence { 4, 2, 3, 1 } partitioning 10 corresponds to

····|··|···|· .

Suppose, first that k = n. Then there is one possible sequence, and so T(n, n) = 1. If k = n-1, then there are two sequences ({ 1, n-1 } and { n-1, 1 }), so T(n, n-1) = 2. Henceforth, let 2 £ k £ n-2.

If k is the initial term of the sequence, the first vertical line will occur after the kth dot, and there are n - k - 1 position between adjacent remaining dots in which lines might be placed to signify the sequences beginning with k. There are 2^n-k-1 such possibilities. Similarly, there are 2^n-k-1 possibilities where k is the final term of the sequence. Thus, k occurs 2^n-k times as the first or the last term of a sequence.

Suppose that that k occurs in an intermediate position, and that the sum of the terms preceding k is equal to s and the sum of the terms succeeding k is equal to n - k - s > 0. By an argument similar to that in the previous paragraph, there are 2^s-1 ·2^{n - k - s - 1} = 2^{n - k - 2} sequences where the terms before k have a sum s. Since we have that 1 £ s £ n - k - 1, there are (n - k - 1)2^n-k-2 occurrences of k in an intermediate position in the sequences.

Therefore, the total number of occurrences of k in all sequences is

2^n-k + (n - k - 1)2^n-k-2 = (n - k + 3)2^n-k ,

for 1 £ k £ n-1, and T(n, n) = 1.

281.: Let a be the result of tossing a black die (a number cube whose sides are numbers from 1 to 6 inclusive), and b the result of tossing a white die. What is the probability that there exist real numbers x, y, z for which x + y + z = a and xy + yz + zx = b?

Solution. Eliminating z from the system, we obtain the equation

x² + (y - a)x + (y² - ay + b) = 0 .

This is solvable for real values of x if and only if

(y - a)² - 4(y² - ay + b) ³ 0 Û -3y² + 2ay + (a² - 4b) ³ 0 .

Since -3y² + 2ay + (a² - 4b) is negative for large values of y, the inequality -3y² + 2ay + (a² - 4b) ³ 0 is solvable for real values of y if and only there are real solutions to the quadratic equation 3y² - 2ay -(a² - 4b) = 0, and the condition for this is a² ³ 3b.

So, if a² ³ 3b, we can find a solution for the inequality in y, and then solve the equation for x, and then set z = a - x - y. So the system is solvable if and only if a² ³ 3b, and this occurs when a ³ 5 or when (a, b) = (2, 1), (3, 1), (3, 2), (3, 3), (4, 1), (4, 2),(4, 3), (4, 4), (4, 5). (In particular, when (a, b) = (3, 3), (x, y, z) = (a/3, a/3, a/3) necessarily.) The required probability is 21/36 = 7/12.

Solution 2. The system of equations is equivalent to the system: xy + (x + y)[a - (x + y)] = b; z = a - (x + y). The first of these equations can be written as

3(2x + y - a)² + (3y - a)² = 4(a² - 3b) .

Hence, we require that a² ³ 3b. On the other hand, if a² ³ 3b, then we can determine a real pair (u, v) for which 3u² + v² = 4(a² - 3b). Then

(x, y, z) =

æ
è

3u - v + 2a

a + v

2a - 3u - v

ö
ø

satisfies the system. There are 21 of the possible 36 outcomes of casting the dice for which a² ³ 3b, so the desired probability is 7/12.

Comment. The necessity of the condition a² ³ 3b also follows from

a² - 3b = (x² + y² + z²) - (xy + yz + zx) =

[(x - y)² + (y - z)² + (z - x)²] ³ 0 .

282.: Suppose that at the vertices of a pentagon five integers are specified in such a way that the sum of the integers is positive. If not all the integers are non-negative, we can perform the following operation: suppose that x, y, z are three consecutive integers for which y < 0; we replace them respectively by the integers x + y, -y, z + y. In the event that there is more than one negative integer, there is a choice of how this operation may be performed. Given any choice of integers, and any sequence of operations, must we arrive at a set of nonnegative integers after a finite number of steps?

: For example, if we start with the numbers (2, -3, 3, -6, 7) around the pentagon, we can produce (1, 3, 0, -6, 7) or (2, -3, -3, 6, 1).

Solution. Let x₁, x₂, x₃, x₄, x₅ be the five numbers in order around the pentagon at some particular point, and suppose that x₃ < 0 and we change the numbers to x₁, x₂ + x₃, -x₃, x₄ + x₃, x₅. Observe that under the operation, the sum of the numbers remains unchanged, and so always positive, Let S be the sum of the squares of the differences

S = (x₁ - x₃)² + (x₂ - x₄)² + (x₃ - x₅)² +(x₄ - x₁)² + (x₅ - x₂)² ,

and T be the corresponding sum of squares after the operation has been performed:

T = (x₁ + x₃)² + (x₂ - x₄)² + (x₃ + x₅)²+ (x₄ + x₃ - x₁)² + (x₅ - x₂ - x₃)² .

Then S - T = -2x₃ (x₁ + x₂ + x₃ + x₄ + x₅) > 0 since x₃ < 0 and x₁ + x₂ + x₃ + x₄ + x₅ > 0.

Each time we perform the operation, the sum S of the squares decreases. Since this sum is a positive integer, this can happen only finitely often, so we must come to a stage at which there is no negative number available to operate on. The result follows.

Comment. It appears to be the case that the number of operations required and the final configuration when all the numbers are nonnegative is independent of the choice of the negative number on which to operate at each stage.