2
$\begingroup$

Now we have some $n$ of the number from the set $\{1,2,...,2n\}$ colored red and the rest of them are colored blue. Say $a_1<a_2<...<a_n$ are red and $b_1>b_2>...>b_n$ are blue. Prove that the value of the expression $$E=|a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|$$ does not depend on the coloring.


All I can do is to calculate this $E$ if we take $a_i=i$ and $b_i = 2n+1-i$ for all $i\leq n$. In this case we get $$E = (n+1)+(n+2)+...+(2n) -1-2-...-n = n+n+...n = n^2$$ Clearly it wants us to prove that $E$ is invariant for such colorings. Does any one has any idea how to prove it. Strong assumption is that it should be done with induction.

$\endgroup$
0
$\begingroup$

Ahh, this is what I found right now. For every $k$ we have $$a_{k+1}-a_k >0 >b_{k+1}-b_k$$ so $$ a_{k+1}-b_{k+1}> a_k-b_k$$ This should kill the problem...?

$\endgroup$
  • $\begingroup$ This is a comment, not a solution! $\endgroup$ – Ehsan M. Kermani Nov 3 '17 at 20:35
  • $\begingroup$ Is it, perhaps some comment is more than pure solution. $\endgroup$ – Aqua Nov 3 '17 at 20:39
0
$\begingroup$

This is not a complete proof but I think something like this should work!

Let's prove a more general statement for any $2n$ consecutive integers $E$ doesn't depend on coloring/partitioning. Proceed by induction on $n.$ The bases cases are trivial to check. Assume that the assert holds for $\leq n-1$ no matter if we choose all $a_i$s first or $b_i$s first.

Now note that, we have either $a_1=1$ or $b_n=1.$ Also either $b_1=2n$ or $a_n=2n$

Case 1. $a_1=1$ and $b_1=2n,$ then $E$ is $(2n-1) + \sum (...)$ so by hypothesis $E$ doesn't depend on the partition.

Case 2. $a_1=1$ and $a_n=2n,$ then $E$ is $(b_1 - 1 ) + \sum (...) + (2n - b_n) = (b_1 - b_n) + (2n-1) + \sum (...).$ By hypothesis, it only remains to show that $b_1 - b_n$ doesn't depend on coloring as well. We can also assume that we have selected $a_i$s first, then $b_i$ were determined uniquely if that help!

Other two cases are similar as well.

$\endgroup$
  • $\begingroup$ I do understand case 1 but i don't follow the case 2. Could you elaborate it? $\endgroup$ – Aqua Nov 5 '17 at 8:17
  • $\begingroup$ @JohnWatson I rephrased case 2, if that helps. $\endgroup$ – Ehsan M. Kermani Nov 5 '17 at 21:19

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.