, 2017

Solution:

Consider the multivariate polynomial
$$\prod_{1 \leq i<j \leq 16}\left(1+x_{i} x_{j}\right)$$
We're going to filter this by summing over all $4^{16}$ 16-tuples $\left(x_{1}, x_{2}, \ldots, x_{16}\right)$ such that $x_{j}= \pm 1, \pm i$. Most of these evaluate to 0 because $i^{2}=(-i)^{2}=-1$, and $1 \cdot-1=-1$. If you do this filtering, you get the following 4 cases:

Case 1: Neither of $i$ or $-i$ appears. Then the only cases we get are when all the $x_{j}$ are 1, or they're all -1. Total is $2^{120}$. $\left(120=\binom{16}{2}.\right)$

Case 2: $i$ appears, but $-i$ does not. Then all the remaining $x_{j}$ must be all 1 or all -1. This contributes a sum of $(1+i)^{15} \cdot 2^{105}+(1-i)^{15} \cdot 2^{105}=2^{113}$. $i$ can be at any position, so we get $16 \cdot 2^{113}$.

Case 3: $-i$ appears, but $i$ does not. Same contribution as above. $16 \cdot 2^{113}$.

Case 4: Both $i$ and $-i$ appear. Then all the rest of the $x_{j}$ must be all 1 or all -1. This contributes a sum of $2 \cdot(1+i(-i)) \cdot(1+i)^{14} \cdot(1-i)^{14} \cdot 2^{91}=2^{107} \cdot i$ and $-i$ can appear in $16 \cdot 15$ places, so we get $240 \cdot 2^{107}$.

So the final answer is this divided a factor for our filter. $\left(4^{16}=2^{32}\right.$.) So our final answer is $\frac{2^{89}+16 \cdot 2^{82}+240 \cdot 2^{75}}{2^{120}}=\frac{1167}{2^{41}}$.

Therefore, the answer is 1167 .