Sum of Dot Products

So we are basically just maximizing the number of 1's in the same place paired together when we divide all 16 binary numbers into pairs, as the dot product will be 0 unless two 1's are in the same place. Note that each pair must have at least one 0 and 1 in the same place, as otherwise the two numbers in the pair would have to be the same, which is of course impossible. Therefore, of the 16*4/2=32 1's in all 16 numbers, at least 8 must not be paired with another 1. This number is the only one that matters in our dot product. With some playing around with the numbers, we see that we can achieve this maximum: 1000 0100 0010 0001 1111 1011 1101 0111 0000 1100 0011 1001 1110 1010 1001 0110 There are therefore 24 1's which are paired with other 1's, or 12 total pairs, and so the answer is 12 (We could have gotten this from counting the pairs in our pairing)

Recall that $(x_1,x_2,x_3,x_4) \cdot (y_1,y_2,y_3,y_4)=x_1y_1+x_2y_2+x_3y_3+x_4y_4$ equals the number of values $i$ such that $x_i=y_i$ .

Let $k$ be the answer to the problem. Note that $k$ also denotes the total number of "overlaps" of two $1$ 's among all the pairs of vectors. Also note that by symmetry, there is an equal number of "overlaps" of two $0$ 's among the pairs of vectors as well.

Since there are $8$ pairings, each pair with $4$ "overlaps" of numbers, there are $32$ "overlaps" total. Hence, if $c$ denotes the number of "overlaps" of one $0$ and one $1$ , then we have that $2k+c=32$ . Thus we maximize $k$ when we minimize $c$ .

We see that if $c<8$ , then by the Pigeon Hole Principle, there exists a pair that shares no "overlaps" of one $0$ and one $1$ . Since that implies the two vectors are equal, this case fails. Hence, $c \geq 8$ . Since pairing vectors of the form $(0,x_1,x_2,x_3)$ with those of the form $(1,x_1,x_2,x_3)$ gets us $c=8$ , that is our minimum value of $c$ , and therefore our final value of $k$ is $\frac{32-8}{2}=12$ .

There are $16*4=64$ total entries, and 32 are 1's, 32 are 0's. That means the total sum is at most $32/2=16$ .

However, that is clearly not attainable. Within any pair of vectors, there will be at least 1 "mis-matched" pair of entries where they are not the same number (otherwise the two vectors would be the same). That means that at least 8 of the 1's will be forcibly paired with 0's, which means that the total potential sum is reduced by $8/2=4$ . Thus, our new maximum sum is $12$ . This is attainable with

$(1,1,1,1) \cdot (1,1,1,0)+(1,0,1,1)\cdot (0,0,1,1)$ $+(0,1,1,1)\cdot (0,1,0,1)+(1,1,0,1)\cdot(1,0,0,1)$ $+(1,1,0,0) \cdot (1,0,0,0)+(1,0,1,0) \cdot (0,0,1,0)$ $+(0,1,1,0) \cdot (0,1,0,0) +(0,0,0,1)\cdot (0,0,0,0)$

$a_1.a_2+a_3.a_4+...+a_{15}.a_{16}=\frac{1}{2}( (\sum_{i=1}^16 a_i^2)-$ $(\sum_{i=1}^8 (a_{2i-1}-a_{2i})^2 ) )$ . We see that: (I): $(\sum_{i=1}^16 a_i^2) =32$ because it's the sum of all squares of length of those vectors which have 4 coordinates, whose values are either 0 or 1. (II) : $( a_{2i} - a_{2i-1} ) \ne \overrightarrow{0}$ and its coordinates are in integer , thus : $( a_{2i} - a_{2i-1} )^2 \ge 1$ Together, (I) and (II) imply that : $\sum_{i=1}^8 a_{2i-1}.a_{2i} \le \frac{1}{2}( 32-8)=12$ . And for: $a_1=(1,0,0,0);a_3=(1,0,0,1);a_5=(1,0,1,0);a_7=(1,0,1,1)$ $a_9=(1,1,0,0);a_{11}=(1,1,0,1);a_{13}=(1,1,1,0);a_{15}=(1,1,1,1)$ $a_{2i}=a_{2i-1}-(1,0,0,0); i \in \overline{1;8}$ , we have the equality. Hence , the desired number is 12

