Find the minimum and maximum in 3n/2 - 2 comparisons, and the adversary that proves it

A courier depot has $n$ parcels, numbered $0$ to $n - 1$ , and a balance scale. One weighing puts two parcels on the scale and shows which is lighter. No two parcels weigh the same. The depot needs the lightest parcel and the heaviest parcel, and every weighing takes time.

Six parcels after two weighings: the ledger of who has won and who has lost.

In code, a weighing is a call lighter(i, j), which returns True when parcel i is lighter than parcel j.

Finding the heaviest alone takes $n - 1$ weighings: keep the heavier parcel of each weighing and bring on the next one. Then finding the lightest among the other $n - 1$ parcels takes $n - 2$ more, $2 n - 3$ in all. Can you do better? And how would you prove that nobody can do better than you?

Grading

Your method is weighed against an adversary. The adversary decides the weights as you go, so that your weighings tell you as little as possible. It is also weighed against several fixed orders, for every $n$ from 1 to 40. Your answer must be proved by your weighings: if they leave any other parcel able to be lighter (or heavier), the answer is wrong, even if you guessed right.
Your adversary is played against several weighing strategies, including ones that bet on a particular order. Its answers must fit some ordering of the parcels.
No timing decides a grade.

Background: Lower Bounds and Adversaries.

The key idea: count what is still unproved

To prove which parcel is lightest, every other parcel must have lost a weighing: been the lighter one at least once. Otherwise it could still be the lightest. To prove which is heaviest, every other parcel must have won one. That is $2 (n - 1)$ facts to establish. Call each one a unit.

A weighing between two parcels that have never been weighed settles two units: one loses, one wins. Any other weighing can be answered so that it settles at most one. So a good method weighs fresh parcels in pairs first: $⌊ n / 2 ⌋$ weighings, two units each. Then the lighter of each pair competes for lightest and the heavier for heaviest. For even $n$ that is $n / 2 + 2 (n / 2 - 1) = 3 n / 2 - 2$ weighings; for odd $n$ , start with one parcel as both candidates and get $⌈ 3 n / 2 ⌉ - 2$ . For 6 parcels, 7.

The adversary, which is part C

Give every parcel a state: new, won only, lost only, or both. Answer each weighing to settle as few units as possible. Two new parcels: one lighter, one heavier (two units, unavoidable). A new parcel against one that has only won: the new one is lighter (one unit). A new parcel against one that has only lost: the new one is heavier (one unit). Two that have only won: one of them becomes "both" (one unit). Two that have only lost: likewise. Anything else is answered by what earlier answers already force, or settles nothing.

To stay consistent, decide weights as you go: when a parcel must be heavier than everything so far, give it a new largest weight; when it must be lighter, a new smallest one. A parcel that has only won only ever gets heavier, and one that has only lost only ever gets lighter, so no earlier answer is contradicted.

Now count. Only weighings between two new parcels settle two units, and there are at most $⌊ n / 2 ⌋$ of them. The other $2 (n - 1) - 2 ⌊ n / 2 ⌋$ units cost one weighing each. In total, at least $⌊ n / 2 ⌋ + 2 (n - 1) - 2 ⌊ n / 2 ⌋ = ⌈ 3 n / 2 ⌉ - 2$ weighings.

Why a fixed set of weights cannot be the adversary

An adversary that picks the weights in advance loses to a method that bets on that particular order. Weigh $0$ against $1$ , $1$ against $2$ , and so on. If every answer agrees with the order, $n - 1$ weighings prove both the lightest and the heaviest. Part C's grader plays exactly that bet. It first learns the order your adversary gives, then replays it against a fresh copy. An adversary has to decide as it goes. That is also why a lower bound is a statement about the worst case: on any one input, some lucky method is fast.

Going further

The second lightest (part D) takes $n + ⌈ \log_{2} n ⌉ - 2$ weighings: a knockout tournament, then a knockout among the parcels that lost directly to the winner. Kislitsyn proved this optimal (1964). The adversary keeps track of how many parcels each parcel has beaten, directly or through others.
Exact minimum-comparison selection for general ranks is still not settled. Knuth's Sorting and Searching, section 5.3.3, collects what is known.
The same counting of units proves lower bounds well beyond comparisons. Recognizing what "still unproved" means is most of the work.

References

I. Pohl. A sorting problem and its complexity. Communications of the ACM 15(6), 1972.
S. S. Kislitsyn. On the selection of the $k$ th element of an ordered set by pairwise comparisons. Sibirskii Matematicheskii Zhurnal 5, 1964.
D. E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd edition, section 5.3.3. Addison-Wesley, 1998.

The Lightest and the Heaviest