Proving there exists no algorithm that can solve a basic problem

Question

Consider the following basic problem, for which the statement is "obvious," but I can't seem to find totally convincing proof.

Problem: Let $S$ be a set of $n$ elements, where $n\geq 2$ is even. And let $f:S \rightarrow \{0, 1\}$ be a function that maps half of the elements in $S$ to $0$, and the other half to $1$. Suppose Alice picks an element from $S$ at random and passes it through $f$ to obtain a value $x \in \{0, 1\}$. Prove there exists no algorithm $A$ that can correctly predict the value $x$ given only $f$ and $S$ (Take $A$ to be a probabilistic polynomial-time algorithm for example).

I understand that this statement seems entirely trivial, but I cannot really form an argument that feels rigorous. What is the basic proof I am missing, or the definition I need to use?

Answer 1

Assuming you are sampling from $S$ uniformly, let $X$ be the random variable you are sampling.

Then the random variable $f(X)$ is a Bernoulli distribution with probability 0.5 to get either $0$ or $1$.

Thus, $\Pr[f(x)=a]=0.5$ for any $a\in\{0,1\}$. So no matter which outcome the algorithm predicts (it has to be independent of the choice of $x$), the probability it is right is exactly $0.5$ - meaning that it cannot predict anything.