# Right Replacement

The applet below illustrates a problem from *The American Mathematical Monthly* (Vol. 75, No. 3. (Mar., 1968), pp. 299-301) proposed by D. W. Burns, Woodstock, Ill.

Given a finite sequence of nonnegative integers, consider the process of replacing each of the integers by the number of integers to its right which are smaller. Repeat the process in turn on each of the sequences obtained. Show that one will finally obtain a sequence such that repetition of the process makes no further change, i.e.,each integer equals the number of smaller integers to its right.

Many solutions were submitted, two have been published. One by induction and another so general that it prompted me to consider a few modifications of the problem. The problem requires to compare integers with those lying on their right. The applet allows to modify the condition of comparison from "smaller than" (LT) to "smaller than or equal to" (LE), "greater than" (GT), "greater than or equal to" (GE). The behavior of the iterations is different in every case, remarkably so in the last one, GE.

What if applet does not run? |

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

### Solution 1

This solution is by E. S. Langford, U. S. Naval Postgraduate School.

An n-sequence _{l}, x_{2}, ... , x_{n})_{2}, x_{3}, ... , x_{n})_{l}.

The ultimate stability of 1-sequences is trivial, so suppose that every k-sequence is ultimately stable, and consider the _{l}, x_{2}, ... , x_{k+1})._{2}, x_{3}, ... , x_{k+1})_{1}, x'_{2}, ... , x'_{k+1})._{1}, x'_{2}, ... , x'_{k+1}).

Suppose first that x''_{1} ≥ x'_{1}. Iterate again to get _{1}, x'_{2}, ... , x'_{k+1})._{1} ≥ x''_{1},_{1}, x''_{1}, x'''_{1}, ... ) is nondecreasing. But this sequence is bounded above (by k), so it must be ultimately constant. That is, the original

A similar argument holds if x''_{1} < x'_{1}, since the sequence (x'_{1}, x''_{1}, x'''_{1}, ... ) is bounded below by 0.

An associated combinatorial problem would be to enumerate all stable

A similar problem suggests itself when we replace "smaller" by "smaller than
or equal to" in the statement of the problem. In this case we can give the following more complete answer: Every

The proof is by induction on the following statement: Let the initial
_{l}(0), x_{2}(0), ... , x_{n}(0))._{l}(k), x_{2}(k), ... , x_{n}(k)),

x_{1}(k)≥ k-1, x_{2}(k)≥ k-1, ... x_{n-k}(k)≥ k-1,

x_{n-k+1}(k)= k-1, x_{n-k+2}(k)= k-2, ... x_{n}(k)= 0.

### Solution 2

This solution by C. B. A. Peck, Ordnance Research Laboratory, State College, Pa. We generalize the problem as follows: Given a finite sequence of objects from a set S, consider the process of replacing each object by an object in S depending only on the collection of objects to its right, the number of times an object occurs in the collection being taken into account. Repeat the process, etc.

The empty set is such a collection, and the first object (counting right to left) in the second sequence is thus determined and fixed thereafter. In general the n^{th} object in the final sequence is determined by at most the n^{th} sequence after the first.

It is not necessary that the process be applied to each object of the sequence, provided that some change results at each application. Furthermore, the arrangement of the objects in the sequence could be changed, if the same change is applied to all the sequences.

The change in the problem from "smaller than" to "greater than" makes iteration converge to a (stable) sequence of all zeros. (The last element becomes 0 on the first iteration and then others, perhaps a few at a time, also vanish for a similar reason.)

However, a change to "greater than or equal to" engenders a different behavior. In all examples I ran, the iterations settled to a 2-cycle, a repeating pattern of two sequences. This is obvious if we start with a monotone nonincreasing sequence. The next iteration will result in a sequence with all the terms 0 and the next one will then be

(n - 1, n - 2, n - 3, ..., 2, 1, 0)

which again leads to the 0 sequence. In a more general case, one of the sequences in the 2-cycle consists of groups of contiguous nonincreasing sequences whereas the other one parallels the first but in which the (same) groups consist of nondecreasing sequences.

The second solution above purports to encompass such situation but wrongly predicts convergence of the iterations.

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

65094971 |