290 views

Fix $n\geq 6$. Consider the set $\mathcal{C}$ of binary strings $x_{1}, x_{2} \dots x_{n}$ of length $n$ such that the bits satisfy the following set of equalities, all modulo $2$: $x_{i}+x_{i+1}+x_{i+2}=0$ for all $1\leq i\leq n-2, x_{n-1}+x_{n}+x_{1}=0,$ and $x_{n}+x_{1}+x_{2}=0.$ What is the size of the set $\mathcal{C}$?

1. $1$ for all $n\geq 6$
2. $4$ for all $n\geq 6$
3. $0$ for all $n\geq 6$
4.  If $n\geq 6$ is divisible by $3 \left | \mathcal{C} \right |=1$. If $n\geq 6$ is $\textit{not}$ divisible by $3$ then $\left | \mathcal{C} \right |=4$.
5. If $n\geq 6$ is divisible by $3$ $\left | \mathcal{C} \right |=4$. If $n\geq 6$ is not divisible by $3$ then $\left | \mathcal{C} \right |=1$.

$\textbf{Answer : E}$

$x_1 + x_2 + x_3 = 0$

$x_2 + x_3 + x_4 = 0$

$x_3 + x_4 + x_5 = 0$

$x_4 + x_5 + x_6 = 0$

$…...$

$x_{n-3} + x_{n-2} + x_{n-1} = 0$

$x_{n-2} + x_{n-1} + x_{n} = 0$

$x_{n-1} + x_{n} + x_{1} = 0$

$x_{n} + x_{1} + x_{2} = 0$

There are $n$ equations.

From $(1)$ and $(2),$ $x_1 = x_4$

From $(2)$ and $(3),$ $x_2 = x_5$

From $(3)$ and $(4),$ $x_3 = x_6$

From $(4)$ and $(5),$ $x_4 = x_7$

$...$

From $(n-3)$ and $(n-2),$ $x_{n-3} = x_n$

From $(n-2)$ and $(n-1),$ $x_{n-2} = x_1$

From $(n-1)$ and $(n),$ $x_{n-1} = x_2$

So,

$x_1= x_4 = x_7 = x_{10}= ….. = x_{3k+1}$

$x_2= x_5 = x_8 = x_{11}= ….. = x_{3k+2}$

$x_3= x_6 = x_9 = x_{12}= ….. = x_{3k}$ $( k \in \mathcal{I})$

So, for $n$ length string, we need only $3$ values $x_1,x_2,x_3$.

Now, if $n$ is divisible by $3$ then possible values of $x_1,x_2,x_3$

$(x_1,x_2,x_3) = (0,0,0),(1,1,0),(1,0,1),(0,1,1)$ ($\because$ we have to make mod-2 sum of $x_1,x_2,x_3$ as zero, so assign any $2$ of $x_{i}’s$ as $1$ or all should be zero)

Each tuple gets repeated for $n$ length string and it satisfies the mod-2 sum for consecutive $3$ bits in cyclic manner because if $n= 3k, k \in \mathcal{I},$ if strings start with $“110”$ then it ends with $“110”,$ so $(x_{n-1}+x_n + x_1) \mod 2 =0$ and $(x_{n}+x_1 + x_2) \mod 2 =0$ and since, $x_i = x_{i+3}$, so out of $3$ consecutive bits, one must be zero becauase $(x_{i+1} + x_{i+2} + x_{i+3}) \mod 2 = (x_{i+1} + x_{i+2} + x_{i}) \mod 2 = 0$ .Simiarly for strings start with  $“101”$ and $011.$

So, $|\mathcal{C}| = 4$

For example:

Consider $6-$ length string as: $(x_1,x_2,x_3,x_4,x_5,x_6)$

Now, possible strings (according to given conditions) are :

$(110110)$

$(101101)$

$(011011)$

$(000000)$

But if  $n$ is divisible by $3$ then then possible values of $x_1,x_2,x_3$

$(x_1,x_2,x_3) = (0,0,0)$ because then for any other possible tuple values as $(1,1,0),(1,0,1),(0,1,1)$, we can’t get the mod-2 sum as zero for example, consider $7-$ length string as $(x_1,x_2,x_3,x_4,x_5,x_6,x_7)$

$(1101101)$ ($(x_7+x_1+x_2) \mod 2 \neq 0$)

$(1011011)$ ($(x_6+x_7+x_1) \mod 2 \neq 0$)

$(0110110)$ ($(x_7+x_1+x_2) \mod 2 \neq 0$)

So, in this case, $|\mathcal{C}| = 1$

[$\because$ in this case, if $n = 3k+1$, $k \in \mathcal{I}$ then for those strings which start with $“11”,$ $x_n=1,x_{n-1}=0$ i.e. these strings ends with $01$, so, $(x_n + x_1 + x_2) \mod 2 \neq 0$ and  for those strings which start with $“10”,$ $x_n=1,x_{n-1}=1$ i.e. these strings ends with $11$, so, $(x_{n-1} + x_n + x_1) \mod 2 \neq 0$ and for those strings which start with $“01”,$ $x_n=0,x_{n-1}=1$ i.e. these strings ends with $10$, so, $(x_{n} + x_1 + x_2) \mod 2 \neq 0$, same we can do for $n = 3k+2$ ]

$\text{For } n\geq 6, \\ \text{If n is divisible by 3 then }\mathcal{C}~\text{contains : }$

$(000)^{\frac{n}{3}},(011)^{\frac{n}{3}},(101)^{\frac{n}{3}}~\text{and}~ (110)^{\frac{n}{3}}$

$\text{example: for n=6, }\\ \quad~\mathcal{C} ~= \{ 000000, 011011, 101101, 110110\}$

$\quad \left | \mathcal{C} \right | = 4$

$\text{If n is not divisible by 3 then }\mathcal{C}~\text{ only contains } (0)^n$

$\text{example: for n=7, }\\ \quad~\mathcal{C} ~= \{ 0000000\}$

$\quad \left | \mathcal{C} \right | = 1$

E is correct.

$\text{Note: Observe the cyclic property defined for } \mathcal{C},$ $\text{It should be cyclic in group of 3.}$

1 vote