November 2002 solution

Solution to November 2002 Problem

The Kolakoski sequence 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, ... is an example of what people call a self-reading sequence: {a_n} is defined to be the sequence of 1's and 2's whose first term is 1, and each subsequent term an is the length of the nth run (of ones or twos). In more detail,

sequence	1,	2,2,	1,1,	2,	1,	2,2,	1,	2,2,	...
run length	1	2	2	1	1	2	1	2

Start with a₁ = 1. The rule says that the first run (which is a single 1) has length 1. Thus a₂ must be different, so that a₂ = 2. The second run therefore has length 2, which forces the third term, a₃, to be a two also. This completes the second run, so the third run begins with a 1; since its length is 2 we have a₄ = 1 and a₅ = 1. The fourth and fifth runs are consequently the singletons 2 then 1. And so on.

Problem for November:

Prove that 0.122112122122112... is irrational. (Recall that a number in decimal form is irrational if its digits are nonrepeating.)

We received correct solutions from Pierre Bornsztein (France) and Juan Mir Pieras (Spain). Their arguments are quite similar and very well presented. For the originals you can follow the links to our French and Spanish pages. What follows is a mixture of the two.

Solution to MP27.

Every sequence S = {s₁, s₂, ...} determines an associated sequence S' = {r₁, r₂, ...} that "reads S" in the sense that r_i is the length of the ith run of repeated numbers. So, for example, the sequence {1, 2, 3, 3, 4} is read by the associated sequence {1, 1, 2, 1}. Our problem concerns the family of self-reading sequences -- those for which S' = S. We also define the family A of sequences composed of the numbers 1 and 2 that, moreover, have no three consecutive terms that are equal. Finally, a sequence {s₁, s₂, ...} is called periodic if there is a positive integer p and an index K for which a_k+p = a_k for all k >= K; the smallest p for which this equality holds is called the period. Note that the Kolakoski sequence is the only self-reading sequence in A that begins with 1. Our goal is to show that any member of A that is periodic cannot be self-reading. This immediately implies that 0.1221122... cannot be rational (because it comes from a self-reading sequence by definition and, therefore, cannot be a repeating decimal).

Let S be a member of A having period p. Each block of p consecutive terms of S will eventually consist of o1 isolated ones, o₂ pairs of consecutive ones, t₁ isolated twos, and t₂ pairs of consecutive twos, where these numbers satisfy,

p = o₁ +t₁ +2(o₂ + t₂). (*) Of course, the associated sequence S' that reads S must also be periodic, eventually consisting of repeated blocks of o₁ + t₁ ones and of o₂ + t₂ twos. The length of the period of S' is therefore a divisor of o₁ + t₁ + o₂ + t₂ <= p. In fact, the period of S' could never equal p: Should o₁ +t₁ + o₂ + t₂ = p, then necessarily o₂ + t₂ = 0 (from (*)); that would force S to consist of alternating 1's and 2's while S' = {1, 1, 1, ...} (so that the periods of S and S' would be 2 and 1 respectively). In any case our assumption that S is a periodic sequence in A implies that S is not equal to S'. Thus, S is not self-reading, and the proof is complete.

The Kolakoski sequence first appeared as Problem 5304 proposed by William Kolakoski, American Mathematical Monthly 72 (1965) p. 674 and 73 (June 1966) pp. 681-682. Information about the problem, further comments, and many references can be found on N.J.A. Sloane's web page

http://www.research.att.com/~njas/sequences/ Alternatively, send an e-mail message to the address sequences@research.att.com; the entire message should be lookup 1 2 2 1 1 2 1 2 2

(Do not type anything in the subject line.)