Let $x_1, x_2, \ldots , x_n \in \{0, 1\}$. Number of possible solutions in terms of $n$?

Question

Let $x_1, x_2, \ldots , x_n \in \{0, 1\}$.

(a) Consider the equation $x_1 + x_2 + \ldots + x_n = 0 \pmod {2}$. How many solutions does this equation have? Express your answer in terms of $n$. For example, if $n = 2$, $x_1 + x_2 = 0$ has 2 solutions: $(x_1, x_2) = (0, 0)$ and $(x_1, x_2) = (1, 1)$.

(b) Consider the equations $x_1 + x_2 + \ldots + x_n = 0 \pmod{2}$,$x_1 + x_2 + \ldots + x_{10} = 0 \pmod{2}$ for $n > 10$.

How many solutions are there satisfying both equations?

For (a), I got that there are $\frac{2^n}{2}$ solutions.

Ex. if $n = 3$, then the possible ordered pairs are:

$$(0,0,0), (1,0,0), (0,1,0), (0,0,1), (1,1,0), (0,1,1), (1,0,1), (1,1,1)$$

There are eight possible pairs so $2^3$, and only the sums of 4 are modular congruent to $2$.

$(0,0,0) = 0$

$(1,1,0) = 2$

$(1,0,1) = 2$

$(0,1,1) = 2$

Assuming my answer to (a) is correct, how would I go about solving (b)?

Answer 1

If $x_1+\ldots +x_{10} = 0 \text{ mod}\ 2$, then $x_{11}+\ldots+x_n = 0\text{ mod}\ 2$, so each solution to the first equation can be paired to a solution of the second to obtain a solution to the original equation. Use that and the fact that the number of solutions of $x_{11}+\ldots+x_n = 0\text{ mod}\ 2$ is the same as the number of solutions of $x_{1}+\ldots+x_{n-10} = 0\text{ mod}\ 2$

Answer 2

For (a) pick anything for $x_2,x_3,\dots,x_n$. Given any specific choice of these there is a unique choice available for $x_1$ such that the overall sum is even. We were able to make $n-1$ choices freely and the remaining choice was forced. As such there are $2^{n-1}$ such sequences.

For (b) pick anything for $x_2,x_3,\dots,x_{10}$ and then pick anything for $x_{12},x_{13},\dots,x_n$. Given any specific choice of these, there is a unique choice available for $x_1$ such that the overall sum of specifically the first ten is even. After having placed that value for $x_1$, there is now a unique choice available for $x_{11}$ such that the overall sum of all elements is even. We had to make $n-2$ choices freely and the remaining two choices were forced. As such there are $2^{n-2}$ such sequences.