This is an expansion of this presentation.
Because the state graph consists of two disconnected components of equal size.
Without loss of generality we can assume that the target state is $1\;2\;3\;...\;15\;\Box$.
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 *
Given a state $S$ a permutation inversion is a tile $T_i$ that is placed after $T_j$ but $i < j$; this happens when (a) $T_i$ is in the same row of $T_j$, but on its right, or (b) $T_i$ is in a lower row:
. . . . . . . .
3 . . 1 . 7 . .
. . . . . 5 . .
. . . . . . . .
(a) (b)
We define $N_j$ as the number of tiles $T_i$, $i < j$ that appears after $T_j$.
For example, in the state:
1 2 3 4
5 10 7 8
9 6 11 12
13 14 15 *
we have that after $T_{7}$ there is one tile ($T_6$) that should be before it, so $N_7=1$; after $T_{10}$ there are four tiles ($T_7, T_8, T_9, T_6$) that should be before it, so $N_{10}=4$.
Let $N$ be the sum of all $N_i$ and the row number of the empty tile $T_{\Box}$
$$N = \sum_{i=1}^{15} N_i + row(T_{\Box})$$
In the example above we have: $N = N_7 + N_8 + N_9 + N_{10} + row(T_{\Box}) = 1 + 1 +1 + 4 + 4=11$
We can notice that when the empty tile is moved horizontally $N$ doesn't change; if we move the empty tile vertically $N$ changes by an even quantity.
For example:
. . . . . . . .
. . 2 3 . . * 3
4 5 * . 4 5 2 .
. . . . . . . .
$N' = N + 3 \mbox{ (2 is placed after 3,4,5)} - 1 \mbox{ (empty tile is moved up)} = N + 2$
. . . . . . . .
. . * 4 . . 3 4
2 5 3 . 2 5 * .
. . . . . . . .
$N' = N + 1 \mbox{ (2 is placed after 3)} - 2 \mbox{ (4,5 are placed after 3)} + 1 \mbox{ (empty tile is moved down)} = N$
So $N \bmod 2$ is invariant under any legal move of the empty tile.
We can conclude that the state space is split in two disconnected halves, one having $N \bmod = 0$ and the other having $N \mod 2 = 1$.
For example the following two states are not connected:
1 2 3 4 1 2 3 4
5 6 7 8 5 6 7 8
9 10 11 12 9 10 11 12
13 14 15 * 13 15 14 *
N = 4 N = 5