For what values of $k$ does $(1+x)^{500+k}(1-x)^{500-k}$ exceed $10^9$? Pretty simple question, for what values of $0\leq k \leq 500$ do we have $\max\{(1+x)^{500+k}(1-x)^{500-k}|x\in[0,1]\} \geq 10^9$ ?
Some trivial observations:
The problem is equivalent to finding the smallest $k$ so that $\max\{(1+x)^{500+k}(1-x)^{500-k}|x\in[0,1]\} < 10^9$
Clearly it is equal to $(1-x^{1000-2k})(1+x)^{2k}$ so we must have $(1+x)^{2k}\geq10^9$, since $1+x\leq 2$ this implies $2k\geq 30\implies k\geq 15$. Of course, this is probably useless.

Edit: Using the fact that maximum is reached at $\frac{k}{500}$ we can rephrase as:
$(500+k)^{500+k}(500-k)^{500-k}>500^{1000}10^9$
The following java problem solves this nicely in well under a second.
    import java.math.*;
public class eulerbla {
    public static void main(String[] args) {
        BigInteger potdiez = new BigInteger ("1000000000");
        BigInteger quinmas = new BigInteger("500");
        BigInteger quinmen = new BigInteger("500");
        BigInteger num;
        BigInteger bound = quinmen.pow(1000);
        bound= bound.multiply(potdiez);
        for(int k=0;k<=500;k++){
            num = (quinmas.pow(500+k));
            num = num.multiply(quinmen.pow(500-k));
            if(num.compareTo(bound)>=0){
                System.out.println(k);
            }
            quinmas=quinmas.add(BigInteger.ONE);
            quinmen=quinmen.subtract(BigInteger.ONE);
        }

    }

}

Output:102
 A: We can compute the critical point for $(1+x)^{500+k}(1-x)^{500-k}$: $x=\frac{k}{500}$. The value at this point is
$$
\left(1-\frac{k^2}{250000}\right)^{500}\left(\frac{500+k}{500-k}\right)^k
$$
For $k\lt500$, this is an increasing function of $k$, the derivative of its log is $\log\left(\frac{500+k}{500-k}\right)$, and computing values shows that for $102\le k\lt500$, $(1+x)^{500+k}(1-x)^{500-k}$ will be bigger than $10^9$ for $x=\frac{k}{500}$.
For $k\lt102$, $(1+x)^{500+k}(1-x)^{500-k}$ will not exceed $10^9$ on $[0,1]$.

We can approximate
$$
\overbrace{\left(1-\frac{k^2}{250000}\right)^{500}}^{\sim e^{-\frac{k^2}{500}}}\overbrace{\left(\frac{500+k}{500-k}\right)^k\vphantom{\left(\frac{k^2}{2}\right)^5}}^{\sim e^{2\frac{k^2}{500}}}
\sim e^{\frac{k^2}{500}}
$$
If we solve
$$
e^{\frac{k^2}{500}}=10^9
$$
we get
$$
k=\sqrt{4500\log(10)}=101.792
$$
A: $\max\{(1+x)^{m+k}(1-x)^{m-k}|x\in[0,1]\} \geq 10^9
$
Set $m = 500$.
Let
$a(x, k)
= (1+x)^{m+k}(1-x)^{m-k}
$.
$\frac{a(x, k+1)}{a(x, k)}
=\frac{(1+x)^{m+k+1}(1-x)^{m-k-1}}{(1+x)^{m+k}(1-x)^{m-k}}
=\frac{1+x}{1-x}
\gt 1
$
so
$a(x, k)$
is increasing for all $k$.
Similarly,
$\begin{array}\\
a'(x, k)
&=(m+k)(1+x)^{m+k-1}(1-x)^{m-k}-(m-k)(1+x)^{m+k}(1-x)^{m-k-1}\\
&=(1+x)^{m+k-1}(1-x)^{m-k-1}((m+k)(1-x)-(m-k)(1+x))\\
&=(1+x)^{m+k-1}(1-x)^{m-k-1}((m+k)-(m-k)-x((m+k)+(m-k))\\
&=(1+x)^{m+k-1}(1-x)^{m-k-1}(2k-2mx)\\
&=0
\qquad\text{for }x = k/m\\
\end{array}
$
Therefore,
for fixed $k$,
$a(x, k)$
is max for
$x = k/m$.
At this $x$,
$\begin{array}\\
b(k, m)
&=a(k/m, k)\\
&=(1+k/m)^{m+k}(1-k/m)^{m-k}\\
&=\frac{(m+k)^{m+k}(m-k)^{m-k}}{m^{2m}}\\
\end{array}
$
If $k = cm$,
$0 < c < 1$,
$\begin{array}\\
b(cm, m)
&=(1+c)^{m(1+c)}(1-c)^{m(1-c)}\\
&=\left((1+c)^{(1+c)}(1-c)^{(1-c)}\right)^m\\
\end{array}
$
To find where
$b(cm, m)
= 10^9$,
when $m = 500$,
we want
$g(c)
=10^{9/500}
\approx 1.042
$.
According to Wolfy,
this is about
$c=0.203$.
This corresponds to
$k = cm
=0.203\cdot 500
\approx 101.5
$.
This agrees fairly well
with your computation.
