Solutions
-
276.
-
Let a, b, c be the lengths of the sides
of a triangle and let
s = 1/2(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
|
tan2 a+ tan2 b+ tan2 g ³ 1 . |
|
Since a+ b+ g = 90°,
|
|
|
= tanatanb+ tanbtang+tang+ tana |
| |
| |
| £ |
Ö
|
tan2 a+ tan2 b+ tan2 g
|
|
Ö
|
tan2 b+ tan2 g+ tan2 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)2 + (v - w)2 + (w - u)2 ³ 0 implies that u2 + v2 + w2 ³ uv + vw + wu.
Hence
|
|
|
+ |
1
(s - b)2
|
+ |
1
(s - c)2
|
|
| |
| |
|
³ |
1
(s - a)(s - b)
|
+ |
1
(s - b)(s - c)
|
+ |
1
(s - c)(s - a)
|
|
| |
| |
| = |
(s - a) + (s - b) + (s - c)
(s - a)(s - b)(s - c)
|
= |
s
(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) = r2s, 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
|
|
1
(s - a)2
|
+ |
1
(s - b)2
|
³ |
2
(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
a1, a2, ¼, an in order around the ring, and we
wish to increase a1 by one more than the rest. Begin
by adding 1 to each of a1, a2, ¼, am; then add 1
to each of am+1, am+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 a1 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) = (-(5k2 ±2k), -1) and (m, n) = (-a2, 0).
Suppose, if possible, that 4mn - m - n = x2 with at least
one of m and n, say m, positive. Then
(4m - 1)(4n - 1) = 4x2 + 1. There must be at least one
prime q congruent to -1 modulo 4 which divides 4m - 1
and so 4x2 + 1. Therefore,
(2x)2 º -1 (mod q), whence (2x)4 º 1 (mod q).
By Fermat's Little Theorem, (2x)q-1 º 1 (mod q).
Observe that neither 2x nor (2x)3 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)2 º (2x)2 \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) = (3k2, 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) = k2 , |
|
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)
2
|
, |
|
|
0 = ±2 ±5 ±¼±(3k - 1) º 2 + 5 + ¼+ (3k - 1) = |
k(3k + 1)
2
|
, |
|
|
0 = ±3 ±6 ±¼±3k º 3(1 + 2 + ¼+ k) = |
3k(k+1)
2
|
. |
|
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 2n-k-1
such possibilities. Similarly, there are 2n-k-1 possibilities
where k is the final term of the sequence. Thus, k occurs
2n-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 2s-1 ·2n - k - s - 1 = 2n - 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)2n-k-2
occurrences of k in an intermediate position in the sequences.
Therefore, the total number of occurrences of k in all
sequences is
|
2n-k + (n - k - 1)2n-k-2 = (n - k + 3)2n-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
|
x2 + (y - a)x + (y2 - ay + b) = 0 . |
|
This is solvable for real values of x if and only if
|
(y - a)2 - 4(y2 - ay + b) ³ 0 Û -3y2 + 2ay + (a2 - 4b) ³ 0 . |
|
Since -3y2 + 2ay + (a2 - 4b) is negative for large values
of y, the inequality -3y2 + 2ay + (a2 - 4b) ³ 0 is
solvable for real values of y if and only there are
real solutions to the quadratic equation 3y2 - 2ay -(a2 - 4b) = 0, and the condition for this is a2 ³ 3b.
So, if a2 ³ 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
a2 ³ 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)2 + (3y - a)2 = 4(a2 - 3b) . |
|
Hence, we require that a2 ³ 3b. On the other hand,
if a2 ³ 3b, then we can determine a real pair (u, v)
for which 3u2 + v2 = 4(a2 - 3b). Then
|
(x, y, z) = |
æ
è
|
|
3u - v + 2a
6
|
, |
a + v
3
|
, |
2a - 3u - v
6
|
|
ö
ø
|
|
|
satisfies the system. There are 21 of the possible 36 outcomes of
casting the dice for which a2 ³ 3b, so the desired
probability is 7/12.
Comment. The necessity of the condition a2 ³ 3b
also follows from
|
a2 - 3b = (x2 + y2 + z2) - (xy + yz + zx) = |
1
2
|
[(x - y)2 + (y - z)2 + (z - x)2] ³ 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 x1, x2, x3, x4, x5 be the five
numbers in order around the pentagon at some particular point,
and suppose that x3 < 0 and we change the numbers to
x1, x2 + x3, -x3, x4 + x3, x5. 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 = (x1 - x3)2 + (x2 - x4)2 + (x3 - x5)2 +(x4 - x1)2 + (x5 - x2)2 , |
|
and T be the corresponding sum of squares after the
operation has been performed:
|
T = (x1 + x3)2 + (x2 - x4)2 + (x3 + x5)2+ (x4 + x3 - x1)2 + (x5 - x2 - x3)2 . |
|
Then S - T = -2x3 (x1 + x2 + x3 + x4 + x5) > 0
since x3 < 0 and x1 + x2 + x3 + x4 + x5 > 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.