The idea is to note certain inequalities regarding each of $a_i \cdot a_j$ to put an upper bound on that, and show that it's achievable. The inequalities come pretty intuitively (let the two vectors in a product to differ at exactly one position to maximize $a_i \cdot a_j$ ), but it needs to be proven formally...

For any $v \in \{0,1\}^4$ (basically $v$ is a vector described in the problem), define $|v|$ (called the value of $v$ ) as the sum of its four coordinates. For example, $|(0,1,0,1)| = 0+1+0+1 = 2$ . Also, define $(i_1,i_2,i_3,i_4) * (j_1,j_2,j_3,j_4)$ as $(i_1j_1, i_2j_2, i_3j_3, i_4j_4)$ ; hence the dot product $u \cdot v$ is $|u * v|$ . Note that this new operation is basically AND operation done to each component independently. Throughout this solution, $u,v$ are distinct vectors over $\{0,1\}^4$ .

Note that $|u * v| \le \min(|u|, |v|)$ . To see this, let $u = (i_1, i_2, i_3, i_4), v = (j_1, j_2, j_3, j_4)$ . Then $|u * v| = i_1j_1 + i_2j_2 + i_3j_3 + i_4j_4, |u| = i_1 + i_2 + i_3 + i_4, |v| = j_1 + j_2 + j_3 + j_4$ . So we want to prove that $i_1j_1 + i_2j_2 + i_3j_3 + i_4j_4 \le \min(i_1+i_2+i_3+i_4, j_1+j_2+j_3+j_4$ . But this is immediate; as $j_i \le 1, i_i \ge 0$ for all $i$ , we have $i_1j_1 + i_2j_2 + i_3j_3 + i_4j_4 \le i_1 * 1 + i_2 * 1 + i_3 * 1 + i_4 * 1 = i_1 + i_2 + i_3 + i_4$ . We can prove $i_1j_1 + i_2j_2 + i_3j_3 + i_4j_4 \le j_1 + j_2 + j_3 + j_4$ by the same way, giving the desired inequality.

We will also prove that $|u * v| < \max(|u|, |v|)$ . If $|u| \neq |v|$ , the inequality is obvious by $|u * v| \le \min(|u|, |v|) < \max(|u|, |v|)$ . Otherwise, suppose $|u * v| = |u| = |v|$ . As $u, v$ cannot be identical, they must differ somewhere; WLOG $u$ has a first component of 1 and $v$ has a first component of 0. Hence the first component of $u * v$ is 0 and hence is different from $u$ . Meanwhile, since any component of $u * v$ cannot be greater than the corresponding component of $u$ , the only way that $|u| = |u * v|$ is if they are identical, but we have proven that they differ at at least the first component. Hence $|u * v| < \max(|u|, |v|)$ . Since $|u * v|$ and $\max(|u|, |v|)$ are integers, we have $|u * v| \le \max(|u|, |v|) - 1$ .

Adding the two inequalities together, we have $2|u * v| \le \min(|u|, |v|) + \max(|u|, |v|) - 1 = |u| + |v| - 1$ ; call this inequality (1).

Now, multiply the desired expression by $2$ to obtain $2|a_1 * a_2| + 2|a_3 * a_4| + \ldots + 2|a_{15} * a_{16}|$ . We can now put an upper bound on this by (1) done to each product: $2|a_1 * a_2| + 2|a_3 * a_4| + \ldots + 2|a_{15} * a_{16}|$ $\le (|a_1| + |a_2| - 1) + (|a_3| + |a_4| - 1) + \ldots + (|a_{15}| + |a_{16}| - 1)$ $= (|a_1| + |a_2| + \ldots + |a_{16}|) - 8$

Now note that $(|a_1|, |a_2|, \ldots, |a_{16}|)$ must be a permutation of $(0,1,1,1,1,2,2,2,2,2,2,3,3,3,3,4)$ (the values of all possible vectors), and hence their sum is fixed: $0+1+1+1+1+2+2+2+2+2+2+3+3+3+3+4 = 32$ . Hence:

$2|a_1 * a_2| + 2|a_3 * a_4| + \ldots + 2|a_{15} * a_{16}| \le (32) - 8 = 24$

Hence $a_1 \cdot a_2 + a_3 \cdot a_4 + \ldots + a_{15} \cdot a_{16} = |a_1 * a_2| + |a_3 * a_4| + \ldots + |a_{15} * a_{16}| \le 12$ . It remains to find a possible configuration for this bound, which there exists:

$a_1 = (1,1,1,1), a_2 = (1,1,1,0),$ $a_3 = (1,1,0,1), a_4 = (1,1,0,0),$ $a_5 = (1,0,1,1), a_6 = (1,0,1,0),$ $a_7 = (0,1,1,1), a_8 = (0,1,1,0),$ $a_9 = (1,0,0,1), a_{10} = (1,0,0,0),$ $a_{11} = (0,1,0,1), a_{12} = (0,1,0,0),$ $a_{13} = (0,0,1,1), a_{14} = (0,0,1,0),$ $a_{15} = (0,0,0,1), a_{16} = (0,0,0,0),$

Basically pair each vector with a 1 at its fourth component to an identical vector except that the new vector has a 0 at its fourth component. This configuration can be verified to achieve said maximum.

Hence the sought maximum is $\boxed{12}$ .

Let $|a_i|$ be the number of coordinates equal to one in the vector $a_i$ .

If we have two vectors $a_i$ and $a_j$ , then $a_i\cdot a_j\leq \dfrac{|a_i|+|a_j|-1}{2}$ , because $a_i\neq a_j$ and then we will have coordinates equal to one in $a_i$ and/or in $a_j$ that will be multiplied by zero in the dot product, so it will always be smaller than $\dfrac{|a_i|+|a_j|}{2}$ .

If all the dot products reach the maximum possible value, the sum of these values will be:

$\dfrac{\left(\displaystyle\sum_{i=1}^{16}|a_i|\right)-8}{2}$

And:

$\begin{aligned}\displaystyle\sum_{i=1}^{16}|a_i|&=0\cdot {4\choose0}+1\cdot {4\choose1}+2\cdot {4\choose2}+3\cdot {4\choose3}+4\cdot {4\choose4}\\ &=32\end{aligned}$

So, the sum will be smaller or equal to $\dfrac{32-8}{2}=12$ .

Now, we need to proof that is possible the sum be equal to $12$ . For this, the vectors $a_{2k-1}$ and $a_{2k}$ , for $k$ integer and $1\leq k\leq8$ , need to have exactly one different coordinate, so $a_{2k-1}\cdot a_{2k}=\dfrac{|a_{2k-1}|+|a_{2k}|-1}{2}$ .

For this, just associate the vector $a_i$ to the correspondent of the decimal number $i-1$ in the Gray code so that if the $4$ -bit representation of the $i-1$ Gray code number is $p_1p_2p_3p_4$ , let $a_i=(p_{1},p_{2},p_{3},p_{4})$ .

Call a vector (a, b, c, d) a k-vector if k of the elements are 1s. Call $a_{1}, a_{2}$ , $a_{3}, a_{4}$ , ..., $a_{15}, a_{16}$ pairs.

Note that there is 1 4-vector, 4 3-vector, 6 2-vector, 4 1-vector and 1 0-vector.

a) The 4-vector is paired with a 3-vector,

