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.

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.

Discussion

Copyright © 1996-2008 Alexander Bogomolny

An n-sequence (x_l, x₂, ... , x_n) is stable if further iteration (as described in the problem) produces no change in the sequence. We show that every finite sequence is ultimately stable. An inductive argument is suggested since the stability of the (n-1)-sequence (x₂, x₃, ... , x_n) is not affected by the value of x_l.

The ultimate stability of 1-sequences is trivial, so suppose that every k-sequence is ultimately stable, and consider the (k+1)-sequence (x_l, x₂, ... , x_k+1). Iterate until the k-sequence (x₂, x₃, ... , x_k+1) is stable; suppose that the sequence becomes (x'₁, x'₂, ... , x'_k+1). Iterate again to get (x''₁, x'₂, ... , x'_k+1).

Suppose first that x''₁ ≥ x'₁. Iterate again to get (x'''₁, x'₂, ... , x'_k+1).; evidently x'''₁ ≥ x''₁, hence the sequence (x'₁, x''₁, x'''₁, ... ) is nondecreasing. But this sequence is bounded above (by k), so it must be ultimately constant. That is, the original (k+1)-sequence must be ultimately stable.

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

An associated combinatorial problem would be to enumerate all stable k-sequences.

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 n-sequence terminates ultimately in the following particular stable sequence (n-1, n-2, ... , 0) after at most n iterations.

The proof is by induction on the following statement: Let the initial n-sequence be (x_l(0), x₂(0), ... , x_n(0)). If after k iterations (1 ≤ k ≤ n) we reach the sequence (x_l(k), x₂(k), ... , x_n(k)), then

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.

Copyright © 1996-2008 Alexander Bogomolny