I saw this example for exhaustive search to break the security of a PRF $F_k:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}$ where the key space is of size $|\mathcal{K}|=2^n$.
The claim is that there is an adversary $\mathcal{A}$ of size $2^n\cdot\text{poly}(n)$ that computes the values of $S_k = F_k([1]_2),F_k([2]_2),\dots,F_k([2n]_2)$ for all the keys. Queries the oracle $\mathcal{O(\cdot)}$ (which might be either $\mathcal{R(\cdot)}$ or $F_k(\cdot)$) for the same queries, i.e. $S_{\mathcal{O}}=\mathcal{O}([1]_2),\mathcal{O}([2]_2),\dots,\mathcal{O}([2n]_2)$, and returns $1$ if there exists a key $k$ for which $S_{\mathcal{O}}=S_k$, otherwise returns 0. It also mentioned that the probability to distinguish:
$\left|\Pr_{k\leftarrow\mathcal{K}}\left[\mathcal{A}^{F_k(\cdot)}=1\right]-\Pr_{k\leftarrow\mathcal{K}}\left[\mathcal{A}^{R(\cdot)}=1\right]\right|\geq1-2^{-n}$
(Where $[x]_2$ represents the binary representation in $n$ bits of $x$.)
I understand we must calculate the PRF for several messages in order to have significant number of bits and ensure $S_{\mathcal{O}}=S_k$ does not equal by chance. But I couldn't figure out why specificly choose $2n$? (I thought maybe we want to have somthing which depends on $n$ bits to have inverse-exponantial probaility for identical strings, but why the factor of 2 is added?)
Also, I don't understand why the probability isn't $\geq1-2^{-2n}$ since the chance for collision in random should be $2^{-2n}$?
Finally, is bruteforce attacks and exhaustive search are basically the same method with different name?