Then we have the dot product of the two vectors 3. Now consider the other 3 3-vectors. If 1 of them is paired with 3-vector, then the resulting dot product is at most 2, and the last 3-vector can be paired with either a 2-vector or a 1-vector (or a 0-vector). Note that the all cases produces at most 4 in the sum, which gives 9 < 12. If at least 1 of them is paired with a 1-vector or 0-vector, then we are left with 2 3-vectors, 6 2-vectors, 4 1 or 0-vectors. And it's obvious that we can get at most 8 for them, and so the sum is at most 11<12. Finally consider the case where all three 3-vectors are paired with 2-vectors, then we can get at most $2 \cdot 3 + 3 + 1 \cdot 3 = 12$ from them.

And we can deal with the other cases similarly so the sum is at most $\boxed{12}$ .

Now $12$ is attainable by pairing as follows :

1,1,1,1 with 1,1,1,0 giving 3

1,0,1,1 with 0,0,1,1 giving 2

1,1,0,1 with 1,1,0,0 giving 2

1,1,1,0 with 1,0,1,0 giving 2

1,0,0,1 with 1,0,0,0 giving 1

0,1,1,0 with 0,1,0,0 giving 1

0,1,0,1 with 0,0,0,1 giving 1

0,0,1,0 with 0,0,0,0 giving 0

