1
$\begingroup$

I have a vector of numbers $x_i$ that can only have the values $0$ or $1$.

I need to find all the possible combinations $(x_1,x_2,x_3,x_4,x_5,x_6)$ such that:

$$\begin{cases} x_1+x_5+x_6 \ \mathrm{is\ odd}\\ x_2+x_4+x_6 \ \mathrm{is\ odd} \\ x_3+x_4+x_5 \ \mathrm{is\ odd} \end{cases} $$

How could I do this? I mean, I can think of some combinations but I don't know how to find all of them, or the number of possible solutions.

$\endgroup$
2
$\begingroup$

First a preliminary remark:

If we fix one number $N$ in such a conditional, we find $$a + b + N \text{ odd}, a,b,N \in \{0, 1\}$$ implies for $N = 1$: $$a + b + 1 \text{ odd} \Leftrightarrow a = b$$ and for $N = 0$: $$a + b + 0 \text{ odd} \Leftrightarrow a \ne b \Leftrightarrow a = 1 - b$$

Now we can start by systematically making cases:

  • $x_1 = 1$
    Equation (I) now reads $1 + x_5 + x_6$ is odd, i.e. $x_5 = x_6$
    • $x_5 = x_6 = 1$
      Now Equations (II) and (III) combine to $x_2 = x_3 = x_4$, so we have $(1, 0, 0, 0, 1, 1)$ and $(1, 1, 1, 1, 1, 1)$ as solutions
    • $x_5 = x_6 = 0$
      This means $x_2 \ne x_4$ and $x_3 \ne x_4$, so $x_2 = x_3 = 1 - x_4$.
      Again we find two solutions:
      $(1, 0, 0, 1, 0, 0)$ and $(1, 1, 1, 0, 0, 0)$
  • $x_1 = 0 \Rightarrow x_5 \ne x_6$
    • $x_5 = 1, x_6 = 0$ gives us $x_3 = x_4$ and $x_2 \ne x_4$, so $x_2 = 1 - x_3 = 1 - x_4$ and we get the two solutions $(0, 1, 0, 0, 1, 0)$ and $(0, 0, 1, 1, 1, 0)$
    • $x_5 = 0, x_6 = 1$ and we get $x_2 = x_4$ and $x_3 \ne x_4$, so $x_2 = 1 - x_3 = x_4$ yielding the final two solutions $(0, 1, 0, 1, 0, 1)$ and $(0, 0, 1, 0, 0, 1)$
$\endgroup$
  • $\begingroup$ That was smooth! Thank you. Those would be all the solutions, right? I'm asking just in case, because I don't think there are more possibilities $\endgroup$ – Tendero Nov 3 '16 at 17:40
  • $\begingroup$ @Tendero Yes, these are all by exhaustion. I provided reason for the derivations in a preliminary note, just to clarify. Can you prove these statements yourself? $\endgroup$ – AlexR Nov 3 '16 at 17:41
  • $\begingroup$ Yes, I get that but I didn't know if there was some systematic method to follow to get all the possibilities. Thanks again! $\endgroup$ – Tendero Nov 3 '16 at 17:42
2
$\begingroup$

This question is really about solving the system

$$\begin{cases} x_1+x_5+x_6 =1 \\ x_2+x_4+x_6 =1 \\ x_3+x_4+x_5 =1 \end{cases} $$

in $\mathbb{Z}/2\mathbb{Z}$. Since that's a field, we should be able to use all the techniques of linear algebra, and just reduce a matrix:

$\left[\begin{array}{cccccc|c} 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 0 & 1 \end{array}\right]$

This matrix is already in reduced row-echelon form, so there are three free variables, and 8 solutions, corresponding to the eight possible values of $x_4$, $x_5$, and $x_6$, and completed by the equations $x_1=1+x_5+x_6$, $x_2=1+x_4+x_6$, and $x_3=1+x_4+x_5$, with all addition being performed in $\mathbb{Z}/2\mathbb{Z}$.

Namely:

$\begin{align} (x_4,x_5,x_6)=(0,0,0) &\implies (1,1,1,0,0,0) \\ (x_4,x_5,x_6)=(0,0,1) &\implies (0,0,1,0,0,1) \\ (x_4,x_5,x_6)=(0,1,0) &\implies (0,1,0,0,1,0) \\ (x_4,x_5,x_6)=(0,1,1) &\implies (1,0,0,0,1,1) \\ (x_4,x_5,x_6)=(1,0,0) &\implies (1,0,0,1,0,0) \\ (x_4,x_5,x_6)=(1,0,1) &\implies (0,1,0,1,0,1) \\ (x_4,x_5,x_6)=(1,1,0) &\implies (0,0,1,1,1,0) \\ (x_4,x_5,x_6)=(1,1,1) &\implies (1,1,1,1,1,1) \end{align}$

Reflecting back on the original problem, since each of $x_1, x_2, x_3$ each occur in precisely one condition, we see that the other three variables can be chosen freely, and then $x_1$ picked to make the first condition work, etc.

$\endgroup$
  • $\begingroup$ Much cleaner than my solution. You might want to list all eight solutions obtained this way. +1 $\endgroup$ – AlexR Nov 3 '16 at 18:19

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.