Could you please tell me if this is the right approach to tackle this problem.I translated it from Spanish into English, so please excuse the wording and let me know if there's something that is not clear.

Problem statement

Let $S$ be the set of all sequences $s=(x_1,x_2,...,x_8)$ that are composed of four zeros and four ones. There is a match between two sequences when both have zero or one in the same position. For instance, there are three matches in $(1,0,0,1,0,1,1,0)$ and $(0,0,1,1,1,0,1,1)$, in the following positions: two, four and seven.

And also, for each sequence $s$ we consider the following seven sequences: $$s_i=(x_i,x_{i+1},...,x_8,x_1,x_2,x_3,...,x_{i-1}),i=2,...,8$$

Prove that there are at least four matches between any sequence $s$ and some of the sequences $s_i$.

My approach

First of all, I build a table to figure out how $s$ and all the $si$ are related:

$$\begin{array}{ccc} s=x_1x_2x_3x_4x_5x_6x_7x_8\\ s_2=x_2x_3x_4x_5x_6x_7x_8x_1\\ s_3=x_3x_4x_5x_6x_7x_8x_1x_2\\ s_4=x_4x_5x_6x_7x_8x_1x_2x_3\\ s_5=x_5x_6x_7x_8x_1x_2x_3x_4\\ s_6=x_6x_7x_8x_1x_2x_3x_4x_5\\ s_7=x_7x_8x_1x_2x_3x_4x_5x_6\\ s_8=x_8x_1x_2x_3x_4x_5x_6x_7\\ \end{array}$$

We observe that $x_i$ from $s$ is left-shift seven times in the $s_2,...,s_8$ sequences. This means that $x_i$ will not have a match with itself in any of the $s_i$. However, as $s$ is composed of four zeros and four ones, $x_i$, there are at least three matches of $x_i$ with $s_2,...,s_8$. That is, if $x_i=1$ there are other three ones, and similarly when $x_i=0$.

For each $x_i$ there are three matches in $s_2,...,s_8$. As the length of $s$ is eight, there are $8·3=24$ matches in total. As there are seven $s_2,...,s_8$, we use the pigeonhole principle to prove that $\lceil{24 \over 7}\rceil=4$. Therefore there is at least one $si$ that contains four or more matches with $s$.

  • $\begingroup$ You have posed your question in a format most appropriate for the site! +1 $\endgroup$ – user21436 Feb 8 '12 at 19:24

Yes, your proof looks correct.

We can view your table as a $7x8$ matrix with $s_i$ corresponding to row i.

An entry of row i will be a * if there is a match between $s_i$ and $s$ in the corresponding position (and blank otherwise).

You are essentially double counting the number of '*'. If you count via the columns, you get $24$ as you have shown. Since this is the same as when you count by rows, and there are only $7$ rows, at least one of the row counts must be $\ge 4$.

Well done.

  • $\begingroup$ Great! This is actually a problem I had to do in my discrete math exam last week. As I couldn't wait until we get the final grading I decided to post my approach here. $\endgroup$ – Javi Feb 8 '12 at 19:48

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.