2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ What is your question? $\endgroup$
    – Nathaniel
    Commented Dec 28, 2022 at 16:03
  • $\begingroup$ 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 $\endgroup$ Commented Dec 28, 2022 at 16:09
  • 3
    $\begingroup$ Don't add precisions in the comments, edit your post so that the question is clearly defined. $\endgroup$
    – Nathaniel
    Commented Dec 28, 2022 at 16:12

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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