Therefore, the answer is $3 + 2*3 + 1*3 = \boxed{12}$ .

To maximize its sum, the vector paired with $(1,1,1,1)$ should have three $1$ 's, since the dot product of this pair would be the sum of the entries of the other vector, so the maximum dot product for this pair is $3$ . Similarly, the vector paired with $(0,0,0,0)$ should have three $0$ 's, since the dot product of this pair is clearly zero so we minimize the sum of the entries of the other vector. Consider any other vector with three $1$ 's. Since there is no other same vector, the dot product cannot be $3$ . Therefore the maximum dot product for this pair is $2$ . The maximum sum of dot products of pairs with vectors that has three $1$ 's excluding the first one mentioned is $6$ . Consider any other vector with three $0$ 's. Since there is only one $1$ , therefore the maximum dot product for this pair is $1$ . The maximum sum of dot products of pairs with vectors that has three $0$ 's excluding the first one mentioned is $3$ . Summing these up gives us $0+3+6+3=12$ . Such a combination exists for example $\{(0,0,0,0),(0,1,0,0)\}, \{(1,0,0,0),(1,0,1,0)\}, \{(0,0,0,1),(1,0,0,1)\}, \{(0,0,1,0),(0,0,1,1)\}, \{(1,1,1,0),(1,1,0,0)\}, \{(0,1,1,1),(0,1,1,0)\}, \{(1,1,0,1),(0,1,0,1)\}, \{(1,1,1,1),(1,0,1,1)\}$ .

Our main strategy is to minimize the scenario of 0 1 or 1 0 appearing in our dot product as what we want is 1*1, which contributes to the sum.

Claim: for a vector with n entries of one, the way to minimize the dot product is to pair it with a suitable vector of n+1 entries of one. we define a 'suitable' vector as those vectors having their n entries of one (out of n+1)coincide with all the entries of one of the vector having n entries of one.

Proof: This is obvious. Any such pairing will yield a sum of n, which is of course the maximum attainable.

With this in mind, we try to construct the sequence of vectors which will fit the above criterion. One such vector is (0,0,0,0)(1,0,0,0)+ (0,1,0,0)(1,1,0,0)+(0,0,1,0)(0,0,1,1)+(0,0,0,1)(0,1,0,1)+(1,0,1,0)(1,1,1,0)+(1,0,0,1)(1,0,1,1)+(0,1,1,0)(0,1,1,1)+(1,1,1,1)(1,1,0,1) Calculating the dot product, we find that the maximum occurs at 12.

Each vector here can be represented by a unique ordered quadruplet of 0s and 1s: $a_n = [x_{n1}, x_{n2}, x_{n3}, x_{n4}]$

So, each product can be represented by $a_na_{n+1} = x_{n1}x_{(n+1)1}+x_{n2}x_{(n+1)2}+x_{n3}x_{(n+1)3}+x_{n4}x_{(n+1)4}$

