Recursive Description

Consider the following sequence of numbers:

1 1 11 11 21 21 1211 1211 111221 111221 ... \text{...}

Each row "describes" the previous row.

For example, the first row has one 1 1 . The next row is one 1 11 \text{one } 1 \implies 11 .

The second row has two 1 s 1\text{s} . The next row is two 1 21 \text{two } 1 \implies 21 .

The third row has one 2 2 and one 1 1 . The next row is one 2 one 1 1211 \text{one } 2 \text{ one } 1 \implies 1211 .

The fourth row has one 1 1 , one 2 2 , and two 1 s 1\text{s} . The next row is one 1 one 2 two 1 111221 \text{one } 1 \text{ one } 2 \text{ two } 1 \implies 111221 .

Consider each unique digit in the 201 8 t h 2018^{th} row of this sequence. What is the sum of these digits?


The answer is 6.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Zain Majumder
Feb 1, 2018

The next number in the sequence is 312211 312211 . Every number following this one must contain a 1 1 , a 2 2 , and a 3 3 at least once to properly describe the previous row. However, I argue that no digit greater than 3 3 can appear in the sequence.

Assume that a digit greater than or equal to 4 4 is in the sequence. This implies that there was a number at some point with at least 4 4 repeating digits in a row. Let n n be the first such number. If this digit is X X , then n = . . . A X X X X B . . . n=\overline{...AXXXXB...} where A A and B B could or could not be X X . What could the previous number have been?

We can divide n n into a series of descriptions, with each description containing a quantity value followed by a digit value. Currently, there have never been 10 10 or more of a digit in a row, so a description will always have exactly 2 2 digits. Depending on the location of A X X X X B \overline{AXXXXB} in the number, the descriptions can be A X , X X , X B A{\color{#D61F06}X}, X{\color{#D61F06}X}, XB or X X , X X X{\color{#D61F06}X}, X{\color{#D61F06}X} . In both cases, the digit value X X appears twice in a row (in red). Both of these situations are impossible since the same digit value cannot appear in two consecutive descriptions (if this did happen, they should be merged into one description). This is a contradiction, so 4 4 digits in a row cannot appear in the sequence.

The 201 8 t h 2018^{th} row contains only 1 s 1\text{s} , 2 s 2\text{s} , and 3 s 3\text{s} , so the sum of the unique digits is 1 + 2 + 3 = 6 1+2+3=\boxed{6}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...