Encontrar todas las soluciones de un sistema de ecuaciones

Question

Tengo un vector de números $x_i$ que sólo puede tener los valores $0$ o $1$ .

Necesito encontrar todas las combinaciones posibles $(x_1,x_2,x_3,x_4,x_5,x_6)$ tal que:

$$\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} $$

¿Cómo podría hacer esto? Se me ocurren algunas combinaciones pero no sé cómo encontrar todo de ellos, o el número de soluciones posibles.

Answer 1

Esta pregunta trata realmente de resolver el sistema

$$\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} $$

en $\mathbb{Z}/2\mathbb{Z}$ . Como es un campo, deberíamos poder utilizar todas las técnicas del álgebra lineal, y simplemente reducir una matriz:

$\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]$

Esta matriz ya está en forma reducida de fila-echelón, por lo que hay tres variables libres, y 8 soluciones, correspondientes a los ocho valores posibles de $x_4$ , $x_5$ y $x_6$ y se completa con las ecuaciones $x_1=1+x_5+x_6$ , $x_2=1+x_4+x_6$ y $x_3=1+x_4+x_5$ con toda la adición que se realiza en $\mathbb{Z}/2\mathbb{Z}$ .

A saber:

$\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}$

Si se reflexiona sobre el problema original, ya que cada uno de $x_1, x_2, x_3$ cada una ocurre precisamente en una condición, vemos que las otras tres variables pueden ser elegidas libremente, y entonces $x_1$ elegido para que la primera condición funcione, etc.

Answer 2

En primer lugar, una observación preliminar:

Si fijamos un número $N$ en dicho condicional, encontramos $$a + b + N \text{ odd}, a,b,N \in \{0, 1\}$$ implica para $N = 1$ : $$a + b + 1 \text{ odd} \Leftrightarrow a = b$$ y para $N = 0$ : $$a + b + 0 \text{ odd} \Leftrightarrow a \ne b \Leftrightarrow a = 1 - b$$

Ahora podemos empezar a hacer casos sistemáticamente:

• $x_1 = 1$
  La ecuación (I) queda ahora como sigue $1 + x_5 + x_6$ es impar, es decir $x_5 = x_6$
  • $x_5 = x_6 = 1$
    Ahora las ecuaciones (II) y (III) se combinan para $x_2 = x_3 = x_4$ , por lo que tenemos $(1, 0, 0, 0, 1, 1)$ y $(1, 1, 1, 1, 1, 1)$ como soluciones
  • $x_5 = x_6 = 0$
    Esto significa que $x_2 \ne x_4$ y $x_3 \ne x_4$ Así que $x_2 = x_3 = 1 - x_4$ .
    De nuevo encontramos dos soluciones:
    $(1, 0, 0, 1, 0, 0)$ y $(1, 1, 1, 0, 0, 0)$
• $x_1 = 0 \Rightarrow x_5 \ne x_6$
  • $x_5 = 1, x_6 = 0$ nos da $x_3 = x_4$ y $x_2 \ne x_4$ Así que $x_2 = 1 - x_3 = 1 - x_4$ y obtenemos las dos soluciones $(0, 1, 0, 0, 1, 0)$ y $(0, 0, 1, 1, 1, 0)$
  • $x_5 = 0, x_6 = 1$ y obtenemos $x_2 = x_4$ y $x_3 \ne x_4$ Así que $x_2 = 1 - x_3 = x_4$ dando lugar a las dos soluciones finales $(0, 1, 0, 1, 0, 1)$ y $(0, 0, 1, 0, 0, 1)$