I am going through some of my notes from class (About Information Security) and I'm stuck understanding how my teacher got this result. The question is:

How many collisions would you expect to find in the following cases?

a) Your hash function generates a 12-bit output and you hash 1024 randomly selected messages.

b) Your hash function generates an n-bit output and you hash m randomly selected messages. 

The teacher's only answered a) like so:
We expect to find one collision every $2^{n/2}$ hashes. There are $2^{(n/2) * 2} = 2^n$ comparisons. Since the output is 12-bit the answer is $2^{10 * 2}/2 ^{12} = 2^{8} = 256$ collisions.

However I don't quite understand how he got this? I get that the expected number of collision after n hashes would be $2^{n/2}$. But the rest doesn't make sense to me. I mean if the output is 12 bits (4096 arrangements), why would we expect to get 256 collision after only hashing 1024 messages (1/4 of the possible outputs)?

Thanks in advance!

I am going through some of my notes from class (About Information Security) and I'm stuck understanding how my teacher got this result. The question is:

How many collisions would you expect to find in the following cases?

a) Your hash function generates a 12-bit output and you hash 1024 randomly selected messages.

b) Your hash function generates an n-bit output and you hash m randomly selected messages.

The teacher's only answered a) like so:

We expect to find one collision every $2^{n/2}$ hashes. There are $2^{(n/2) * 2} = 2^n$ comparisons. Since the output is 12-bit the answer is $2^{10 * 2}/2 ^{12} = 2^{8} = 256$ collisions.

However I don't quite understand how he got this?

I get that the expected number of collision after n hashes would be $2^{n/2}$. But the rest doesn't make sense to me. I mean if the output is 12 bits (4096 arrangements), why would we expect to get 256 collision after only hashing 1024 messages (1/4 of the possible outputs)?