Return to Answer

Case A:   Let $\ b_0b_1b_2b_3\ $ have (at least) three same bits, say $\ x$.   Then $\ b_4\ldots b_8\ $ bits contain (at least) three bits say $\ y$,   where values $\ x\ y\ $ are different or the same. In either case by leaving the two groups of three bits we get one of the four strings of length 6:

Case A:   Let $\ b_0b_1b_2b_3\ $ have (at least) three same bits, say $\ x$.   Then $\ b_4b_5b_6b_7b_8\ $ bits contain (at least) three bits say $\ y$ (the majority of five),   where values $\ x\ y\ $ are different or the same. In either case by leaving the two groups of three bits we get one of the four strings of length 6:

Let's refer to the six Goucher's sequences as of the type $\ 6\ \ 3\!+\!3\ \ 2\!+\!2\!+\!2$,   where each type addresses the consecutive two sequences by Goucher.

I'll provide a simpler derivation below, and will leave the previous one at the bottom.

Let $\ b_0\ldots b_8\ $ be a bit string.

Case A:   Let $\ b_0b_1b_2b_3\ $ have (at least) three same bits, say $\ x$.   Then $\ b_4\ldots b_8\ $ bits contain (at least) three bits say $\ y$,   where values $\ x\ y\ $ are different or the same. In either case by leaving the two groups of three bits we get one of the four strings of length 6:

$$ 000000\quad 000111\quad 111000\quad 111111$$

Case A':   Consider $\ b_5b_6b_7b_8\ $ -- everything is symmetric.

From now on let's assume that the distribution of bits in $\ b_0b_1b_2b_3\ $ is two bits of each, and the same for $\ b_5b_6b_7b_8$.

Case B:   $b_3=b_5$,   and say $\ b_3=b_5=x$.   Then remove one of bits of value $\ 1-x\ $ from $\ b_0b_1b_2\ $ and from $\ b_6b_7b_8\ $ and remove also bit $\ b_4$.   We are left with one of the strings:

$$ 001100\qquad 110011$$

Case C:   $b_3=b_4\ne b_5$,   and say $\ b_3=x$.   Then remove the one bit of value $\ x\ $ from $\ b_0b_1b_2$,   and the two more bits $\ x\ $ from $\ b_6b_7b_8$.   We are left with one of the two 6-strings as the above.

Case C':   $b_3\ne b_4= b_5$ -- symmetry.

END of PROOF

(Back to the old argument)

Let's refer to the six Goucher's sequences as of the type $\ 6\ \ 3\!+\!3\ \ 2\!+\!2\!+\!2$,   where each type addresses the consecutive two sequences by Goucher.

For each $\ n=9\cdot m + 3\cdot k\ $ one gets a bound of $\ 6^m\cdot 2^k\ $ for every $\ m=0\ 1\ \ldots\ $ and $\ k\in\{0\ 1\ 2\}$.

A hand justification below of the result by @Adam P. Goucher (and a computer) indicates a further possible progress along a similar line. I'll explicitly associate binary sequences of length $\ 9\ $ with the respective Goucher's sequences.

Let's refer to the six Goucher's sequences as of the type $\ 6\ \ 3\!+\!3\ \ 2\!+\!2\!+\!2$,   where each type addresses the consecutive two sequences by Goucher.

Case 1: one of the bit values of a binary sequence $\ b_0\ldots b_8\ $ occurs at least $\ 6\ $ times. Then we may leave a six of them to produce a 6-sequence of type $\ 6$.   Now we may restrict ourselves to the cases when each bit value of a 9-sequence $\ b_0\ldots b_8\ $ occurs $\ 4\ $ or $\ 5\ $ times.

Let the bit value $\ x\ $ be the value of the majority of $\ b_6b_7b_8$,   and $\ y\ $ be the value of the majority of $\ b_0b_1b_2$. (Values $ x\ y\ $ can be equal or different).

Case 2:   $b_6=b_7=b_8=x\ $ or $\ b_0=b_1=b_2=y$. It's enough to consider just the earlier option, about $\ x$.   Then there are three bits among $\ b_0\ldots b_5\ $ which have the same value.   These three bits together with $\ b_6b_7b_8\ $ form a 6-sequence of type $\ 6\ $ or $\ 3+3$. The latter option, about $\ y$,   is proved similarly.

Now we may assume that exactly two bits of $\ b_6b_7b_8\ $ have value $\ x$,   and exactly two of $\ b_0b_1b_2\ $ have value $\ y$.

