3

Suppose we have a sequence of $n$ integers not necessarily distinct. Let's define,

$E$ = Number of pairs $(i, j)$ such that $i<j$ and $A_i+A_j$ is even.

$O$ = Number of pairs $(i, j)$ such that $i<j$ and $A_i+A_j$ is odd.

$D = \lvert E-O \rvert$.

We need to find minimum value of $D$??

Example: $n=5$, min value of $D$ will be 2. $A=\{1,2,3,4,5\}$.

Can we find a relation for value of $n$??

NoName
  • 2,975
savvi singh
  • 293

3 Answers3

2

If there are $o$ odd numbers and $e$ even numbers, then $E=e(e-1)/2+o(o-1)/2$, and $O=eo$.

We want to minimize $$2D = |e^2-e+o^2-o-2eo|\\ =|(n-o)^2-(n-o)+o^2-o-2(n-o)o|\\ =|n^2-2no+o^2-n+o^2-2no+2o^2|\\ =|n^2-4no+4o^2-n| $$

This will be when $o=(4n\pm \sqrt{16n})/8=n/2\pm \sqrt{n}/2$

Empy2
  • 50,853
  • The worst case will be when $n/2+\sqrt{n}/2$ is a half-integer, in which case $(n-2o)^2-n=(\sqrt{n}-1)^2-n=1-2\sqrt{n}$ – Empy2 Jul 08 '14 at 16:34
1

If you have $k$ odd numbers and $m$ even numbers in your set $A$, there will be $km$ pairs with an odd sum and $\frac 12k(k-1)+\frac 12m(m-1)$ pairs with even sum. As $k+m=n$, the number of pairs with even sum will be $\frac 12k(k-1)+\frac 12(n-k)(n-k-1)=\frac12 (k^2-k+n^2-2nk+k^2-n+k)=\frac 12(n^2-2nk+2k^2-n)$ compared with the $k(n-k)=nk-k^2$ odd pairs The difference between these is $\frac 12(n^2-2nk+2k^2-n)-nk+k^2=\frac 12(n^2-4nk+4k^2-n)$

This will be zero when $n$ is a square, call it $p^2$ and $k=\frac 12 p(p+1), m=\frac 12p(p-1)$ (or the reverse). The difference becomes $\frac 12(p^4-2p^2p(p+1)+p^2(p+1)^2-p^2)=0$

Ross Millikan
  • 374,822
0

I don't believe the example provided is relevant. "$n$ integers not necessarily distinct" means that the same integer may appear more than once, so all we know is that our set of integers $A$ has cardinality $n$ but we can't don't know exactly which integers are in $A$, except that they fit into some sort of sequence.

If we're assuming $A = \{1, 2, \ldots, n\}$, however, we can work with that.

Let's start with $n$ being even. There are $n-1$ sums that use $1$, and the sums alternate being even and odd. Since the first and last are odd, there is one more odd sum than there are even sums.

Next, there are $n-2$ remaining sums that use $2$. This sequence of sums alternates odd and even like before, and it starts odd $(2 + 3)$ and ends even $(2 + n)$ so there are exactly as many even sums as there are odd sums.

Continuing this argument, we find that every odd number in the sequence $\{1, 2, \ldots, n\}$ produces exactly one more odd sum than even sum, and that every even number produces the same amount of both. Therefore there are $\frac{n}{2}$ more odd sums than even sums.

Now consider when $n$ is odd. Using the same method, we find now that the odd numbers in the sequence $\{1, 2, \ldots, n\}$ yield the same number of sums belonging to $O$ and $E$, while the even numbers yield one more sum belonging to $O$. Therefore there are $\frac{n-1}{2}$ more odd sums than even sums, since there are $n-1$ even numbers in our sequence.

Thus the answer (to the problem I extrapolated from your problem) is $\lfloor \frac{n}{2} \rfloor$.

NoName
  • 2,975
  • for n=4 answer will be 0 so i dont know if this formula is valid!! – savvi singh Jul 08 '14 at 16:40
  • this is not correct. Counting the sums with $1$, there will be one more odd sum only when $n$ is even. If $n$ is odd, there will be the same number of odd and even sums. – Ross Millikan Jul 08 '14 at 16:40
  • Wait, isn't that what I said? If $n$ is even, then every odd number in the sequence (1 included) yields one more odd sum, and the even numbers yield the same amount of odd and even sums. If $n$ is odd, the reverse is true, yes? If $n = 4$ then there are two more odd sums than even, which can easily be verified by hand. – NoName Jul 08 '14 at 16:50