Let A be a set of n DIFFERENT natural numbers in range [1, 2,...,n*log n]
The number of pairs from this set is n choose 2 (number of different ways to choose 2 objects out of n where repettion is not allowed and order doesn't matter) which equals n(n-1)/2
Each pair's value can be any number between 3 and 2n*logn - 1 Now I'm trying to find and prove an upper bound of the number of pairs that are equal
For example let A be 1,2,3,4 The pairs (as a sum of two different elements of A) are 3,4,5,5,6,7 In this example there are two equal pairs
My question is, How can I prove an upper bound of the number of equal pairs in an n size set (of different values by definition) in a range 1 through nlogn? Thank you!!
The upper bound is $\left \lfloor \frac n2\right \rfloor$ and does not depend on the upper limit of the numbers. The bound is achieved with the set $\{1,2,3,\ldots n\}$, though there are other possibilities with higher largest numbers. As all the numbers are different, the pairs must be disjoint. There can only be that many pairs. The common sum in this example is $n+1$.