In order to maximize all the products, we must maximize the number of times we have $1 \times 1$ in our products. In order to do so, we must minimize the number of times we have $1 \times 0$ , which wastes a 1.

We have 1 vector with 4 ones, 4 vectors with 3 ones, ${4 \choose 2} = 6$ vectors with 2 ones, 4 vectors with 1 one, and 1 vector with 0 ones.

Suppose we have $a_1 = [1, 1, 1, 1]$ . Since each vector is unique, $a_2$ can have at most 3 ones, and thus the product $a_1 \cdot a_2$ can be at most $1\times1+1\times1+1\times1+1\times0=3$ . In this case, we have one instance of $1\times0$ .

Our next largest product must be at most 2 since each vector with 3 ones must multiply by a vector with at most 2 ones that line up to produce a product. To produce a product of 2 with the minimum number of times we have $1 \times 0$ , we can multiply a vector with 3 ones by one with 2 ones, e.g. $1\times1+1\times0+0\times0+1\times1$ .

There still remains 2 vectors with 3 ones, so we can have at most 2 more products of 2.

Afterwards, what's remaining are 3 vectors with 2 ones, 4 vectors with 1 one, and 1 vector with 0 ones.

Matching the 3 vectors with 2 ones with 3 vectors with 1 one gives 3 maximum products of 1. Afterwards, we match the last vector with 1 one with the 0 vector, creating a product of zero.

In the end, we have an upper limit of $3+2+2+2+1+1+1+0=12$ as our product sum, which exists only if each product has exactly one $1 \times 0$ . To show that this upper limit product can exist, we can have the set of vectors $a_1=[1, 1, 1, 1], a_2 = [0, 1, 1, 1]$ [4 pairs with 3, making 3]

$a_3 = [1, 0, 1, 1], a_4 = [0, 0, 1, 1]$ [3 pairs with 2, making 2]

$a_5 = [1, 1, 0, 1], a_6 = [1, 0, 0, 1]$ [3 pairs with 2, making 2]

$a_7 = [1, 1, 1, 0], a_8 = [1, 1, 0, 0]$ [3 pairs with 2, making 2]

$a_9 = [1, 0, 1, 0], a_{10} = [1, 0, 0, 0]$ [2 pairs with 1, making 1]

$a_{11} = [0, 1, 0, 1], a_{12} = [0, 1, 0, 0]$ [2 pairs with 1, making 1]

$a_{13} = [0, 1, 1, 0], a_{14} = [0, 0, 1, 0]$ [2 pairs with 1, making 1]

$a_{15} = [0, 0, 0, 1], a_{16} = [0, 0, 0, 0]$ [1 pairs with 0, making 0]

This has a product sum of 12, our determined upper limit.

Beginning with (1,1,1,1), find pairs of vectors with the most corresponding 1s and eliminate. There is one vector pair with 3 corresponding 1s, three pairs with 2 corresponding 1s, three pairs with 1 corresponding 1s, and one pair left over with no corresponding 1s. An example pairing is listed below:

3: (1,1,1,1), (1,1,1,0)

2: (1,1,0,1), (1,1,0,0); (1,0,1,1), (1,0,1,0); (0,1,1,1), (0,1,1,0)

1: (1,0,0,1), (1,0,0,0); (0,1,0,1), (0,1,0,0); (0,0,1,1), (0,0,1,0)

0: (0,0,0,1), (0,0,0,0)

Thus, the value will be $3\left(1\right)+2\left(3\right)+1\left(3\right)+0\left(1\right)=12$ .

The list of 16 vectors consists of: 1 vector with all of its components equal to 1 ( type I ), 1 vector with all of its components equal to zero ( type II ), 4 vectors with three 1's and one 0 as components ( type III ), 4 vectors with three 0's and one 1 as components ( type IV ), and 6 vectors with two 1's and two 2's as components ( type V ).

