Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Question also asked at http://math.stackexchange.com/questions/497343/deletion-puzzle.

Consider all $2^n$ different binary vectors of length $n$ and assume $n$ is an integer multiple of $3$. You are allowed to delete exactly $n/3$ bits from each of the binary vectors, leaving vectors of length $2n/3$ remaining. The number of distinct vectors remaining depends on which bits you delete. Assuming your aim is to leave as few remaining different vectors as possible, how few can you leave as a function of $n$?

Example, $n=3$. You can leave only the two vectors $11$ and $00$.

Following comments at the math.se site (in particular by Jack D'Aurizio), in general for larger values of $n$ you can replace any block of three consecutive bits by either $00$ or $11$. This gives an upper bound of $2^{n/3}$. Is this in fact the correct answer?

Now I have some code to solve small instances, we can start to fill in a table of optimal results. We use the notation $H(n,b)$ to indicate the smallest number of distinct vectors that results from starting with all vectors of length $n$ and removing $b$ from each.

$$12 \leq H(15,5) \leq17$$

$$H(12,4) = 10$$

For $n=10$ and $b = 1,2,3,4$ we have $\leq140,\leq 31,10, 4$

For $n=9$ and $b = 1,2,3,4$ we have $70,18,6,2$

For $n=8$ and $b = 1,2,3$ we have $40,10,4$

For $n=7$ and $b = 1,2,3$ we have $20,6,2$

For $n=6$ and $b = 1,2$ we have $12,4$

For $n=5$ and $b = 1,2$ we have $6,2$

$$H(4,1) = 4, H(3,1) = 2, H(2,1) = 2$$

If we only allow symmetric solutions then $H(10,2)=32$. This implies (assumnig no error in the calculations) that for some instances there may be no symmetric optimal solutions as we already have $H(10,2) \leq 31$.

share|improve this question
1  
This is the first question I see whose answers look so much like a mini polymath project. –  Benoît Kloeckner Sep 26 '13 at 13:53
    
Why is your bound for H(10,1) 141 when the bound for H(9,1) is 70? Just by appending 0 or 1 to the end of the substrings for H(9,1) you can obtain a bound of 140. –  Thomas Sep 27 '13 at 8:01
    
@Thomas Thank you. Fixed. –  Anush Sep 27 '13 at 8:12
    
Can you list the 31 substrings for H(10,2)? Also, what symmetries are you thinking of? Just complementary symmetry? –  Thomas Sep 28 '13 at 2:11
    
Finding H(n,1) for large n is actually quite hard, so I will focus on proving some easier things. For example, it is easy to prove that H(2a+1,a)=2, because one of the digits has at most a occurences. –  Thomas Sep 28 '13 at 3:31
show 2 more comments

8 Answers

I can, at least, answer your question 'Is this in fact the correct answer?' with an affirmative 'no'.

Specifically, we can replace the upper bound $2^{n/3} \approxeq 1.26^n$ with the slightly better bound $6^{n/9} \approxeq 1.22^n$ by applying the same 'separate into independent blocks' construction to the following (conjecturally optimal) covering set for $n = 9$:

$$\{000000, 111111, 111000, 000111, 001100, 110011\}$$

Clearly, $2^{n/3}$ is still optimal for $n = 3$ and indeed (by exhaustive search) $n = 6$.

share|improve this answer
1  
Thank you for this. At this point any lower bound would be interesting. –  Anush Sep 22 '13 at 20:55
    
Indeed, I haven't been able to establish a non-constant lower bound. Any covering set must necessarily contain the words $00\dots 0$ and $11 \dots 1$, and except in the case of $n=3$ these are insufficient. I suspect that we can asymptotically beat $(1 + \epsilon)^n$ for any $\epsilon > 0$. –  Adam P. Goucher Sep 22 '13 at 21:01
1  
If we change the problem so that we delete $n/5$ bits instead of $n/3$ then we can get a simple exponential lower bound. We remove $n/5$ bits from each vector leaving $K$ distinct vectors. So we have $K\binom{n}{n/5}2^{n/5} \geq 2^n$. Therefore $K\geq \left(\frac{2^{1-1/5}}{(5e)^{1/5}}\right)^n > 1.033^n$. Maybe this approach can be improved to work for $n/3$ as well? –  Anush Sep 23 '13 at 16:20
    
I am trying to prove that the covering set is optimal for n=9. The way I am doing this is to first consider the forced strings 000000, and 111111. Then the first length 9 strings that don't work are 000001111 and 111110000. This forces two more strings (0^a)(1^(6-a)) and (0^b)1^(6-b) for some a and b at least 2 and at most 4 (because of 000011111 and 111100000). For each of the 6 cases (3 are removed by symmetry), I then check for two other strings which don't have those as a substring and are incompatible with each other. a=b=2 has 010000111 and 101111000, and I am onto the a=2, b=3 case now. –  Thomas Sep 25 '13 at 4:14
    
Woops, actually, there is another case: having the set 000000, 000001, 011111, (1^a)(0^(6-a)), 111111, for a=2, 3, or 4. Although, that case is covered by 101010101, so we're ok. –  Thomas Sep 25 '13 at 4:23
show 5 more comments

This is not an answer but rather a long comment. I give an informal argument that suggests what the right answer should be. The proof of the lower bound is rigorous, the proof of the upper bound is not.

Denote $k=n/3$. Let us say that a binary word $y\in\{0,1\}^{2k}$ covers a word $x\in \{0,1\}^n$ if $y$ can be obtained from $x$ by removing $k$ digits. Our goal is to find a set $S \subset \{0,1\}^{2k}$ of smallest possible cardinality that covers all words in $\{0,1\}^n$.

A lower bound on the size of $S$. We will show that every word $y$ covers approximately $2^{nH(1/3)}$ words in $\{0,1\}^n$. Therefore, the size of $|S|$ is at least $2^{n(1-H(1/3))}\approx 2^{0.08\, n}$. Here $H(t)$ is the entropy function $$H(t) = -t \log_2 t - (1-t) \log_2(1-t).$$

Let us fix $y$ and count the number of words $x$ that $y$ covers. To this end, we consider an algorithm that checks whether $y$ covers $x$. This is just a simple greedy algorithm that scans $x$ from left to right and finds indices $i_1 < \dots < i_{2k}$ s.t. $x_{i_r} = y_r$ for $r\in\{1,\dots, 2k\}$: $i_1$ is the first index s.t. $x_{i_1} = y_1$, $i_2$ is the first index after $i_1$ s.t. $x_{i_2} = y_2$ and so on. The algorithm terminates when it defines $i_{2r}$. The algorithm succeeds and finds $i_1< \dots < i_{2r} \leq n$ if and only if $y$ covers $x$.

Let $I_y(x) = \{i_1, \dots, i_{2k}\}$ for given words $x$ and $y$. Note that if $I_y(x') = I_y(x'')$ then the algorithm performs exactly the same steps. In particular, the first $i_{2r}$ digits in $x'$ and $x''$ are equal. Also for every set $I\subset \{1,\dots, n\}$ of size $2k$, there is a word $x$ s.t. $I_y(x) = I$.

Therefore, the number of words $x$ covered by $y$ is equal to sum over all possible values of $j\equiv i_{2r}$ the number of subsets of $\{1,\dots, j\}$ of size $2k$ times the number of possibilities for digits at positions $j+1,\dots, n$. $$\sum_{j=2k}^{n} \binom{j}{2k} 2^{n-j} \approx \sum_{j=2k}^{n} 2^{jH(2k/j)} 2^{n-j}\approx 2^n \sum_{j=2k}^n 2^{(\frac{j}{2k} (H(2k/j)-1))\cdot 2k} = 2^n \sum_{j=2k}^n 2^{f(2k/j)\cdot 2k}.$$ where $f(t) = (H(t)-1)/t$. The function $f(t)$ attains its maximum on $[2/3,1]$ when $t=2/3$. Thus the number of words covered by $y$ is approximately $$2^{n + 2 f(2/3)k} = 2^{nH(1/3)}.$$ We conclude that the set $S$ must contain at least $2^{n}/2^{H(1/3)n}\approx 2^{0.08\, n}$ words.

An upper bound on the optimal size of $S$. Note that this problem is a version of the set cover problem. Thus the size of the optimal set cover (optimal size of $S$) is within a log-factor of the size of the optimal fractional cover. (The log factor is $\log 2^{3n} = O(n)$). So it suffices to get an upper bound on the size of a fractional cover to get an approximate upper bound on the size the optimal set $S$.

Warning: This is not a proof! Some statements below are not correct!

Consider the bipartite graph with words $\{0,1\}^{2k}$ on the left, and words $\{0,1\}^{n}$ on the right, in which $y$ is connected to $x$ if $y$ covers $x$. The graph is “more or less bipartite”. To be precise, it is not regular but it is very close to a regular graph (this is an informal statement that needs justification!). We will pretend nevertheless that the graph is regular. The degree of each vertex on the left is approximately $2^{H(1/3)n}$ as we computed above. Thus we get a fractional cover when we take every string of length $2k$ with weight $2^n / (2^{2k} 2^{H(1/3)n})$. The total weight of all words in the fractional cover is $2^n / (2^{H(1/3)n}) \approx 2^{0.08\, n}$.

Answer: $\approx 2^{(1-H(1/3))n}\approx 2^{0.08n}$.

share|improve this answer
1  
Thank you. I wonder what, if any, the relation is between these ideas and those for deletion codes (see e.g. eecs.harvard.edu/~michaelm/TALKS/DelSurvey.pdf ). –  Anush Sep 23 '13 at 18:32
    
@Anush, I have not heard before about this paper, but it looks like it is related. –  Yury Sep 25 '13 at 0:09
add comment

If a vector has $d$ one-entries, and $d\leq n/2$, then delete as many ones as you can, (and further zeros if necessary). Conversely, if a vector has more one entries than zero entries, delete as many zeros as you can, (and further ones if necessary).

Any remaining vector of the first type will have $\max(d-n/3,0)\leq n/6$ ones. The number of such vectors with exactly $n/6$ ones in $2n/3$ positions is $\binom{2n/3}{n/6}$. For the final sum, one needs to sum over bimomial coefficients $2 \sum_{i=0}^{n/6} \binom{2n/3}{i}$ and such a sum can be approximated: Note that the largest entry, with $d=n/6$ gives by far the greatest contribution. The binomial coefficient in this region can be approximated by $\binom{k}{l}=2^{k H(l/k)+o(k)}$, where $H$ denotes the entropy function $H(x)=\frac{-x \log x-(1-x)\log (1-x) }{\log 2}$, (for $x\in [0,1]$, and $\log $ is the natural logarithm).

Edit: In view of Yuri's comment, I correct this: (Thank you, Yuri!)

As $H(1/4)$ is about $0.811$, this is about $2^{2n/3 \times 0.811...+o(1)}=2^{0.54\ldots n}$.

This upper bound is certainly weaker than the bound $2^{n/3}$, but uses a quite different method. It would be interesting to see, whether the "optimum" uses a deterministic construction, or a random construction (like Shannon's bounds in coding theory), or a combination of methods.

Some explanation why the method above gives some saving over the trivial $2^{2n/3}$: most of the original vectors have about $n/2+ O(\sqrt{n})$ zero and one entries. Going away from this symmetric centre reduces (by the binomial distribution) the number of possibilities. In other words the tail of this distibution is small.

share|improve this answer
2  
Shouldn't it be $\binom{2n/3}{n/6}\approx 2^{kH(1/4)} \approx 2^{(2n/3) \cdot 0.811} \approx 2^{0.54n} \gg 2^{n/3}$ ? –  Yury Sep 22 '13 at 16:30
add comment

Here is an exponential lower bound. We begin by determining exactly how many strings $Y$ of length $n$ can be reduced to a given string $X=x_1x_2\cdots x_k$. In general $y$ might contain many copies of $X$, but it contains exactly one left-most copy of $X$; that is, the first $x_1$ then the first $x_2$ and so on. The strings with $X$ as a left-most substring form a regular language of simple form. For example, if $X=101$ then the language is $0^*1 \cdot 1^*0 \cdot 0^*1 \cdot (0+1)^*$. The generating function for $0^*1$ and $1^*0$ is $z/(1-z)$ while the generating function for $(0+1)^*$ is $1/(1-2z)$.

Therefore, the number of $Y$s that contain $X$ is independent of the structure of $X$ and is the coefficient of $z^n$ in $z^k (1-z)^{-k} (1-2z)^{-1}$, namely $$N(n,k) = \sum_{i=0}^{n-k} 2^i\binom{n-i-1}{k-1},$$ which I think doesn't have a closed form.

Therefore, a lower bound for the question is $2^n/N(n,k)$.

For $k=2n/3$, the largest term in the sum is the first one, and the following terms are close to a geometric progression with ratio $2/3$. This gives $$ N(n,2n/3) = (2 + O(1/n)) \binom{n}{2n/3},$$ giving a lower bound of $$ (1+o(1)) \frac{\sqrt{\pi n}}{3} \left(\frac{2^{5/3}}{3}\right)^n. $$ Note that $2^{5/3}/3\approx 1.05826737$.

I think it is most unlikely that this is best possible.

share|improve this answer
1  
I think your answer is essentially the same as Yury's nice answer from yesterday. Note that his $2^{0.08}$ is approximately your $1.058$. Yury suggested plausibly that this might be the right answer. –  Lucia Sep 24 '13 at 13:50
1  
An issue for this being the correct value is how disjoint the "radius $k$" sets can be. For example in the case $n=9$ the string $111000111$ can be reduced to $111111$ and to $111000$ and to $110011$, half the members of the six element covering set. –  Aaron Meyerowitz Sep 24 '13 at 21:11
add comment

For $n=12$ it is possible to use $10$ strings of length $2k=8.$

There is, for $n=3k$, a smallest size $s(n)$ for a set $S$ of strings in $ \{0,1\}^{2k}$ which covers all the strings in $\{0,1\}^n$.

We have $s(n_1)s(n_2)\ge s(n_1+n_2)$ so, by Fekete's Lemma there is a constant $\alpha=\inf {s(n)^{1/n}}$ such that $\lim {s(n)^{1/n}}=\alpha.$

We so far have from the various answers that $$1.05827 \lt \alpha \lt 6^{1/9}\approx 1.2203.$$

I show below that $s(12) \le 10$ which improves the upper bound to $10^{1/12}\approx 1.2115.$

To improve on this upper bound we would need $s(15) \le 17$ (I'd bet on $16$, if anything, just because it seems nicer.) Taking into account that we must have $0^{10},1^{10}$ (in an obvious notation) and adding the optimistic condition that the set of strings is closed under complements and reversing the order, it might be possible to investigate this by somewhat intelligent brute force. An even more optimistic condition would be that each string of length $2k=10$ is either unchanged or replaced by its complement when reversed. Finally one could add the restriction that each of the non-constant words has five $0$'s and five $1$'s. I can think of some obvious further strings to include but that still leaves much to do.

A larger lower bound might (or might not) arise from considering how much overlap there has to be for various "radius $k$" balls. For example each of the six members from the set for $s(9)=6$ covers $130$ of the $512$ strings in $\{0,1\}^{9}$ so on average each string is covered a little over $1.5$ times. Some just once and others, such as $111000111$ as many as three times.

In general one might reasonably hope to have a covering set where every non-constant string has $k$ $0$'s and hence $k$ $1$'s. This has the advantage that one knows for any particular word how many $1$'s and $0$'s must be deleted.

For $n=12$ the eight strings below ( Walsh sequences ) are (nearly) enough $$00000000,00001111,00110011,00111100$$$$11111111,11110000,11001100,11000011.$$ They are enough with the addition of the two strings $$11101000,00010111$$ Here is a sketch where we avoid using the final two strings as long as possible:

Thanks to the two constant strings we need only consider length $12$ strings with $5,6$ or $7$ $1$'s. By symmetry and complements we can restrict to either $6$ or $7$ $1$'s with at least as many among the first $6$ locations as the last $6$. Observe that any length $6$ string with $3$ $1$'s can be reduced to $0011$ or $1100$ with two deletions.

Consider first the case of $6$ $1$'s. If $3$ are in the left half (and $3$ on the right) then the previous observation shows that we can get one of the four strings which are not constant on either half. If $5$ or $6$ are on the left then we can get $11110000$.

It remains to consider the case of $7$ $1$'s and $5$ $0$'s with at least $4$ of the $1$'s on the left side. We must delete a single $0$ and three $1$'s. Again, if there are $5$ or $6$ $1$'s on the left side then we can get $11110000$. All that is left is the subcase with $4$ $1$'s on the left. If the left side is $abcde0$ then we can delete the single $0$ among $abcde$ and continue to get $11110000.$ If the left side is $abcd11$ then we can delete the two $1$'s among $abcd$ to get $0011$. So now we have the subsubcase that the left side is $abcd01$ and the right side has $3$ $0$'s and $3$ $1$'s. The four possibilities on the left include $111001$,$110101$ (both of these can be reduced to $1100$ with two deletions). Finally we get the case that the left side is $101101$ or $011101$ and there are three $1$'s on the right side. In some cases we are still covered but $101101\ 010101$ (for example) seems hopeless. However for all $30$ of the length 12 strings left uncovered we can delete the first $0$ from the left half and all three $1$'s from the right to get $1110101000.$

share|improve this answer
1  
A better choice for the "extra" two vectors for $n=12$ is $10010110,01101001$. Then one has the four vectors constant on each half and six more vectors each equal or complementary to its reverse (as before) AND with equally many $0$'s and $1$'s in each half. –  Aaron Meyerowitz Sep 25 '13 at 4:45
    
And it is the unique minimal cover with all these properties. –  Aaron Meyerowitz Sep 25 '13 at 4:57
    
I have checked a few relatively simple cases, and it seems that using 00011111 and 11100000 would be better than 00001111 and 11110000. I know that it lacks the symmetry of the original solution, but we should try it anyway. –  Thomas Sep 25 '13 at 8:45
1  
I have now proved by computer search that $10$ is optimal for $n=12$. Unfortunately it does not seem feasible to scale this up to $n=15$ without some more work. –  Anush Sep 26 '13 at 8:47
1  
I managed to get a $17$ solution for $(15,5)$. They are 0000001111,0000111111,0001101100,0011100011,0011111000,0100111010,0110001‌001,01‌​11001110,1000010000,1001100111,1100011100,1101000110,1110000011,1111‌100000,11111‌​11000 plus the all 0s and all 1s. –  Anush Oct 2 '13 at 17:13
show 18 more comments

I think it may be helpful and/or intersting to consider the problem for fractions other than $1/3$.

Specifically, if $n$ is a multiple of $q$, let $f(p/q,n)$ be the minimal size of a set of $n- (p/q)n$ bit strings such that deleting $(p/q)n$ bits from each $n$-bit string produces an element of the set. Then set

$$g(p/q) = \lim _{n\to \infty} \frac{\log f\left(\frac{p}{q},n\right)}{n}$$

The limit exists because, by the divide-into-independent-blocks argument, any particular value is a bound for the $\lim\sup$.

It is clear that $g$ is monotonic. It's not immediately obvious to me if we can prove that $g$ is continuous.

Clearly $g(x)=0$ for $x \geq 1/2$.

For a simple upper bound on $g$ for $x<1/2$, we can assume with the loss only of a constant that there are fewer $0$s than $1$s. Then divide the $n$ bits into $q$ equally sized parts, and delete all the $0$s in the $2p$ parts with the fewest ones. This takes $2^{ (1-2p/q)n }$, giving an upper bound $g(x) \leq (1-2x) \log 2$.

Thanks to Brendan McKay and Yury, we have a lower bound on $g$. If I understand this bound correctly, it is that $g(x) \geq \log 2 + x \log x + (1-x) \log(1-x)$. (We can easily check that the maximal term in the $x=1/3$ case remains maximal for all $0<x<1/2$.)

Specific examples, like, Adam Goucher's, can give us tighter upper bounds for specific values of $x$.

share|improve this answer
    
I think this is a good idea. But why not just consider $H(n,k)$ which is the number of strings needed if we are allowed to delete $k$ elements from an $n$ element string. As you note the methods of Yury and McKay giive lower bounds for $H(n,k)$. Note that $H(n,k) \le H(a,\ell)H(n-a,k-\ell)$ and so Goucher's example gives non-trivial upper bounds. –  Lucia Sep 25 '13 at 20:09
    
The reason I did that is that I want to consider asymptotics as $n$ goes to $\infty$. The most obvious way to do this was to fix $n/k$. But there might be other interesting things to do! Yes, this bound on $H(n,k)$ gives an upper bound on $g$, forcing it to be convex. So currently our curve bounding $g$ is the convex hull of just $3$ points. A search could presumably find more. –  Will Sawin Sep 25 '13 at 20:47
    
Your $g(x)$ is my $(\log H(n,nx))/n$ as $n$ goes to infinity. The upper bound on $H(n,k)$ noted above I think gives that $g$ is convex, and therefore continuous. –  Lucia Sep 25 '13 at 20:48
    
Our last comments crossed, but at least they are in agreement. Note that the lower bound for $g$ is also convex, so that it is at least plausibly the right answer. –  Lucia Sep 25 '13 at 21:04
    
I have calculated a few values of H(n,j), and I discovered that H(2a+1,a)=2, and H(2a+2,a)=4. I am trying to figure out H(2a+3,a) now. –  Thomas Sep 26 '13 at 10:01
show 1 more comment

This answer is an elaboration on the idea of Christian Elsholtz. Like that answer, this answer does not beat $2^{n/3}$.

As noted by Christian, by symmetry it suffices to deal with vectors that contain at most $n/2$ ones. By left-right symmetry, it suffices to deal with vectors of at most $n/4$ ones among the first $n/2$ positions. Remove the first $n/3$ ones. That leaves a vector of length $2n/3$ with at most $n/6$ ones that starts with a string of $n/4$ zeros. There are approximately $\binom{2n/3-n/4}{n/6}\approx 2^{5n/12\times H(2/5)}=2^{0.40455n}$, which is still worse than $2^{n/3}$.

One can improve this a bit. Namely, after deleting all the ones from the first half of string, we choose whether to remove ones from third or four quarter. It appears that in the worse case (non-rigorously!) we end up with a string of length $2n/3$ that contains $n/6$ ones among which $n/24$ are in the third quarter and $n/8$ are in the fourth quarter. There are approximately $\binom{n/6}{n/24}\binom{n/4}{n/8}\approx 2^{0.385n}$ of them.

share|improve this answer
1  
You can do better. Split ones into three parts and delete two of them. In one of three ways you obtain two rows of zeroes at the left and at the right with the sum of lengths at least $n/3$. Thus you get at most ${n/3\choose n/6}\cdot O(n)=2^{n/3+o(1)}$. –  Ilya Bogdanov Sep 23 '13 at 12:48
add comment

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.

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_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:

$$ 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.

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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