John writes a number with 2187 digits on the blackboard, each digit being a 1 or a 2. Judith creates a new number from John's number by reading his number from left to right and wherever she sees a 1 writing 112 and wherever she sees a 2 writing 111. (For example, if John's number begins 2112, then Judith's number would begin 111112112111.) After Judith finishes writing her number, she notices that the leftmost 2187 digits in her number and in John's number are the same. How many times do five 1's occur consecutively in John's number?
(A) 182
(B) 183
(C) 184
(D) 185
(E) 186
We will refer to the digits of each of John's and Judith's numbers from the left. Thus, "the first digit" will be the leftmost digit.

If the first digit of John's number is 1, then Judith's number will begin 112.

If the first digit of John's number is 2, then Judith's number will begin 111. In either case, Judith's number begins with a 1.

Since the first 2187 digits are the same, then John's number begins with a 1.

Since John's number begins with a 1, then Judith's begins 112, so John's begins 112.

Since John's number begins 112, then Judith's begins 112112111, so John's begins 112112111. Each time we repeat this process, the length of the string which we know will be multiplied by 3 .

We continue this process to construct the $2187=3^{7}$ digits of John's number.

We make a table to keep track of this information. We notice that if at one step, the string ends in a 1, then at the next step it will end in a 2, since the 1 becomes 112. Similarly, if at one step, the string ends in a 2, then at the next step, it ends in a 1 , since the 2 becomes 111 . Also, since each 1 becomes 112 and each 2 becomes 111, then the number of 2's at a given step will be equal to the number of 1's at the previous step. Similarly, the number of 1's at a given step equals 2 times the number of 1's at the previous step plus 3 times the number of 2's at the previous step. (Alternatively, we could determine the total number of 1's by subtracting the number of 2's from the length of the string.)

| Step \# | Length | \# of 1's | \# of 2's | Ends in |
| :---: | :---: | :---: | :---: | :---: |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 3 | 2 | 1 | 2 |
| 2 | 9 | 7 | 2 | 1 |
| 3 | 27 | 20 | 7 | 2 |
| 4 | 81 | 61 | 20 | 1 |
| 5 | 243 | 182 | 61 | 2 |
| 6 | 729 | 547 | 182 | 1 |
| 7 | 2187 | 1640 | 547 | 2 |

How can five consecutive 1's (that is, 11111) be produced in this step 7?

There can never be two consecutive 2's at a given step, since every 2 is the end of one of the blocks and so must be followed by a 1 .

Thus, there can never be two consecutive 2's which would produce 111111.

This tells us that 11111 can only be produced by 21 at the previous step.

So the number of occurrences of 11111 at step 7 is equal to the number of occurrences of 21 at step 6 . But every 2 at step 6 is followed by a 1 (since the string at step 6 does not end with a 2 ), so this is equal to the number of 2's at step 6 .

Therefore, there are 182 occurrences of 11111 in the 2187 digits of John's number.