How to figure out the size of the output of a cryptographic checksum function
The question states that the probability of finding a collision is $2^{-64}$. This is incorrect. The probability depends on the number of available messages, as we will see below.

If you take two random messages, the probability of them having the same $m$-bit hash is $2^{-m}$. So you're going to have to try around $2^{m}$ pairs before you find a collision.

But you can do this without generating $2^m$ messages.

Consider this:

With $n$ different messages, you can generate $C(n,2)$ different pairs of messages

$C(n,2) = \dfrac{n!}{2(n-2)!}$

$= \dfrac{n(n-1)(n-2)!}{2(n-2)!}$

$=\dfrac{n(n-1)}{2}$

$=\dfrac{n^2 -n}{2}$

So with $n$ different messages, we can generate $\dfrac{n^2 - n}{2}$ unique pairs.

Now we need to figure out how many messages are required to have a good probability ($\geq$50%) of finding two colliding messages.

$\dfrac{\frac{n^2 - n}{2}}{2^m} \geq 0.5$

$\dfrac{n^2 - n}{2^{m+1}} \geq 0.5$

$n^2 - n \geq 2^m$

So it turns out we need just over $2^{m/2}$ messages. This is usually simplified to exactly $2^{m/2}$ since we're dealing with such large numbers that the difference is negligible. There are other ways of calculating it, but they all work out to the same approximation (see Birthday Problem, Birthday Attack).