Finding all solutions for an equation system 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.
 A: 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.
A: 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)$


