Kvant Math Problem 97

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m46s
Source on kvant.digital

Problem

In the trapezoid $ABCD$ with bases $AB=a$ and $CD=b$, a segment $A_1B_1$ is drawn connecting the midpoints of the diagonals. In the resulting trapezoid $A_1B_1CD$, a segment $A_2B_2$ is again drawn connecting the midpoints of the diagonals, and so on (Fig. 1). Can any number appear twice in the sequence of segment lengths $AB$, $A_1B_1$, $A_2B_2$, ...? Will this sequence be monotonic (increasing or decreasing)? Does it converge to a limit?

Insert illustration

A. L. Rosenthal

Exploration

Let $x_n$ denote the length of the base of the $n$th trapezoid obtained in the process, with $x_0=AB=a$ and with the other base always equal to $b=CD$.

The first task is to determine the length of the segment joining the midpoints of the diagonals of a trapezoid. A coordinate model is natural. Put

$$D=(0,0),\qquad C=(b,0),\qquad A=(p,h),\qquad B=(p+a,h).$$

Then the midpoint of diagonal $AC$ is

$$M=\left(\frac{p+b}{2},\frac h2\right),$$

and the midpoint of diagonal $BD$ is

$$N=\left(\frac{p+a}{2},\frac h2\right).$$

Hence

$$MN=\left|\frac{p+b}{2}-\frac{p+a}{2}\right| =\frac{|b-a|}{2}.$$

Thus the new upper base depends only on the two bases of the trapezoid and equals half their difference.

If $x_n$ denotes the upper base at step $n$, then

$$x_{n+1}=\frac{|b-x_n|}{2}.$$

Everything reduces to studying this recurrence.

Try a few values. Let $b=10$, $a=2$. Then

$$2,\ 4,\ 3,\ 3.5,\ 3.25,\ldots$$

The sequence oscillates and approaches something near $10/3$.

Let $b=10$, $a=20$. Then

$$20,\ 5,\ 2.5,\ 3.75,\ 3.125,\ldots$$

Again it approaches $10/3$.

The fixed point satisfies

$$x=\frac{|b-x|}{2}.$$

If $x\le b$, then

$$x=\frac{b-x}{2},$$

hence

$$3x=b, \qquad x=\frac b3.$$

If $x>b$, then

$$x=\frac{x-b}{2},$$

hence $x=-b$, impossible. So the unique fixed point is $b/3$.

The delicate point is proving monotonicity. The sequence itself is generally not monotone, as the examples show. However, after the first step all terms lie in $[0,b]$, because

$$x_{n+1}=\frac{|b-x_n|}{2}\le \frac b2.$$

On $[0,b]$ the recurrence becomes

$$x_{n+1}=\frac{b-x_n}{2}.$$

Then

$$x_{n+1}-\frac b3 =-\frac12\left(x_n-\frac b3\right).$$

The deviations from $b/3$ alternate in sign and are halved each time. This immediately gives convergence and shows that equal values can occur only if the sequence has already reached the fixed point.

Problem Understanding

This is a Type C problem. We are asked to determine the behavior of the sequence of lengths

$$AB,\ A_1B_1,\ A_2B_2,\ldots$$

generated by repeatedly replacing a trapezoid by the trapezoid whose upper base is the segment joining the midpoints of its diagonals.

The questions are whether a length can occur twice, whether the sequence is monotone, and whether it converges.

The core difficulty is to find a recurrence relation for the successive lengths. Once the length of the segment joining the midpoints of the diagonals is expressed in terms of the two bases, the geometric problem becomes a one-dimensional recurrence.

The answer is that the recurrence is

$$x_{n+1}=\frac{|b-x_n|}{2}.$$

No value can occur twice unless the sequence has reached the fixed point $b/3$. The sequence is generally not monotone. It converges to the limit $b/3$.

Proof Architecture

The first lemma states that in a trapezoid with bases of lengths $u$ and $v$, the segment joining the midpoints of the diagonals has length $\frac{|u-v|}{2}$; this follows from a coordinate computation.

The second lemma states that if $x_n$ is the upper base length at step $n$, then

$$x_{n+1}=\frac{|b-x_n|}{2};$$

this is an immediate application of the first lemma.

The third lemma states that for every $n\ge1$,

$$0\le x_n\le \frac b2;$$

this follows directly from the recurrence.

The fourth lemma states that for every $n\ge1$,

$$x_{n+1}-\frac b3=-\frac12\left(x_n-\frac b3\right);$$

this uses the previous lemma to remove the absolute value.

The hardest point is establishing the exact linear relation with the fixed point $b/3$, because all conclusions about repetition, monotonicity, and convergence follow from it.

Solution

Let

$$x_0=a,$$

and for each $n\ge0$ let $x_n$ denote the length of the upper base of the trapezoid obtained after $n$ steps. The lower base remains $CD=b$ throughout the construction.

We first compute the length of the segment joining the midpoints of the diagonals of an arbitrary trapezoid.

Consider a trapezoid with bases of lengths $u$ and $v$. Choose coordinates

$$D=(0,0),\qquad C=(v,0),\qquad A=(p,h),\qquad B=(p+u,h).$$

The midpoint of diagonal $AC$ is

$$M=\left(\frac{p+v}{2},\frac h2\right),$$

and the midpoint of diagonal $BD$ is

