Eh... Absolutely trivial for an olympiad..

Suppose we have $n$ coins numbered $1,2,\ldots,n$, and let $a_i$ be the probability that coin $i$ turns heads. Let Lolek and Bolek play a game using these coins. They throw all the coins and observe the parity of the number of heads. If it's odd, then Lolek wins, otherwise Bolek wins. Then the sum given in the problem is the probability that Lolek wins, and the problem becomes "prove that if Lolek has a fair (1/2) chance of winning, then at least one of the coins is fair (probability 1/2 for each side)". Why do I choose those names? Because it's now more or less the same problem as IPSC 2012 Problem F (solution in Page 28).

I'd just like to point out that \[ \sum_{|S| \text{ odd}} f(S) - \frac{1}{2} = (-2)^{n-1} \prod_{k=1}^n \left (a_k - \frac{1}{2}\right ). \] Note that if $a_1=\frac{1}{2}$, then \begin{align*} \sum_{|S| \text{ odd}} f(S) - \frac{1}{2} &= \frac{1}{2}\sum_{T\in \{2, ... , n\}} \left ( \prod_{i\in T} a_i \cdot \prod_{j \not \in T} (1-a_j) \right )- \frac{1}{2} \\ &= \frac{1}{2} \prod_{k=2}^n \left (a_k + (1-a_k) \right ) - \frac{1}{2} \\ &= \frac{1}{2} - \frac{1}{2} \\ &= 0. \end{align*} So $a_1 - \frac{1}{2}$ is a factor of $\sum_{|S| \text{ odd}} f(S) - \frac{1}{2}$. Then by symmetry $a_2 - \frac{1}{2}, \cdots , a_n - \frac{1}{2}$ are also factors of it and since it is an n-degree polynomial, we only now seek a constant term of multiplication which can be evaluated by adjusting the constant term to be $-\frac{1}{2}$.

The typical hoperaiser (or maybe ego gainer :3). Define $b_i = 2a_i -1$. Also define $f_n(x) = \sum_{S} \prod_{i \in S}(x+ b_i) \prod_{ j \nin S} (x-b_j)$. Let $f(x) = g_n(x) + h_n(x)$, where $g$ is the sum for subsets with even cardinality and $g$ the sum for subsets with odd cardinality. Claim 1: $f_n(x) = (2x)^n$. Proof: Induction. Clearly holds for $n=2$. Suppose that its true for $n=N$. We show that its also true for $n=N+1$. Now note that $f_{N+1}(x) = f_N(x)(x+b_{N+1) + f_N(x)(x-b_{N+1}) = 2x f_n(x) = (2x)^{n+1}}$. Claim 2: $h_n(x) = 2^{n-1} \left( x^n + (-1)^{n-1}b_1b_2 \cdots b_n \right)$. Proof: Induction. Clearly true for $n=2$. Suppose that this holds for $n=N$. We show its also true for $n=N+1$. Now, we have \[ h_{N+1}(x) = g_n(x)(x+b_{n+1}) + h_n(x)(x-b_{n+1}) = xf_n(x) + b_{n+1}(g_n(x)-h_n(x)) \]\[= xf_n(x) + b_{n+1}(f_n(x)-2h_n(x)) = 2^n(x^{n+1} + (-1)^nb_1b_2 \cdots b_{n+1})\]We are given that $h_n(1) = 2^{n-1}$. Therefore, we get $b_1b_2\cdots b_n =0$. Therefore, $\exists k$ such that $b_k =0$, and equivalently, $a_k=1/2$.

Let $g(n)=\sum_{|S|\text{ odd}} f(S)$ and $h(n)=\sum_{|S|\text{ even}} f(S)$ where $n$ is held fixed. We claim that $$g(n)=1/2+1/2(-1)^{n+1}(2a_1-1)(2a_2-1)(2a_3-1)...(2a_n-1)$$ and $$h(n)=1-g(n)=1/2(-1)^n (2a_1-1)(2a_2-1)(2a_3-1)...(2a_n-1)$$ We prove this via induction on $n$. Its not hard to verify the formulas for $g(2)$ and $h(2)$. Now we apply the inductive step. Consider adding the term $a_{n+1}$ to our sequence. We see that $g(n+1)=a_{n+1}h(n)+(1-a_{n+1})g(n)$ and $h(n+1)=a_{n+1}g(n)+(1-a_{n+1})h(n)$. This proves the inductive step. Finally, the equation $g(n)=1/2$ gives $(2a_1-1)(2a_2-1)(2a_3-1)...(2a_n-1)=0$, so one of the $a_i$ equals $1/2$, as desired.

