Problem (Combinatorics):
For $k \geq 3$, we define an ordered $k$-tuple of real numbers $\left(x_{1}, x_{2}, \ldots, x_{k}\right)$ to be special if, for every $i$ such that $1 \leq i \leq k$, the product $x_{1} \cdot x_{2} \cdot \ldots \cdot x_{k}=x_{i}^{2}$. Compute the smallest value of $k$ such that there are at least 2009 distinct special $k$-tuples.

Solution:
The given conditions imply $k$ equations. By taking the product of these $k$ equations, we have $\left(x_{1} x_{2} \ldots x_{k}\right)^{k-1}=x_{1} x_{2} \ldots x_{k}$. Thus it follows that either $x_{1} x_{2} \ldots x_{k}=0$ or $x_{1} x_{2} \ldots x_{k}= \pm 1$. If $x_{1} x_{2} \ldots x_{k}=0$, then some $x_{j}=0$, and by plugging this into each of the equations, it follows that all of the $x_{i}$ 's are equal to 0 . Note that we cannot have $x_{1} x_{2} \ldots x_{k}=-1$, because the left hand side equals $x_{1}\left(x_{2} \ldots x_{k}\right)=x_{1}^{2}$, which can't be negative, because the $x_{i}$ 's are all given as real. Thus $x_{1} x_{2} \ldots x_{k}=1$, and it follows that each $x_{i}$ is equal to either 1 or -1 . Because the product of the $x_{i}$ 's is 1 , there must be an even number of -1 's. Furthermore, by picking any even number of the $x_{i}$ 's to be -1 , it can be readily verified that the ordered $k$-tuple $\left(x_{1}, x_{2}, \ldots, x_{k}\right)$ is special. Thus there are

$$
\left(\begin{array}{c}
k \\
0
\end{array}\right)+\left(\begin{array}{l}
k \\
2
\end{array}\right)+\left(\begin{array}{l}
k \\
4
\end{array}\right)+\ldots+\left(\begin{array}{c}
k \\
2\lfloor k / 2\rfloor
\end{array}\right)
$$

special non-zero $k$-tuples. By considering the binomial expansion of $(1+1)^{k}+(1-1)^{k}$, it is clear that the above sum of binomial coefficients equals $2^{k-1}$. Thus there are a total of



$2^{k-1}+1$ special $k$-tuples. Because $2^{10}=1024$ and $2^{11}=2048$, the inequality $2^{k-1}+1 \geq 2009$ is first satisfied when $k=\mathbf{1 2}$.

Use a recursive approach. Let $S_{k}$ denote the number of special non-zero $k$-tuples. From the analysis in the above solution, each $x_{i}$ must be either 1 or -1 . It can easily be verified that $S_{3}=4$. For $k>3$, suppose that $x_{k}=1$ for a given special $k$-tuple. Then the $k$ equations that follow are precisely the equation $x_{1} x_{2} \ldots x_{k-1}=1$ and the $k-1$ equations that follow for the special $(k-1)$-tuple $\left(x_{1}, x_{2}, \ldots, x_{k-1}\right)$. Because $x_{1} x_{2} \ldots x_{k-1}=1$ is consistent for a special $(k-1)$-tuple, and because this equation imposes no further restrictions, we conclude that there are $S_{k-1}$ special $k$-tuples in which $x_{k}=1$.

If, on the other hand, $x_{k}=-1$ for a given special $k$-tuple, then consider the $k$ equations that result, and make the substitution $x_{1}=-y_{1}$. Then the $k$ resulting equations are precisely the same as the $k$ equations obtained in the case where $x_{k}=1$, except that $x_{1}$ is replaced by $y_{1}$. Thus $\left(x_{1}, x_{2}, \ldots, x_{k-1},-1\right)$ is special if and only if $\left(y_{1}, x_{2}, \ldots, x_{k-1}\right)$ is special, and thus there are $S_{k-1}$ special $k$-tuples in which $x_{k}=-1$.

Thus the recursion becomes $S_{k}=2 S_{k-1}$, and because $S_{3}=4$, it follows that $S_{k}=2^{k-1}$.

Final answer: 12