Finding optimal price in a sale
Let's do the case $k = 2$. If the prices are $p_1 \geq p_2 \geq p_3 \geq p_4$ then there are three possible pairings $(p_1,p_2),(p_3,p_4);(p_1,p_3),(p_2,p_4);(p_1,p_4),(p_2,p_3)$ with cost $p_1+p_3;p_1+p_2;p_1+p_2$. So the first pairing is the best.

There are several ways to show that this pairing strategy is optimal in general. You might start by showing that given an arbitrary pairing in which $p_1$ is not matched with $p_2$, there is a way to modify it so that $p_1$ is matched with $p_2$, and the overall cost is lower. This leads to one proof.

Another idea is to show directly that the cost is always at least $p_1+p_3+\cdots$. For example, $p_1$ is always the largest in its pair, and $p_3$ is either the largest in its pair, or it is paired with $p_2&gt;p_3$ or with $p_1&gt;p_3$. You have to modify this argument so that you don't double count prices (for example, if $p_1$ is paired with $p_3$ and you follow the argument as stated, you will count $p_1$ twice).

There might be other ways to prove it, so if you have other ideas, by all means go ahead and try them out.