Something to do with the pigeons

$1 + 1001=1002$ , but $1001\not<1000$ . So there's no pair for $1$ . Also, $501+501=1002$ , but $501$ can't be paired with itself, so there's no pair for $501$ .

That leaves 249 pairs of odd numbers between $1$ and $1000$ (inclusive) whose pair-wise sum is $1002$ . If we choose only one element of each of these pairs, we don't have any pairs summing to $1002$ .

So, 2 unpairable elements, plus one element of each of 249 pairs gives us a total of 251 elements we can choose without having a valid pair. As soon as we choose the 252nd, however, we must have the pair we needed. Thus the answer is 252.