HMIC 2017 Problem 5

Let $S$ be the set $\{-1,1\}^{n}$, that is, $n$-tuples such that each coordinate is either -1 or 1 . For

$$s=\left(s_{1}, s_{2}, \ldots, s_{n}\right), t=\left(t_{1}, t_{2}, \ldots, t_{n}\right) \in\{-1,1\}^{n}$$

define $s \odot t=\left(s_{1} t_{1}, s_{2} t_{2}, \ldots, s_{n} t_{n}\right)$. Let $c$ be a positive constant, and let $f: S \rightarrow\{-1,1\}$ be a function such that there are at least $(1-c) \cdot 2^{2 n}$ pairs $(s, t)$ with $s, t \in S$ such that $f(s \odot t)=f(s) f(t)$. Show that there exists a function $f^{\prime}$ such that $f^{\prime}(s \odot t)=f^{\prime}(s) f^{\prime}(t)$ for all $s, t \in S$ and $f(s)=f^{\prime}(s)$ for at least $(1-10 c) \cdot 2^{n}$ values of $s \in S$.