# Probability of getting the sum of two numbers selected from two ranges as odd.

Consider two integers N and M.
One number is selected from a range of 1 to N.
Another number is selected from a range of 1 to M.
What is the probability that the sum of the two numbers is odd?

Note: I figured out that, whenever either N or M is even, the probability will be 1/2. But what if both or any one of them is odd.

-

As you correctly pointed out, if either $N$ or $M$ is even, then the probability is $1/2$, by a symmetry argument. Suppose both $M,N$ are odd. Then there are two cases:

1. We pick exactly $M$ from $[1,M]$
2. We pick anything else from $[1,M]$.

In case 1, the probability that the sum is odd is $\frac{(N-1)/2}{N}= \frac{N-1}{2N}$, slightly less than half, because slightly less than half of the numbers in $[1,N]$ are even. In case 2, the probability that the sum is odd is 1/2 again, because this is equivalent to picking from $[1,M-1]$. Hence the combined answer is

$$\frac{1}{M}\frac{N-1}{2N} + \frac{M-1}{M}\frac{1}{2}=\frac{MN-1}{2MN}$$

A slightly more compact way to write the answer, which handles the cases of $M,N$ even as well, is $$\left \lfloor \frac{MN}{2}\right\rfloor \frac{1}{MN}$$ where $\lfloor\cdot\rfloor$ denotes the floor function.

-

$A \equiv \text{Number selected from the range$1\ldots N$is odd}\\ B \equiv \text{Number selected from the range$1\ldots M$is odd}$

Now $P(A) = \frac 1 N\left\lceil\frac N 2\right\rceil,\ P(\bar{A}) = \frac{1}{N}\left\lfloor \frac N 2 \right\rfloor$
and $P(B) = \frac 1 M\left\lceil\frac M 2\right\rceil,\ P(\bar{B}) = \frac{1}{M}\left\lfloor \frac M 2 \right\rfloor$

Then the probability that the sum of the two numbers is odd is

$P(A)P(\bar{B}) + P(\bar{A})P(B)\\ = \dfrac 1 N\left\lceil\dfrac N 2\right\rceil \dfrac{1}{M}\left\lfloor \dfrac M 2 \right\rfloor + \dfrac{1}{N}\left\lfloor \dfrac N 2 \right\rfloor \dfrac 1 M \left\lceil\dfrac M 2\right\rceil\\ = \dfrac{1}{MN}\left( \left\lceil\dfrac N 2\right\rceil \left\lfloor \dfrac M 2 \right\rfloor + \left\lfloor \dfrac N 2 \right\rfloor \left\lceil\dfrac M 2\right\rceil \right)$

-

Odds and evens form a checkerboard.

Write the numbers from 1 to M down one side, and the numbers from 1 to $N$ along the top. Put $i+j$ in column $i$, row $j$. Colour $i+j$ red if even, blue if it is odd.

You can cover the checkerboard with dominos. Each domino covers a blue and a red, and there will be one square left over because there is an odd number of squares.

All four corners are even : 1+1, 1+N, 1+M, M+N - so it makes sense that the extra square is even.

There are $(NM+1)/2$ even squares and $(NM-1)/2$ odd squares, making a total of $NM$ squares.

-