In order to maximize the sum of the dot products, the type IV vector must be dotted to one of the four type III vectors, thus yielding a product equal to 3 and leaving three type III vectors in the process. It is essential to realize that the highest possible dot product after such is 2 since the type III vectors (which are the only potential vectors to give a product of 3) could not have the same coordinates. To maximize the sum, the 3 type III vectors should be dotted to 3 type V vectors with the position of the 1's in the type V corresponding to its type III pair. This yields three 2's as products and also leaving three type V vectors in the process. Using the same reasoning earlier, the remaining V vectors should be dotted to three type IV vectors such that the 1 in the type IV vector corresponds to a 1 in its pair. This yields three 1's as products. Lastly, the remaining type IV vector should be dotted with the type II vector to give a product equal to zero.

Therefore, the maximum sum is equal to 3+2+2+2+1+1+1+0= 12 .

The vectors in consideration are (0;0;0;0), (0;0;0;1), (0;0;1;0), ... , (1;1;1;0), (1;1;1;1). For convenience, I will refer to the "1" values as bits. Note the following observations:

• there are a total of 32 bits.
• because all vectors are different, in each dot product, one bit is "lost" by being multiplied with a zero.
• as there are 16 dot products, at least 8 bits will get lost
• in the best case, the remaining 32-8=24 bits are multiplied with each other and leave a sum of 12.

The maximum value is 12. We show that the ordering below actually produces this sum and is optimal:

a1 = (0;0;0;0), a2 = (0;0;0;1) a1.a2 = 0 a3 = (0;0;1;0), a4 = (0;0;1;1) a3.a4 = 1 a5 = (0;1;0;0), a6 = (0;1;0;1) a5.a6 = 1 a7 = (0;1;1;0), a7 = (0;1;1;1) a7.a8 = 2 a9 = (1;0;0;0), a10 = (1;0;0;1) a9.a10 = 1 a11 = (1;0;1;0), a12 = (1;0;1;1) a11.a12 = 2 a13 = (1;1;0;0), a14 = (1;1;0;1) a13.a14 = 2 a15 = (1;1;1;0), a17 = (1;1;1;1) a15.a16 = 3

Let wt(v) denote the number of ones in the vector v. First we prove:

Claim : For any $a_i \ne a_j$ , we have $2a_i\cdot a_j \le wt(a_i) + wt(a_j) - 1$ .

Proof : Consider two cases.

• If $a_i$ and $a_j$ have the same weight w, their dot product is clearly at most w-1, so the result follows.
• Otherwise, if $wt(a_i) < wt(a_j)$ , we get $wt(a_i) \le wt(a_j) - 1$ and the LHS is at most $2 wt(a_i) \le wt(a_i) + wt(a_j) - 1$ . QED

Thus, if $S := a_1 \cdot a_2 + a_3 \cdot a_4 + \ldots + a_{15}\cdot a_{16}$ , we have:

$2S \le wt(a_1) + \ldots + wt(a_{16}) - 8 = 24$

so $S \le 12$ . On the other hand, equality can be attained by pairing up $(x_1, x_2, x_3, 0)$ and $(x_1, x_2, x_3, 1)$ for all 8 possibilities of $(x_1, x_2, x_3)$ .

Hence, maximum value of S is 12.

Group the vectors in pairs such that you maximize the common 1's per pair. so pair four 1's with 3, the other 3 three's with two, the other 2 with 1, and the last 1 with 0. Now multiplying(dot product of vectors), (1 1 1 1) (1 1 1 0)=3 (1 1 0 1) (1 1 0 0)=2 (1 0 1 1) (1 0 1 0)=2 (0 1 1 1) (0 1 1 0)=2 (1 0 0 1) (1 0 0 0)=1 (0 1 0 1) (0 1 0 0)=1 (0 0 1 1) (0 0 1 0)=1 (0 0 0 1) (0 0 0 0)=0

Therefore,sum of the dot products of vectors=3+2+2+2+1+1+1=12.