$$N=\left(\frac{p+u}{2},\frac h2\right).$$

Since $M$ and $N$ have the same $y$ coordinate,

$$MN=\left|\frac{p+v}{2}-\frac{p+u}{2}\right| =\frac{|v-u|}{2}.$$

Applying this to the trapezoid at step $n$, whose bases have lengths $x_n$ and $b$, yields

$$x_{n+1}=\frac{|b-x_n|}{2}.$$

For every $n\ge0$,

$$x_{n+1}\le \frac b2.$$

Hence

$$0\le x_n\le \frac b2$$

for all $n\ge1$.

Consequently, for $n\ge1$ we have $x_n\le b$, so the recurrence simplifies to

$$x_{n+1}=\frac{b-x_n}{2}.$$

Subtracting $b/3$ from both sides gives

$$x_{n+1}-\frac b3 =\frac{b-x_n}{2}-\frac b3 =\frac{b-3x_n}{6} =-\frac12\left(x_n-\frac b3\right).$$

Define

$$d_n=x_n-\frac b3.$$

Then for $n\ge1$,

$$d_{n+1}=-\frac12 d_n.$$

Repeated application yields

$$d_n=\left(-\frac12\right)^{n-1}d_1, \qquad n\ge1.$$

Therefore

$$x_n=\frac b3+\left(-\frac12\right)^{n-1} \left(x_1-\frac b3\right).$$

Since

$$\left(-\frac12\right)^{n-1}\to0,$$

we obtain

$$\lim_{n\to\infty}x_n=\frac b3.$$

Thus the sequence always converges, and its limit is

$$\boxed{\frac b3}.$$

We now examine repetition of values. Suppose

$$x_m=x_n$$

for some $m<n$, with $m,n\ge1$. Then

$$\frac b3+\left(-\frac12\right)^{m-1} \left(x_1-\frac b3\right) = \frac b3+\left(-\frac12\right)^{n-1} \left(x_1-\frac b3\right).$$

Hence

$$\left[\left(-\frac12\right)^{m-1} - \left(-\frac12\right)^{n-1}\right] \left(x_1-\frac b3\right)=0.$$

The two powers are distinct because $m\ne n$, so

$$x_1=\frac b3.$$

Then every subsequent term equals $b/3$.

Thus a number can appear twice only in the exceptional case when the sequence reaches the fixed point $b/3$; otherwise all terms are distinct.

Finally, the relation

$$d_{n+1}=-\frac12 d_n$$

shows that the sign of $d_n$ alternates whenever $d_n\ne0$. Hence the terms lie alternately above and below $b/3$. A nonconstant sequence with this property cannot be monotone. The only monotone case is the constant sequence

$$x_n=\frac b3,$$

which occurs precisely when

$$x_1=\frac b3.$$

Since

$$x_1=\frac{|b-a|}{2},$$

this condition is equivalent to

$$|b-a|=\frac{2b}{3},$$

that is,

$$a=\frac b3 \quad\text{or}\quad a=\frac{5b}{3}.$$

Therefore the sequence is generally not monotone; it is monotone only in the constant case.

The determined value is

$$\boxed{\frac b3},$$

and equality is attained as the limit of every sequence generated by the construction.

Verification of Key Steps

The first delicate step is the formula for the midpoint segment. Using the coordinates above, the midpoint of $AC$ has $x$ coordinate $(p+v)/2$, while the midpoint of $BD$ has $x$ coordinate $(p+u)/2$. Their $y$ coordinates are equal, so the distance is the absolute difference of these $x$ coordinates. Any argument that assumes symmetry of the trapezoid would be invalid, because the trapezoid need not be isosceles.

The second delicate step is removing the absolute value. The recurrence alone does not permit replacing $|b-x_n|$ by $b-x_n$ for every $n$. The justification is that

$$x_{n+1}\le \frac b2,$$

which implies

$$x_n\le \frac b2<b$$

for all $n\ge1$. Only after proving this bound may one write

$$|b-x_n|=b-x_n.$$

The third delicate step is the claim about repeated values. Periodic behavior might seem possible because the recurrence alternates around the limit. The explicit formula

$$x_n=\frac b3+\left(-\frac12\right)^{n-1} \left(x_1-\frac b3\right)$$

eliminates this possibility. Distinct powers of $-1/2$ cannot be equal, so equality of two different terms forces $x_1=b/3$, after which every term is equal to $b/3$.

Alternative Approaches

Instead of coordinates, one may place the trapezoid in vector form. If $M$ and $N$ are the midpoints of the diagonals, then

$$\overrightarrow{MN} =\frac12\bigl((\overrightarrow C-\overrightarrow B) + (\overrightarrow A-\overrightarrow D)\bigr).$$

Using the fact that the bases are parallel, the vector on the right is half the difference of the base vectors. Taking lengths yields

$$MN=\frac{|u-v|}{2}.$$

The remainder of the argument is unchanged.

Another approach is to regard the recurrence as an affine contraction. After the first step it becomes

$$x_{n+1}=\frac b2-\frac12 x_n.$$

The map

$$T(x)=\frac b2-\frac12x$$

has fixed point $b/3$ and contraction ratio $1/2$. General contraction theory immediately gives convergence to $b/3$. The explicit computation with deviations from the fixed point is preferable here because it simultaneously yields convergence, nonmonotonicity, and the criterion for repeated values.