The birthday problem isn't applicable here, because you're trying to match a specific combination rather than looking for any matching pair. So the average number of attempts needed is indeed 4096/2.
This is the same as the difference between a preimage (specific input) attack and a collision (any pair of inputs) attack on a hash algorithm[1].