Length of a Challenge in Challenge and Response Protocol
If your challenge is random bits, the security level is about $2^{bitlen}$, but since you are using it in challenge response you might want to avoid collisions as you said, especially if $O(2^{bitlen/2})$ storage is feasible, so you should set the length about twice required security level. But since you will likely be using pseudo-random numbers, your actual entropy won't be higher than its seed. For example, if the seed is just 64 bits, even if you produce 1K long sequence, we can expect collision in about four billion challenges since PRN generators produce a sequence deterministic to the seed which an attacker who is recording can replay using someone else's signature to complete authentication. But $k$ bit long seed from some source of entropy does not necessarily mean $k$ bits of entropy if the source of entropy used for seeding is not very good. And the PRNG must be cryptographically strong as well. In a nutshell, assuming cryptographically secure PRNG, you can expect repetition as you said in about half the actual bit entropy of the seed.