Let me try yet a different approach. I like its elegance. It is really short, except that I give a very detailed proof here... And I will generalize it to $n$ -tuples. (For this problem, obviously $n = 4$ .)

First solve a (slightly) different problem.

Let $S = \{\pm 1\}^n$ be the set of all $n$ -tuples with coordinates $\pm 1$ . There are $2^n$ such tuples.

Claim 1. If $\vec a, \vec b$ are two distinct vectors in $S$ , then the maximum value of $\vec a\cdot \vec b = n-2$ .

Proof : If $k$ is the number of coordinates in which $\vec a$ and $\vec b$ are the same , then $\vec a\cdot \vec b = k - (n-k) = 2k-n$ . If $\vec a\not = \vec b$ then $k \leq n-1$ . Therefore the maximum value of the dot product is $2(n-1) - n = n-2.$

Claim 2. The elements of $S$ can be partitioned into $2^{n-1}$ pairs, so that for each pair $\{\vec a, \vec b\}$ , the dot product is $\vec a \cdot \vec b = n-2$ .

Proof: For any $(n-1)$ -tuple $(c_1, \dots, c_{n-1})$ , take the pair $\vec a = (c_1, \dots, c_{n-1}, -1)$ and $\vec b = (c_1, \dots, c_{n-1}, +1)$ . They differ only in one coordinate, so apply Claim 1 with $k = n-1$ .

From Claims 1 and 2 follows obviously:

Claim 3. This partition results in the maximum possible value of the sum of dot products, $\sum_{2^{n-1}\ \text{pairs}} \vec a \cdot \vec b = 2^{n-1}\cdot (n-2).$

Now tweak this conclusion so it fits our current problem.

To transform the coordinates $\pm 1$ into $0, 1$ , we apply the transformation $\vec a = (a_1, \dots, a_n) \mapsto \vec a' = (\tfrac12(a_1 + 1), \dots, \tfrac 12(a_n + 1)) = \tfrac12(\vec a + \vec e),$ where $\vec e = (1, 1, \dots, 1).$

Under this transformation, the dot product transforms as follows: $\vec a'\cdot \vec b' = \tfrac14(\vec a + \vec e)\cdot (\vec b + \vec e) \\ = \tfrac14(\vec a\cdot \vec b + (\vec a + \vec b)\cdot \vec e + \vec e \cdot \vec e).$ The last term $\vec e \cdot \vec e = n$ .

Now take the partitioning in pairs from Claim 2 above, and apply this transformation. The sum of the $2^{n-1}$ dot products becomes $\sum \vec a'\cdot \vec b' = \sum \tfrac14(\vec a\cdot \vec b + (\vec a + \vec b)\cdot \vec e + n) \\ = \tfrac14 \sum \vec a \cdot \vec b + \tfrac 14\left(\sum \vec a + \vec b)\right)\cdot \vec e + \tfrac14 \cdot 2^{n-1} \cdot n \\ = \tfrac 14\cdot 2^{n-1}\cdot (n-2) + 0 + \tfrac14 \cdot 2^{n-1} \cdot n \\ = \tfrac 14\cdot 2^{n-1}\cdot (2n -2) = \boxed{2^{n-2}\cdot (n-1)}.$

In the last step, we used $\sum_{\vec x \in S} \vec x = \vec 0$ , because of the symmetry of our original set of $n$ -tuples.

Substituting $n = 4$ we find the answer $2^{4-2}\cdot (4-1) = 2^2\cdot 3 = \boxed{12}$ .

a1 should be (0,0,0,0) and a16 should be (1,1,1,1) (ascending order of binary number) so the answer is 4x3=12

Consider a single dot product $x \cdot y$ . In order for this dot product to be at least $k$ , $x$ and $y$ must both have at least $k$ components that are $1$ . Moreover, since $x$ and $y$ are different, they must differ in at least one component. Therefore, the total number of components that are $1$ in $x$ and $y$ combined must be at least $2k+1$ .

