probability
What are the odds that a person in one group of $105$ people, has the same last four digits of their cell phone number as another person in a different group of $105$ people?
I understand how to do this with only one group (the birthday paradox), but my intuition tells me that having two groups changes the problem.
After thinking for a while, it seems to me that part of the problem you're actually struggling with is how to state and specify the "real life" problem that you want to solve, rather than actually solving it. One way to state and solve the problem is addressed below, here I'd like to discuss about other ways to specify the problem.
In short, you may want to have a look at Markov chains, or even hidden Markov chains. One way to see Markov chains, is that you have a system that can evolve between certain states, with a certain probability. Here for example, person $A$ could be your system, and its state could be which city $A$ is currently in. You can make things non uniform by specifying the probabilities with which the system can transition from one state to another. Want to include $B$? Make the system pairs of cities. Don't want to make the decision of $A$ and $B$ independent? That's already built-in with the probability to transition from one state to another. Want to have time play a role? One transition can be equivalent to one time unit, and a state can transition into itself to simulate that $A$ and $B$ do not move. Want to simulate a 2-day vacation to another city (staying 2 days somewhere, coming back to hometown)? Make a special state that can only transition back to the state it came from...
I think you get the idea. To conclude, the approach below could be modeled by a Markov chain, but it would probably be very annoying. The more "natural" thing to do with Markov chain would be to have $N$ and $M$ as random variables, enforcing them to be constant would probably be annoying? (Not sure, I haven't done any Markov chain in ages.)
You need to specify in some way what the probabilities are when $A$ and $B$ move around... For instance for $A$, is $N$ fixed or a random variable? Assuming $N$ is fixed, $A$ will visit $N+1$ points, let $T_i$ be the number of days $A$ stay at the $i$-th point. Can the $i$-th point and the $(i+1)$-th point be the same? I'll assume that they must be distinct. I'll also assume that $T_i\ge 1$ for every $i$, and that every $T_i$ is an integer.
Just looking at the $T_i$, there is $364\choose N$ possible choices of them. This corresponds to all the ways $A$ can choose to move around, without specifying where.
When looking at the locations, $A$ can choose between $P-1$ destinations, so if we disregard the "when", we have a choice between $(P-1)^N$ trajectories. I ignored the starting point, but if this is also a variable make that $(P-1)^{N+1}$.
If you put those together, there are ${364\choose N}(P-1)^N$ ways for $A$ to move around in the span of one year. Are all of these ways equally probable? Or is there some specific process for $A$ to choose when and where he moves? Unless you specify this information, it will be difficult to solve your problem.
Ps: if $A$ and $B$ start on the same point, they will obviously be together on the same point on day 1... you may want to revise your problem statement.
Nick G was faster than me, but I want to add a few remarks to his approach (read his answer first).
When $A$ and $B$ move simultaneously, there are indeed $(p-1)^2$ possible pairs of destination, but only $p-2$ outcomes where $A$ and $B$ meet. Indeed $A$ can move to $p-1$ points, but that number includes the point where $B$ is currently at. Because they cannot meet there, only $p-2$ cities (and outcomes) remain. So the probability that they do not meet right after they both move is $$\frac{(p-1)^2-(p-2)}{(p-1)^2}$$ When $X=k$, the probability they do not meet during the course of one year then becomes $$ P(\text{$A$ and $B$ do not meet}\mid X=k)= \left(\frac{p-2}{p-1}\right)^{N+M-2X}\times \left(\frac{(p-1)^2-(p-2)}{(p-1)^2}\right)^X $$
The last remaining problem is how to determine $X$. Let $T^A_i$ be the number of days $A$ stays in the $i$-th city he visits, likewise for $T^B_i$. Given the values of $T^A_i$ and $T^B_i$ it is possible to compute $X$. You didn't provide any information on the probability of having one set of $T^A_i$, $T^B_i$ over another, so I'll just assume uniform distribution. Also dealing with the durations of the stay is annoying, so instead let $U^A_i$ be the night when $A$ travels from the $i$-th city to the $(i+1)$-th city. The sequence $(U^A_i)_{1\le i\le N}$ is strictly increasing and has integer values between $1$ and $364$ (inclusive). We have likewise a sequence $(U^B_i)_{1\le i\le M}$ for $B$.
Without loss of generality assume $N\le M$. For an integer $k$, $0\le k\le N$, we want to compute $P(X=k)$, the probability that $X$ is equal to $k$. Because we assume uniform distribution, it is the number of ways to draw both $(U^A_i)$ and $(U^B_i)$ such that they share exactly $k$ identical night values divided by the total number of ways to draw $(U^A_i)$ and $(U^B_i)$. There are $364\choose k$ ways to choose $k$ distinct nights on which $A$ and $B$ both move. Following this, $A$ still move $N-k$ times on the remaining $364-k$ nights, while $B$ move $M-k$ times. However, those $(N-k)+(M-k)$ nights must be distinct, there are $364-k\choose N+M-2k$ ways to chose the nights they move on, and ${N+M-2k\choose N-k} = {N+M-2k\choose M-k}$ ways to decide whether $A$ or $B$ is the one moving during those nights.
In the end there are $$ {364\choose k}\times{364-k\choose N+M-2k}\times{N+M-2k\choose N-k} =\frac{364!}{k!\,(364-N-M+k)!\,(N-k)!\,(M-k)!} $$ different ways to draw the nights $(U^A_i)$ and $(U_i^B)$ so that $A$ and $B$ move the same night exactly $k$ times. In total, there are ${364\choose N}\times{364\choose M}$ ways to draw the nights (without constraints). This means we can compute $P(X=k)$.
To conclude, $$ P(\text{$A$ and $B$ do not meet}) =\sum_{k=0}^N P(X=k)\times P(\text{$A$ and $B$ do not meet}\mid X=k) $$ and you want to take $1$ minus the above to answer your problem. I have no clue whether there is a nice simplification of the various formula, but at least a computer can do the work for you.
Also note that the assumption in this model are not very "realistic". As TMM pointed out, most people should have some kind of pattern when travelling. Uniform distribution on the $(U^A_i)$ and $(U^B_i)$ also means the below situations have the same likelihood:
Depending on the circumstances, those may not be desirable properties...
As far as I can tell, your methods do not work and cannot be salvaged.
This is a hard problem that cannot be solved by conventional means. To find the probability that at least three people have a common birthday, let us instead compute the probability that no three people share a birthday. This is equal to $$ \frac{n^{365}}{365^n}.\tag 1 $$ Here, $[x^n]f(x)$ is the coefficient of $x^n$ in the polynomial $f(x)$. You want one minus the above. Another way to write this is $$ \sum_{a_1,a_2,\dots,a_{365}}\frac1{365^n}\frac{n!}{a_1!a_2!\cdots a_{365}!}.\tag 2 $$ where the sum ranges over all vectors $(a_1,a_2,\dots,a_{365})$ of integers between $0$ and $2$ whose sum is $n$. This works because each vector specifies a valid distribution of birthdays where no birthday repeats three times or more, and the multinomial coefficient gives the number of ordered selections of birthdays which have that distribution, and each is then multiplied by the probability $(1/365)^n$ of that ordered selection occurring. You can check that when you expand out $(1)$ and collect the coefficient of $x^{n}$, you get exactly $(2)$.
If you are okay with an approximate result, the expected number of triplets of people who share a common birthday is $\lambda =\binom{n}{3}\cdot \frac1{365}^2$, and the number of triplets with a common birthday is approximately Poisson with parameter $\lambda$. Therefore, the probability some triplet share a birthday is approximately $$ 1-e^{-\binom{n}3/365^2}. $$
Best Answer
It doesn't change things much. Each pair of people has $1$ in $10^4$ chance of sharing the last four digits assuming the digits are randomly distributed. How many pairs of people are there? As it is a bit larger than $10^4$ it is reasonably likely (about $2/3$) that there will be a match.