Solve a system for the existence or absence of variables I have a series of triplets. Only some of them have to be added to a triplet constant to get the result. The result, the constant and the series of triplets are all known and with fixed values.
For example, let's say we have $A = (a_1, a_2, a_3)$, $B$, $...$ to $Z = (z_1, z_2, z_3)$, and only 5 of them will satisfy the equation. We could have, for example: $B + G + J + M + W$, added to the constant:
$\begin{pmatrix} C_{1} \\ C_{2} \\ C_{3} \end{pmatrix}$
that would give the expected result, let's say:
$\begin{pmatrix} 50 \\ 100 \\ 150 \end{pmatrix}$
This looked like a very classic linear system to solve, using Gaussian elimination, so I tried to do it in this way. However, it doesn't seem to work, as I don't want to solve for the values of the triplets $A, B, ...$, but for their existence or not, as only one combination of triplets will satisfy the equation.
How could I do this?
EDIT: added finite-fields tag since the maths will probably take place in $GF(256)$, as I work with bytes and XOR (though I guess it shouldn't change the logic of the solving).
 A: So, incorporating the constant into the result, we have
$$
x_1 \,A_1  + x_2 \,A_2  +  \cdots  + x_n \,A_n  = S\quad \left| \begin{array}{l}
 \;A_1 ,A_1 , \cdots ,A_n ,S \in \left\{ {\left( {\begin{array}{*{20}c}
   {a_{k,1} }  \\  {a_{k,2} }  \\   {a_{k,3} }  \\
\end{array}} \right)} \right\}given \\ 
 \,x_1 ,x_2  \cdots ,x_n  \in \left\{ {0,1} \right\}\;unknown \\ 
 \end{array} \right.
$$
and the problem is to determine the $x_k$ knowing a priori that the solution is unique.
Hint about the solution
Now, start with a simple example, take the A's to be just scalars and take just two of them $A_1 = 2, \; A_2 = 3$ .
The equation is
$$
x_1 \,A_1  + x_2 \,A_2  = S \in \left\{ {0,2,3,5} \right\}
$$
Divide both sides by a positive integer $q$
$$
\begin{array}{l}
 \frac{{x_1 \,A_1  + x_2 \,A_2 }}{q} = x_1 \frac{{\,A_1 }}{q} + x_2 \,\frac{{A_2 }}{q} =  \\ 
  = x_1 \left( {\left\lfloor {\frac{{\,A_1 }}{q}} \right\rfloor  + \frac{{A_1 \bmod \left( q \right)}}{q}} \right)
 + x_2 \,\left( {\left\lfloor {\frac{{\,A_2 }}{q}} \right\rfloor  + \frac{{A_2 \bmod \left( q \right)}}{q}} \right) =  \\ 
  = \left\lfloor {\frac{S}{q}} \right\rfloor  + \frac{{S\bmod \left( q \right)}}{q} \\ 
 \end{array}
$$
Being the $x_k$ equal to $0$ or $1$, we can write
$$
x_1 \left( {A_1 \bmod \left( q \right)} \right) + x_2 \,\left( {A_2 \bmod \left( q \right)} \right) \equiv S\quad \left( {\bmod q} \right)
$$
and if we take $q$ to be in turn $A_1$ and $A_2$ we can establish the system
$$
\left\{ \begin{array}{l}
 x_1  \cdot 0 + x_2  \cdot \,1 \equiv S\left( {\bmod 2} \right) \\ 
 x_1  \cdot 2 + x_2  \cdot 0 \equiv S\left( {\bmod 3} \right) \\ 
 \end{array} \right.
$$
which is a $2 \times 2$ system, with a matrix that has a determinant not null (full rank),
and therefore has a unique solution for whichever set of numbers are given as the known column.
Therefore if S admits the on-off  representation in the $A_k$, that should be the solution of the system.
In fact we get
$$
\begin{array}{c|cccc}
   {S = }  &  0 & 2 & 3 & 5  \\
   {x_1  = }  &  0 & 1 & 0 & 1  \\
   {x_2  = }  &  0 & 0 & 1 & 1  \\
\end{array}
$$
The above until $\gcd (A_1, A_2)=1$, which ensures that the system has full rank,
also considering  Chinese Remainder Theorem.
I suppose you can take on  from here.