Stated in reverse, if the total number of ones in $x$ and $y$ is $n$ , then their dot product is at most $\frac12n - \frac12$ . Therefore, the sum of all 8 dot products is at most $\frac12N - 4$ , where $N$ is the total number of ones in all vectors, which is easily found to be $32$ . Therefore, we establish an upper bound $12$ on the answer.

If we pair up the vectors such that in each dot product, the vectors differ only in the first component, which is trivially possible, it is easy to see that all the inequalities in the previous paragraph turn into equalities. Therefore, this pairing yields precisely the maximum value $\boxed{12}$

In general, for $2^d$ vectors in $d$ dimensions, the answer is $(d-1)2^{d-2}$ .

We must pair the 16 vectors and find the sum of all pairs of 1's that correspond in each pair. For example, (0,1,0,1) and (0,1,1,1) have a dot product of 2, since the second and fourth coordinates are both 1 in each. For convenience, let an n-vector be a vector with n 1's, and let a wasted 1 be one that is paired with a 0.

The total number of 1's is 32 (count, or do $\dfrac{16\cdot 4}{2}$ ). We can subtract those 1's that must be paired with a 0 and divide by two to get our answer. For each 2-vector (there are 6), one 1 must be wasted when being paired. If a 2-vector is paired with a 1-vector, one 1 is wasted from the 2-vector. If a 2-vector is paired with a 3-vector, one 1 is wasted from the 3-vector. If a 2-vector is paired with another 2-vector, a 0-vector, or a 4-vector, at least 2 1's are wasted. To minimize waste, let each 2-vector be paired with either a 1-vector or a 3-vector. Now, we have $32-6=26$ 1's left. However, whichever vector the 0-vector is paired with, clearly at least another 1 is wasted. If a 2-vector is paired is instead paired with the 0-vector, there is two wastage instead of 1. Similarly, whichever vector the 4-vector is paired with, at least another 1 is wasted. Now, we have $32-8=24$ 1's left, so if $24$ is achievable, it is correct.

Here is one way to achieve 24:

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

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

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

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

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

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

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

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

Therefore, the answer is $\dfrac{24}{2}=\boxed{12}$ .

We have one vector with no 1's, four vectors with one 1's, 6 vectors with two 1's, 4 vectors with three 1's, and one vector with 4 1's.

Since the dotproduct of vectors equals the sum of the products of corresponding coordinates, clearly we should pair (0, 0, 0, 0) with any of the vectors with one 1. Using the same logic, we should pair (1, 1, 1, 1) with any of the vectors with three one's. There are 12 vectors left.

If we pair the vectors with the same number of 1's with each other, the most we could possibly get is n-1 since they are distinct. However, if we pair a vector with n-1 1's with a vector with n 1's, we can get n-1 vectors optimally. So, we pair the three remaining one-1 vectors with three two-1 vectors, and the other two-1 vectors with the three three-1 vectors, making sure that our dot products are maximized, i.e. vectors with 1's in the same places are paired with each other.

Adding these all together, we have 0 + 3 + 3(1) + 3(2), or 12 as our dot product sum.

vectors are:

a1 = 0 0 0 0
a2 = 0 0 0 1
                             a1.a2 = 0
a3 = 0 0 1 0
a4 = 0 0 1 1
                             a3.a4 = 1
a5 = 0 1 0 0
a6 = 0 1 0 1
                             a5.a6 = 1
a7 = 0 1 1 0
a8 = 0 1 1 1
                             a7.a8 = 2
a9 = 1 0 0 0
a10 = 1 0 0 1
                             a9.a10 = 1
a11 = 1 0 1 0
a12 = 1 0 1 1
                             a11.a12 = 2
a13 = 1 1 0 0
a14 = 1 1 0 1
                             a13.a14 = 2
a15 = 1 1 1 0
a16 = 1 1 1 1
                             a15.a16 = 3

so sum is $= 0 + 1 + 1 + 2 + 1 + 2 + 2 + 3 = 12$