Given a class with n boys and n girls, in which the girls recieved the grades p1,...,pn, and the boys recieved the grades s1,...,sn in an exam, find a pairing of girl-boy in a way that minimizes the average difference between the grades in the couples. For example, if p1=30, p2=60, s1=50, s2=90, we should pair girl #1 with boy #1 (20 points difference) and girl #2 with boy #2 (30 points difference), and we will get a minimal average difference of (30+20)/2 = 25.
Prove that the following algorithm is optimal: Pair the girl with the lowest grade to the boy with the lowest grade. Then pair the girl with the second lowest grade to the boy with the second lowest grade, etc.
In my solution, I tried using the greedy choice property (showing that there exist an optimal solution where a certain element is in the solution, and then using induction to prove that all elements are in the optimal solution) :
Let A1<=...<=An be the girl's grades sorted, and B1<=...<=Bn be the boys' grades sorted.
Claim - There exists an optimal solution which includes the pair A1-B1 (the boy with the lowest grade paired to the girl with the lowest grade).
Proof - Assume by contradiction that the statement is false. Therefore, no optimal solution includes A1-B1 as a pair. Assume A1-Bi (i>1) and B1-Aj (j>1) are pairs in the solution. We know that A1<=Aj and B1<=Bi. How do I continue from here ?
Thanks in advance.
OK, I found something based on some geometric observations.
Say you have only 4 numbers for now: a1 <= a2 and b1 <= b2 (0).
|a1-b1| + |a2-b2| <= |a1-b2| + |a2-b1| (1)
In this case, we want to check if (1) is true.
I rewrite (1) based on obvious equivalence relations:
( |a1-b1| + |a2-b2| ) ^ 2 <= ( |a1-b2| + |a2-b1| ) ^ 2 (2)
-2 * a1 * b1 -2 * a2 * b2 <= -2 * a1 * b2 -2 * a2 * b1 (3)
Should I explain how I got from (2) to (3)? I guess not.
Then we get:
a1*b1 + a2*b2 >= a1*b2 + a2*b1 (4)
a1(b1-b2) >= a2*(b1-b2) (5)
a1(b1-b2) - a2*(b1-b2) >=0 (6)
a1(b1-b2) + a2*(b2-b1) >=0 (7)
But (5) is obviously true because b1-b2 <= 0 and a1 <= a2 (see (0)).
This is a rigorous proof for N=2.
My gut tells me this should be generalized somehow
pretty easily for the case of N. Maybe we can try an
induction from here (having seen these (1),(2),(3), etc.).
Geometrically, you can imagine that Ai and Bj as points
on two parallel numeric linex (axis A, axis B). One
pairing configuration is defined by connecting the paired
points from A and B with segments. Your statement basically
says that the optimal pairing is the one in which no two
segments (Ai,Bj) cross each other (they may overlap with
each other /in the optimal solution/ but may not cross each other).
Right?
Now, if we do the same thing (which I did for N=2),
for any N, you will get this question: "Is
a1(b1-bi1) + a2(b2-bi2) + a3(b3-bi3) + ... + aN*(bN-biN) >= 0 (4')
true", where i1,i2,...,iN is any permutation of (1,2,...,N),
and given that a[i] <= a[i+1] and b[i] <= b[i+1] for each i.
Now, here we do induction on N to prove (4').
Suppose (4') is true for N and for all K such that K<N.
Add two more numbers to A and B. Say aN+1 and bN+1.
Let's say they get inserted at positions s1 (in A) and s2 (in B)
in their respective SORTED sequences (A, B). Let's say s1 <= s2
(the reverse case is analogical). So now as1 = aN+1 and bs2 = bN+1,
but s1 and s2 are their real indices in the NEW sorted sequences.
But now proving (4') for N+1 turns into a matter of
proving it for N=2 because only these terms (from (4'))
matter when we do the step from N to N+1.
as1 * (bs1 - bs2) + as2 * (bs2 - bs1) >= 0 (7')
and as we saw this is true for N=2 (see (7) above).
For the other N-1 terms (which remain from (4')), we get that the
inequality (4') is true due to the assumption from the induction (that it is
true for N-1). Thus from the truth for 2 and N-1 we got the truth for N+1.
Hope you understand how I did it. On paper it is easier
to write it, hard to write it here.
So this should be your rigorous proof for the N case.