EDIT 2
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.)
Original answer
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.
EDIT 1
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:
- $A$ visits one city per day $N$ days in a row then do not move the rest of the year
- $A$ stays $365/(N+1)$ days in each city he visits
- anything in between
- and let's not forget it's the same for $B$
- the model also assumes that $(U^A_i)$ and $(U^B_i)$ are independant by the way
Depending on the circumstances, those may not be desirable properties...
Best Answer
For $i=2,3,\dots,100$ let $X_i$ take value $1$ if number $i$ is chosen by both and let $X_i$ take value $0$ otherwise.
Then the number of numbers chosen by both is: $$X=\sum_{i=2}^{100}X_i$$
Now find $\mathbb EX$ by applying linearity of expectation and symmetry.