2
$\begingroup$

You may now the following sequence:

1
11
21
1211
111221
312211
13112221

Explanation of the sequence (I've put an hint just for the ones who want to search a bit ;) )

Where, in each iteration you count the number of occurrence of a digit then put the count and the digit in the new child. (First you've 1, then you've got one 1 (11), then you've got two 1(21)...)

I've the feeling that the numbers of the sequence will never contains a digit >3 but my mathematics knowledge are way to poor to prove it. So I've made a little program that compute the terms for me to found out if there is a number greater than 3 but up to the 42th term it doesn't find any.

As the length of the string is growing very fast, I can't compute a lot more terms and, even if I was able to do so, this would not be a proof.

So here's the question: How can I prove my feeling?

$\endgroup$
2
5
$\begingroup$

Consider the problem systematically: Starting with $1$, the sequence cannot contain the number $2$ until there are $2$ adjacent $1$s. Similarly, the sequence cannot contain $3$ until there are either $3$ adjacent $1$s or $3$ adjacent $2$s. Since the former will occur first, this occurs when there are $3$ adjacent $1$s.

Continuing this trend, it is not possible for the sequence to contain a $4$ until there are $4$ adjacent $1$s, $2$s, or $3$s.

In order to show that the number $4$ will not appear, you must show that there must not be $4$ adjacent $1$s, $2$s, or $3$s.

Assume that $\cdots 1111 \cdots$ occurs somewhere in the sequence, where the numbers preceding and succeeding this subsequence are not $1$. Thus, we have $\cdots a1111b \cdots$, $a,b \ne 1$.

There are two possible interpretations of the subsequence, depending on whether the index of $a$ is even or odd.

If even, the interpretation is that there were $a$ $1$s followed by $1\,$ $1$ followed by $1$ $b$ in the preceding sequence. However, if there were $a$ $1$s followed by $1\,$ $1$, we would simply write $(a+1)1$ in the sequence. Therefore, the subsequence $1111$ could not exist here.

If odd, the interpretation is that there was $1\,$ $1$ followed by $1\,$ $1$ in the preceding sequence; hence: $11$. However, this would be translated into the current sequence as $21$ rather than as $1111$. The subsequence $1111$ could not exist in this case either.

Similar logic will show that $2222$ and $3333$ cannot exist anywhere in the sequence. Therefore, as a result, the sequence cannot contain $4$ anywhere.

$\endgroup$
1
$\begingroup$

This is a typical proof by induction. The base case is just that the first term ($1$) does not contain any digit greater than $3$ nor more than $3$ consecutive, equal digits.

If some term had a digit greater than $3$, it would have had to come from more than $3$ (that is, $4$ or more) consecutive, equal digits in the previous term. But the first four of such digits (say that the digit is $k$) would had have to come from $k$ consecutive $k$s followed by $k$ consecutive $k$s, which makes no sense, because we would have written $2k$ and after $k$.

Example: if a term contains $41$ then the previous term contains $1111$ and then, the previous one contains "one $1$ and one $1$", that is, $11$, which should be transformed to $21$ and not to $1111$.

$\endgroup$
2
  • 1
    $\begingroup$ It should be noted that $k$ consecutive $k$s followed by $k$ consecutive $k$s is not the only interpretation of $kkkk$, depending on the parity of the index of the first $k$. For example, $akkkkb$ could mean $a$ consecutive $k$s followed by $k$ consecutive $k$s followed by $k$ consecutive $b$s. $\endgroup$
    – user134593
    Aug 25 '15 at 13:02
  • $\begingroup$ @stonebrakermatt Put differntly: By definition of the look-and-say process, the $2i$th and the $(2i+2)$th digit are different at any fixed stage. Any block of four or more consecutive digits covers two positions of even index, hence different digits. $\endgroup$ Aug 25 '15 at 13:08
0
$\begingroup$

Prove it by contradiction. Suppose thre is some step at which a number larger than $3$ appears. Let step $i$ be the one such step. Obviously, $i\neq 1$ since the first step has only 1.

Then, in step $i$, you have the subsequence Ak in your sequence for some A>3, meaning that step $i-1$ had a subsequence

xkkkky

for some values x,y. Now, you have two options:

  1. The step xkkkky is read as "x repetitions of k, then k repetitions of k, then k repetitions of y". This is not possible, as instead of x repetitions of k, then k repetitions of k, you would simply write x+k repetitions of k"

  2. The step reads as k repetitions of k, then another k repetitions of k, which is again impossible.

$\endgroup$
0
$\begingroup$

Each number contains pairs of type $xy$ where x is the number of corresponding consecutive y digit in the previous number. Consider the first number in sequence containing digit 4. Then the previous number must have 4 equal consecutive digits, let's say $dddd$.Now, $dddd$ cannot represents two pair of d repetition of d, therefore we must have something like k repetitions of d and d repetitions of d which also is not possible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.