Notice that $\sum_S f(S) = \prod_{i = 1} ^ n (a_i + (1 - a_i))$. In particular, $\sum_{|S|=2k} f(S) = \sum_{|S| = 2k + 1} f(S)$. This motivates considering the polynomial $\prod_{i = 1} ^ n (a_i + (1-a_i)x)$. Notice that $-1$ is a root, so one of the terms $a_i+(1-a_i)(-1) = 0$, or $a_i = \frac 1 2$ as desired.

Note that in the expansion of the product \[(2a_1 - 1)(2a_2-1)\cdots (2a_n - 1) = \left(a_1 - (1-a_1)\right)\left(a_2 - (1-a_2)\right)\cdots\left(a_n - (1-a_n)\right),\]all terms are of the form \[ f(S) = \prod_{i \in S} a_i \cdot \prod_{j \not \in S} (1-a_j)\]for some set $S$, and this term is positive iff $|[n]\setminus S|$ is even; thus, the expression becomes equal to \[\sum_{|[n]\setminus S|\text{ even}}f(S) - \sum_{|[n]\setminus S|\text{ odd}}f(S) = 0,\]and so by Zero Product Property one of the $a_i$ must be $\tfrac12$.

Don't get scared. It's just very formalized, but after a while you will surely understand it. Make substitution $x_i=\frac{a_i}{1-a_i}$, and let $P=(1-a_1)\cdot...\cdot (1-a_n)$. Then $x_i\in R_+\wedge 1-a_i=\frac{1}{x_i+1}$. First equality comes strictly from definition of this sum. $$\sum_{|S| \text{ odd}} f(S)=P\cdot \sum_{1\le k\le n\wedge k\in2\mathbb Z+1}\sum_{1\le i_1<...<i_k\le n}\prod_{j=1}^k \frac{a_{i_j}}{1-a_{i_j}}=\prod_{l=1}^n\frac{1}{x_l+1}\cdot \sum_{1\le k\le n\wedge k\in2\mathbb Z+1}\sum_{1\le i_1<...<i_k\le n}\prod_{j=1}^k x_{i_j}$$Hence $$\sum_{|S| \text{ odd}} f(S) = \frac{1}{2}\iff 2 \sum_{1\le k\le n\wedge k\in2\mathbb Z+1}\sum_{1\le i_1<...<i_k\le n}\prod_{j=1}^k x_{i_j}=\prod_{l=1}^n(x_l+1)$$$$\iff\sum_{1\le k\le n\wedge k\in2\mathbb Z+1}\sum_{1\le i_1<...<i_k\le n}\prod_{j=1}^k x_{i_j}=1+\sum_{1\le k\le n\wedge k\in2\mathbb Z}\sum_{1\le i_1<...<i_k\le n}\prod_{j=1}^k x_{i_j}$$$$0=1+\sum_{1\le k\le n\wedge k\in\mathbb Z}\sum_{1\le i_1<...<i_k\le n}(-1)^k\prod_{j=1}^k x_{i_j}$$$$0=(-1)^n+\sum_{1\le k\le n\wedge k\in\mathbb Z}\sum_{1\le i_1<...<i_k\le n}(-1)^{n-k}\prod_{j=1}^k x_{i_j}$$$$0=\prod_{i=1}^n(x_i-1)$$$$\exists_{1\le j\le n}\ ( j\in\mathbb Z\wedge x_j=1)$$Using the definition of our substitution $$\exists_{1\le j\le n}\ ( j\in\mathbb Z\wedge a_j=\frac{1}{2})$$

