# Proving there exists no algorithm that can solve a basic problem

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?

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.