3
$\begingroup$

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$??

$\endgroup$
  • $\begingroup$ What is E and D? $\endgroup$ – TZakrevskiy Jul 8 '14 at 15:30
  • $\begingroup$ sorry i am unable to describe in statement.E=number of pairs (i,j) where i<j and Ai+Aj is even. Similarly O=number of pairs (i,j) where i<j and Ai+Aj is odd. D=abs(E-O). $\endgroup$ – savvi singh Jul 8 '14 at 15:31
  • $\begingroup$ i don't know why it is not being displayed in the problem?? sorry for the inconvenience. $\endgroup$ – savvi singh Jul 8 '14 at 15:34
  • $\begingroup$ I'd try to study the sequences $A=\{1,\ldots n\}$, find your E O D, and then generalize. $\endgroup$ – TZakrevskiy Jul 8 '14 at 15:37
  • 2
    $\begingroup$ Without loss you may assume that the sequence of integers consists entirely of $0$ and $1$. $\endgroup$ – vadim123 Jul 8 '14 at 15:54
2
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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}$ $\endgroup$ – Empy2 Jul 8 '14 at 16:34
1
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ for n=4 answer will be 0 so i dont know if this formula is valid!! $\endgroup$ – savvi singh Jul 8 '14 at 16:40
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Jul 8 '14 at 16:40
  • $\begingroup$ 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. $\endgroup$ – NoName Jul 8 '14 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.