I am having a difficult time understanding how to think about and analyze the following problem: (I have done research, but I am not sure how to phrase my enquiries and my research seems to be almost helpful, I think I need a little nudge in the right direction)
There are n people in a room that contains a vending machine that dispenses k varieties of soda, k and n positive integers. Assume the machine is stocked with at least n cans of each variety. Every person buys one can of soda, dispensed at random. Show that when n is large, the probability that two people get the same variety of soda is $1 -e^\frac{-n^2}{2k}$.
This seems to be the equation for the birthday problem when you consider $1 - \bar{p}(x)$, with the approximation $e^x \approx 1 + x$. However, I don't see how this could be the case. I do not know what to make of "the machine is stocked with at least n cans of each variety", as this is incredibly vague. Do we assume there are only n of each variety? Do we assume there are an infinite number of cans of each variety? How do we handle the fact that there are k varieties of soda, whereas there is only 1 variety of birthday in the birthday problem? How could it end up being the same formula despite all of these differences?
When I follow the steps laid out in the wikipedia article on the birthday problem I end up getting something along the lines of (via the pigeonhole principle): $\bar{p}(x) = 1 - p(x) = 1 -(1- \frac{(k)_n}{(k)^n}) = \frac{(k)_n}{(k)^n}$ This in turn can be written: $\frac{(k)(k-1)...(k-n+1)}{k^n}$ $=\frac{(k)}{k}\frac{(k-1)}{k}...\frac{(k-n+1)}{k}$ $=1(1-\frac{1}{k})(1-\frac{2}{k})...(1-\frac{n-1}{k})$ This only holds if we assume there is a uniform probability of each person getting a given soda 1/k (like the pigeonhole principle). From here this becomes the same as the birthday problem, but why did we assume the probability is 1/k for each of them? Doesn't the probability change as sodas are dispensed, since the pool of targets and the overall pool of candidates both shrink?
I'm pretty sure this is wrong, but I do not know what to do. Can someone please explain to me how I should be thinking about this problem, and how I should approach it? Thank you, I really appreciate it.