Optimal number of operations in the given scenario?

45 Views Asked by At

Suppose $$A_1=\{x_1+x_2+x_3,\quad x_2+x_3+x_4,\quad x_3+x_4+x_5\} \\ A_2=\{x_0+x_1+x_2, \quad x_0+x_1+x_8, \quad x_0+x_7+x_8\} \\ A_3=\{x_{10}+x_{11}+x_{12}, \quad x_{11}+x_{12}+x_7, \quad x_7+x_8+x_{12}\}$$ By observation one can find that there is exactly one common pair ( , ) in a $A_i$ and exactly one common pair ( , ) between two $A_i$ for $i=1,2,3$. For example, $(x_1+x_2), (x_3+x_4), (x_7+x_8), (x_{11}+x_{12})$ etc. Using this observation one can reduce the total number of additions from $18$ to $14$. So, the whole idea is to reduce the total number of operations.

Is $14$ the optimal number of operations in the given scenario? If so, how can one prove it?