Case 3:   $x=y$.   Then if at least $\ 2\ $ of the bits of $\ b_3b_4b_5\ $ have value $\ x\ $ then we leave these two $x$-bits together with two of the $x$-bits of $\ b_0b_1b_2\ $ and another two $x$-bits of $\ b_6b_7b_8\ $ to produce a 6-sequence of type $\ 6$.   Otherwise two bits of $\ b_3b_4b_5\ $ are different from $\ x=y$.   Then two (middle) non-x bits together with the 2+2 bits from $\ b_0b_1b_2\ $ and $\ b_6b_7b_8\ $ form a 6-sequence of type $\ 2+2+2$.

Case 4:   $x\ne y$.   The three bits $\ b_3b_4b_5\ $ cannot have the same value or else there would be $\ 6\ $ bits of the same value in the whole 9-sequence. Next, if there are integers $\ r\ s\ $ such that $\ 3\le r<s\le 5\ $ and $\ b_r=y\ $ and $\ b_s=x\ $ then we would get a 6-sequence of type $\ 3+3$.   Otherwise $\ b_3=x\ $ and $\ b_5=y$. Let's assume that $\ b_4=x\ $ (the case $\ b_4=y\ $ is symmetric). The the two of $y$-bits of $\ b_0b_1b_2\ $ together with $\ b_3b_4b_5\ $ and the single $y$-bit of $\ b_6b_7b_8\ $ form a 6-sequence of type $\ 2+2+2$.

END of PROOF

For each $\ n=9\cdot m + 3\cdot k\ $ one gets a bound of $\ 6^m\cdot 2^k\ =\ 6^{\frac n9}\cdot 2^k\ $ for every $\ m=0\ 1\ \ldots\ $ and $\ k\in\{0\ 1\ 2\}$.

A hand justification below of the result by @Adam P. Goucher (and a computer) indicates a further possible progress along a similar line. I'll explicitly associate binary sequences of length $\ 9\ $ with the respective Goucher's sequences.

Let's refer to the six Goucher's sequences as of the type $\ 6\ \ 3\!+\!3\ \ 2\!+\!2\!+\!2$,   where each type addresses the consecutive two sequences by Goucher.

Case 1: one of the bit values of a binary sequence $\ b_0\ldots b_8\ $ occurs at least $\ 6\ $ times. Then we may leave a six of them to produce a 6-sequence of type $\ 6$.   Now we may restrict ourselves to the cases when each bit value of a 9-sequence $\ b_0\ldots b_8\ $ occurs $\ 4\ $ or $\ 5\ $ times.

Let the bit value $\ x\ $ be the value of the majority of $\ b_6b_7b_8$,   and $\ y\ $ be the value of the majority of $\ b_0b_1b_2$. (Values $ x\ y\ $ can be equal or different).

Case 2:   $b_6=b_7=b_8=x\ $ or $\ b_0=b_1=b_2=y$. It's enough to consider just the earlier option, about $\ x$.   Then there are three bits among $\ b_0\ldots b_5\ $ which have the same value.   These three bits together with $\ b_6b_7b_8\ $ form a 6-sequence of type $\ 6\ $ or $\ 3+3$. The latter option, about $\ y$,   is proved similarly.

Now we may assume that exactly two bits of $\ b_6b_7b_8\ $ have value $\ x$,   and exactly two of $\ b_0b_1b_2\ $ have value $\ y$.

Case 3:   $x=y$.   Then if at least $\ 2\ $ of the bits of $\ b_3b_4b_5\ $ have value $\ x\ $ then we leave these two $x$-bits together with two of the $x$-bits of $\ b_0b_1b_2\ $ and another two $x$-bits of $\ b_6b_7b_8\ $ to produce a 6-sequence of type $\ 6$.   Otherwise two bits of $\ b_3b_4b_5\ $ are different from $\ x=y$.   Then two (middle) non-x bits together with the 2+2 bits from $\ b_0b_1b_2\ $ and $\ b_6b_7b_8\ $ form a 6-sequence of type $\ 2+2+2$.

Case 4:   $x\ne y$.   The three bits $\ b_3b_4b_5\ $ cannot have the same value or else there would be $\ 6\ $ bits of the same value in the whole 9-sequence. Next, if there are integers $\ r\ s\ $ such that $\ 3\le r<s\le 5\ $ and $\ b_r=y\ $ and $\ b_s=x\ $ then we would get a 6-sequence of type $\ 3+3$.   Otherwise $\ b_3=x\ $ and $\ b_5=y$. Let's assume that $\ b_4=x\ $ (the case $\ b_4=y\ $ is symmetric). The the two of $y$-bits of $\ b_0b_1b_2\ $ together with $\ b_3b_4b_5\ $ and the single $y$-bit of $\ b_6b_7b_8\ $ form a 6-sequence of type $\ 2+2+2$.

END of PROOF