Nice! Here's my solution: Suppose we choose a subset of $X_n=\{1,2, \dots,n\}$ randomly, such that the element $i$ is chosen with probability $a_i$ for every $1 \leq i \leq n$. Then $f(S)$ simply represents the probability that we chose our subset as $S$. We proceed by induction on $n \geq 1$, with the case $n=1$ being obvious. So suppose the result is true for some $n$, and consider $X_{n+1}$. FTSOC assume that $a_k \neq \frac{1}{2}$ for all $1 \leq k \leq n+1$. Let $P_1$ (resp. $P_2$) denote the set of even (resp. odd) subsets of $X_n$ containing the element $a_{n+1}$. Similarly, let $Q_1$ (resp. $Q_2$) denote the set of even (resp. odd) subsets of $X_n$, which do not contain the element $a_{n+1}$. Consider some set $P \in P_1 \cup P_2$, and let $\psi(P)=P-\{a_{n+1}\}$. Then for $P \in P_1$ (resp. $P \in P_2$), we have $\psi(P) \in Q_2$ (resp. $\psi(P) \in Q_1$). Also, note that we have $f(\psi(P))=\frac{1-a_{n+1}}{a_{n+1}}f(P)$ for all $P \in P_1 \cup P_2$. In general, this means $$f(Q_1)=\frac{1-a_{n+1}}{a_{n+1}}f(P_2) \text{ and } f(Q_2)=\frac{1-a_{n+1}}{a_{n+1}}f(P_1)$$where $f(P_1)$ represents the sum of $f$ values for all sets in $P_1$, i.e. it is the probability of choosing a subset out of $P_1$ (and similarly for $P_2,Q_1,Q_2$). Now, from the given hypothesis (and since $\{P_1,Q_1\}$ and $\{P_2,Q_2\}$ are mutually exclusive), we have $$f(P_1 \cup Q_1)=f(P_2 \cup Q_2) \Rightarrow f(P_1)+f(Q_1)=f(P_2)+f(Q_2)=\frac{a_{n+1}}{1-a_{n+1}}f(Q_1)+\frac{1-a_{n+1}}{a_{n+1}}f(Q_1) \Rightarrow \frac{1-2a_{n+1}}{1-a_{n+1}}f(Q_1)=\frac{1-2a_{n+1}}{a_{n+1}}f(P_1)$$Since $a_{n+1} \neq \frac{1}{2}$, and using $f(P_1)+f(Q_1)=\frac{1}{2}$, we get that $$(1-a_{n+1})f(P_1)=a_{n+1}f(Q_1) \Rightarrow f(P_1)=a_{n+1}(f(P_1)+f(Q_1))=\frac{a_{n+1}}{2}$$Let $O_n$ be the set of odd subsets of $X_n$. Then $$O_n=P_1-\{a_{n+1}\} \Rightarrow f(O_n)=f(P_1-\{a_{n+1}\})=\frac{f(P_1)}{a_{n+1}}=\frac{1}{2}$$Thus, the numbers $a_1,a_2, \dots ,a_n$ also satisfy the problem condition. Then our original assumption (that none of the $a_i$'s are equal to $\frac{1}{2}$) contradicts the induction hypothesis. Hence, done. $\blacksquare$

Claim: $\sum_{S} f(S) = 1$. Proof: By linearity of expectation, the expected value of $f(S)$ for a random $S$ is $\prod_{i=1}^n \tfrac{1}{2} = \tfrac{1}{2^n}$, so summed over all sets, the total sum is $1$. We now prove the problem by induction on $n$; we show that, assuming none of $a_1, a_2, \dots, a_n$ are equal to $\tfrac{1}{2}$, then $\sum_{|S| \text{ odd}} f(S) \neq \tfrac{1}{2}$. Base case: $n=1$, obvious. Inductive step: for $n > 1$, let $T$ be any subset of $\{ 1, 2, \dots, n-1 \}$. We have \begin{align*} & \sum_{|S| \text{ odd}} f(S) \\ = ~ & (1-a_i) \sum_{|T| \text{ odd}} f(S) + a_i \sum_{|T| \text{ even}} f(S) \\ = ~ & (1-a_i) (1-x) + a_i \cdot x \\ = ~ & \frac{(2a_i - 1)(2x-1)}{2} + \frac{1}{2}, \end{align*}where $x \neq \tfrac{1}{2}$ by our inductive step. So, ${ \sum_{|S| \text{ odd}} f(S)} \neq \tfrac{1}{2}$.