Conference rusure::math

272.0. "A collection question" by HARE::STAN () Tue Apr 30 1985 13:13

Given a finite sequence of non-negative integers (a, b, c, ...)
one can define a collection process as follows:

	Find the first pair of consecutive terms y, x that are
	out of order (i.e. y>x), remove them from the sequence,
	and replace them by the three terms: x, y, z where
	z is obtained by concatenating together the binary
	representations of y and x (in that order).

The process terminates when the resulting sequence is in non-descending order.

For example:

(1, 0) => (0, 1, 10)

(1, 0, 0) => (0, 1, 10, 0) => (0, 1, 0, 10, 100) => (0, 0, 1, 10, 10, 100)

[All numbers are represented in binary.]

The question is this:

Does the collection process applied to (1, 0, 0, 0) ever terminate?

The process begins as follows:

(1, 0, 0, 0) => (0, 1, 10, 0, 0)
	     => (0, 1, 0, 10, 100, 0)
	     => (0, 0, 1, 10, 10, 100, 0)
	     => (0, 0, 1, 10, 10, 0, 100, 1000)
	     => (0, 0, 1, 10, 0, 10, 100, 100, 1000)
	     => (0, 0, 1, 0, 10, 100, 10, 100, 100, 1000)
	     => (0, 0, 0, 1, 10, 10, 100, 10, 100, 100, 1000)
	     => (0, 0, 0, 1, 10, 10, 10, 100, 10010, 100, 100, 1000)
	     => (0, 0, 0, 1, 10, 10, 10, 100, 100, 10010, 10010100, 100, 1000)
	     => etc.

Another question is:
Does the collection process applied to (1, 1, 1, 0) ever terminate?

Not soon, at any rate: in either case the cycle with 29 numbers in it
has one number of more than 32 bits in it, so one can no longer check the
arithmetic with VAX longwords. - Lynn

Even less likely. I looked at the case where (if the strings got above 32
bits long) one only exchanges if the lengths of two adjacent numbers are
wrong, and it doesn't quit. I generated strings > 500 digits this way.
-Lynn

A proof that the process never ends would be neat.

Of course it never terminates.  In your example:

(1, 0, 0, 0) => (0, 1, 10, 0, 0)
	     ...
	     => (0, 0, 0, 1, 10, 10, 10, 100, 10010, 100, 100, 1000)

Note the subsequence (10010, 100, 100, 1000) must also be collected,
and its similarity to the (1, 0, 0, 0) being collected.

Can you define a different ordering function over the integers, and with 1>0,
so the collection process, when applied to (1,0,0,0) *does* terminate?