The probability two balls have the same number 
Suppose I have $10^6$ jars, and $k$ balls are randomly and independently placed in each jar. I am given that the probability that there exists a jar with 2 balls is approximately $50\%$. Then $k$ is:

*

*$500000$

*$64$

*$1+2+\ldots+64$

*$\approx 64\log(64)$

So my way of thinking is this. $k$ balls are given a random number from $1$ to $10^6$. I go ball by ball, and ask it whether or not it has a companion. I am having trouble of how to do this mathematically. The probability the $i$-th ball has a number already given is at most $\displaystyle\frac{10^6-(i-2)}{10^6}$ (since the first ball gets a unique number with probability 1). The problem I am facing is determining the exact value.
My answers say that the result is $4$, but I don't have any lead on how to achieve that.
 A: We can show that the question is wrong whether it means "at least 2 balls" or "exactly 2 balls".
$\def\lfrac#1#2{{\large\frac{#1}{#2}}}$
At least 2 balls
This is clearly equivalent to throwing $n$ balls one at a time into a random jar. The probability of each ball avoiding all the previous balls is $\prod_{i=0}^{k-1} (1-\frac{i}{n})$. To estimate this accurately, we pair the large with the small, so we want $\sqrt{\prod_{i=0}^{k-1} (1-\frac{i}{n})(1-\frac{k-1-i}{n})}$. Note that given any positive reals $a,b,c,d$ such that $a+b=c+d$, if $a \le c \le d \le b$ then $ab \le cd$. This gives us both lower and upper bounds on what we want, namely $(1-\frac{k-1}{n})^{k/2}$ and $(1-\frac{k-1}{2n})^k$ respectively. The lower bound alone is already enough to disprove the question's given answer, since even if we have $300$ balls, much more than $64 \ln(64)$ balls, the probability that they all land in different jars is at least $(1-\frac{266}{10^6})^{267/2}>0.965$, and hence having at least two in the same jar has probability less than $3.5\%$, nowhere near $50\%$.
In fact the bounds above are asymptotically close if $k^3 \ll n^2$, which can be easily seen by using the Taylor expansions of $\exp,\ln$. Specifically, let $r = \frac{k-1}{n}$ for convenience, and now if $r < \frac12$ we get a lower bound of $(1-\frac{k-1}{n})^{k/2} = \exp(\ln(1-r)\frac{k}{2}) \ge \exp((-r-r^2)\frac{k}{2}) = \exp(-\frac{kr}{2})\exp(-\frac{kr^2}{2})$ and an upper bound of $(1-\frac{k-1}{2n})^k = \exp(\ln(1-\frac{r}{2})k) \le \exp(-\frac{kr}{2})$. The discrepancy vanishes if $kr^2 \to 0$, which is equivalent to $\frac{k^3}{n^2} \to 0$.
So in fact we can solve accurately for $k$ given the probability $p$ of each jar having at most one ball, since $p \approx \exp(-\frac{k(k-1)}{2n})$ when $k^3 \ll n^2$, and hence $k^2-k \approx -2n\ln(p)$ when $-\ln(p)^3 \ll n$, in which case $k \approx \frac12(1+\sqrt{1-8n\ln(p)}) \approx \sqrt{-2n\ln(p)}$ if $n \gg 0$. If we want $⟨n,p⟩ \approx ⟨10^6,0.5⟩$ we would need $k \approx 1178$, which gives $q \in (0.50015,0.50026)$, where $q = 1-p$ is the probability that some jar has at least 2 balls. (Note that the other answer does not give any bounds on the error of the Poisson approximation, and one needs the above bounds to do so, which also show that taking $k = 1178$ makes $q$ closer to $50\%$ than taking any other value for $k$.)
Exactly 2 balls
"Exactly 2" is less likely than "at least 2". Thus the lower bounds in the previous section imply that the probability of a jar having exactly 2 balls is less than $1-(1-\frac{k-1}{n})^{k/2}$, and the calculations show that we would need at least $1178$ balls. Perhaps surprisingly, we shall now show that we need no more than that! The probability that some jar has at least 3 balls is at most $\lfrac{n^{k-2}C(k,3)}{n^k} < \lfrac{k^3}{6n^2}$. When $k = 1178$, this is less than $0.00028$, and hence the probability $q_2$ of some jar having exactly 2 balls is clearly in the range $(0.49987,0.50026)$. One can check that this is the best choice for $k$, since taking $k = 1179$ makes $q_2 \ge 0.50046$.
A: Let $m= 10^6$ and k be the number of balls
There are $m \choose 1$ jars that could have only two balls, and for each of those there are $m-1$ jars to distribute the rest of the $k-2$ balls (counted by using the stars-and-bars principle with $m-2$ 'bars' and $k-2$ 'stars').
So far that's  $\dbinom{m}{1}\dbinom{m+k-2-1-1 }{ m-2} = \dfrac{m!(m+k-4)!}{1!(m-1)!(m-2)!(k-2)!}$
However, to avoid double counting we must use the exclusion inclusion principle.  Subtract the ways to have two jars with only two balls, add back those with three such jars, etc. till you reach $m-\frac{k}{2}$ such jars.
If by some means you can calculate this for k that will be your answer:
$$\frac{\left[\sum_{i=1}^{\frac{k}{2}} (-1)^{(i+1)} {10^6\choose i}{(10^6+k-3i-1)\choose(10^6-i-1)}\right]}{{(10^6+k-1)\choose (10^6-1)}} = 0.5$$
If you can back calculate this with k = 840, you are very close to the answer of 0.5.  So now, I am confident of this solution.
You can try the formula in Wolfram

Edit:
You can use Poisson Approximation  for the problem:
Thus $Poi\left(\frac{{k\choose2}}{10^6}\right) = Poi(u)$
$$P(X>0) = 1-e^{-u} = 0.5 => e^{-u} = 0.5 => u = ln(2)$$
$$\frac{k(k-1)}{2.10^6} = ln(2)$$
Applying quadratic solution  $\frac{\sqrt{b^2-4ac}}{2}$
=> $$k \approx \frac{\sqrt{4.2.10^6.ln(2)}}{2} = 1177$$
The choice d equates to 115.5
For k to be equal to this choice, the number of jars should have been  $10^4$. which would have resulted in 117.7 which is the  fourth choice
Goodluck
