In a battle of $n$ different faiths, what is the probability of all of them being wrong? Assuming we have no knowledge about any of them and at most only one can be right, what is the probability that all of the faiths are wrong?
This is how our teacher solved it today:

Since we have no knowledge about any of them, we have to treat them equally. We have $n$ faiths, so the probability of faith $i$ being wrong is $1/n$ and therefore the probability of all of them being wrong is $1/n^n$.

Then he concluded we should choose some faith because the probability of all of them being wrong (not choosing any faith at all) is much less (he was not teaching us math).
I know this answer is wrong but I don't know how to solve it correctly.

With three or more faiths, atheism is your best option.
Under the implied assumptions, the probability of faith $i$ being right is $\frac 1n$. Thus the probability of it being wrong is $\frac {n-1}{n}$.
As $n$ gets (modestly) large, the probability of all being wrong $\left(\frac {n-1}{n}\right )^n \approx \frac 1e \approx 37\%$
(there are a number of problems with this whole set-up, but as you note the lesson was not really about math).
