# Greedy algorithm-maximal minimum average of n pairs

Lets assume $$2n$$ gifts such that each gift $$i$$ has price $$a_i$$

The goal is to find a partition of the gifts into $$n$$ pairs such that each pair $$P_i=\left(a_{i_{0}},a_{i_{1}}\right)$$ has maximal minimum average IE $$\min_{i\le n}\left\{ \frac{a_{i_{0}}+a_{i_{1}}}{2}\right\}$$ is maximal.

How to get a contradiction inside the induction proof?

So the algorithm I guessed(with a lot of python examples):

1. Initiate a pair array P of size n
2. Sort the array of prices A in ascending order.
3. for i<n:
P.insert(A[i],A[2n-1-i])

I struggle to prove its correctness with induction. for the base case I assume that since $$Sol_0=\emptyset$$ then $$Sol_0\subseteq Opt$$ for some optimal solution. then assuming for $$i that each iteration is good,IE $$Sol_i\subseteq Opt$$ for some opt.

now the kth iteration, IE $$Sol_k=Sol_{k-1}\cup (a[k],a[2n-1-k])\nsubseteq Opt$$

This means that the pair we just added is not part of any optimal solution, so there are some $$\left(a[r],a[w]\right)\in\widehat{Opt}$$ such that $$\frac{a[k]+a[2n-1-k]}{2}<\frac{a[r]+a[w]}{2}$$

$$(a[r],a[w])$$ are the minimum average of some $$Opt$$

How do I get a contradiction here?

As for the $$Sol_{n}\supseteq Opt$$ I can say that since we had $$n$$ iterations and at each iteration we added a single pair, after $$n$$ iterations we have $$\left|Opt\right|=\left|Sol\right|=n$$ therefore there is a mutual inclusion.

• What is your question? Commented Dec 28, 2022 at 16:03
• how do I get a contradiction that the k'th iteration doesn't break the $Sol_{k}\subseteq Opt$ property? IE that $\frac{a[k]+a[2n-1-k]}{2}<\frac{a[r]+a[w]}{2}$ can not happen Commented Dec 28, 2022 at 16:09
• Don't add precisions in the comments, edit your post so that the question is clearly defined. Commented Dec 28, 2022 at 16:12

Here is the induction step that shows $$Sol_k\subset$$ some optimal solution.

By induction assumption, there is an optimal solution $$O_k$$ that contains the same pairs as $$Sol_k$$ except possibly the last pair, $$(a[k],a[2n-1-k])$$.

• If $$(a[k],a[2n-1-k])\in O_k$$, we are done.

• Otherwise, $$(a[k],a[2n-1-k])\notin O_k$$.
Let $$(a[k],a[j])$$ and $$(a[\ell], a[2n-1-k])$$ be the pairs in $$O_k$$ that contain $$a[k]$$ and $$a[2n-1-k]$$ respectively.

Let $$O_k'$$ be the solution that is the same as $$O_k$$ except that pairs $$(a[k],a[j])$$, $$(a[\ell], a[2n-1-k])$$ are replaced with $$(a[k],a[2n-1-k])$$, $$(a[\ell],a[j])$$.

Since $$a[k]$$ and $$a[2n-1-k]$$ are the minimum element and the maximum element in the remaining elements respectively, we have $$a[k] \le a[\ell]$$ and $$a[j]\le a[2n-1-k]$$. So $$\frac{a[k]+a[j]}2 \le \min(\frac{a[k]+a[2n-1-k]}2, \frac{a[\ell]+a[j]}2),$$ which implies the minimum pair average of $$O_k$$ is not greater than that of $$O_k'$$. Since $$O_k$$ is an optimal solution, so must be $$O_k'$$.

Since $$O_k'$$ contains the pair $$(a[k],a[2n-1-k])$$, we are done.

If you have to use proof by contradiction, then the existence of $$O_k'$$ gives rise to a contradiction. This will be an example when proof by contradiction only brings unnecessary clutter.

Let $$P = \{P_0, …, P_{n-1}\}$$ be the set of pairs returned by your algorithm and $$P' = \{P_0', …, P_{n-1}'\}$$ be an other set of pairs.

Denote $$f(P) = \min\limits_{i=1}^n(a_{i,0} + a_{i,1})$$ where $$P_i = \{a_{i,0}, a_{i,1}\} = \{a_i, a_{2n-i-1}\}$$ (I got rid of the $$\frac{\cdot}2$$ part, because it does not change the result) and let $$m\in \{0, …, n-1\}$$ be an index such that $$f(P) = a_m + a_{2n-m-1}$$.

Let $$i\in \{0, …, 2n - 1\}$$ be the index of the element paired with $$a_m$$ in $$P'$$. Let us distinguish:

• if $$i \leqslant 2n-m-1$$, then $$f(P') \leqslant a_m + a_i \leqslant a_m + a_{2n-m-1} = f(P)$$;
• if $$2n-m-1 < i$$, then by the pigeonhole principle, there exist two indices $$j < m$$ and $$k \leqslant 2n-m-1$$ such that $$a_j$$ and $$a_k$$ are paired together in $$P'$$. If that's the case, $$f(P') \leqslant a_j + a_k \leqslant a_m + a_{2n-m-1} = f(P)$$.

That means that $$P$$ is optimal.