Maybe I don't understand your proof correctly or it has a flaw.

In the three comparisons you propose between the solutions for C and C' you assume there must be a comparison between min and max. This is rarely the case in the implementations regarded as optimal. Thus your proof excludes the relevant algorithms.

Disproving the existence of a certain algorithm is indeed hard. You must not make any assumptions about its function, otherwise you may exclude some algorithms and the proof becomes worthless.

First of all, there is a strong need do define what that algorithm shall be. In this specific case I'd define a solving algorithm as follows:

• It is an nondeterministic state machine.
• The initial input is the number of items.
• The state machine then outputs pairs (i, k) of indices and expects the result of m(i) <=> m(k) as the next input.
• The machine stops after S steps and produces a directed graph G = (V, E) as output with these properties:
• The vertices V are the indices 1 .. N.
• There is an edge i -> k in E if and only if m(i) < m(k) has been directly proven in the running phase of the machine.
• The graph G has one source in min = min m and one sink in max = max m.

There should be a proof that there is no algorithm that produces a valid output with S < 2 N/3 - 2 comparisons. Such a proof is impossible, as the defined algorithms include those that are cheating. An algorithm may just call for N - 1 comparisons producing a straight sequence of subsequent numbers producing the trivial graph min -> p(2) -> ... ->p(n-1) -> max.

Therefore we need to modify the setup. We do not preallocate the numbers, but arrange them in a consistent way while requested from the algorithm. E.g. if we are first asked for comparing a < b, then for c < d and afterwards for b < c, we are free to arrange these such that b > c.

Then we need to prove that an algorithm under such dynamic conditions is not capable of:

• Finding the solution with S < 3 N/2 - 2 comparisons in every attempt (strict). Or
• Finding the solution with an average number of S < 3 N/2 - 2 comparisons (relaxed).

Maybe my expectations are too high, but that is the kind of proof I had expected and I don't feel capable to provide.

> In the three comparisons you propose between the solutions for C and C' you assume there must be a comparison between min and max.

You mean statement (1) ?

All algorithms must start somewhere, you just pick (Inf,-Inf) for the first pair in algorithm A.¹ And since you already know the result, it's a pseudo comparison - you skip the step it in the constructed algorithm A'.

Just imagine playing the game with C' 100 covered cards plus two extra dummy cards in your head and applying an algorithm A for C 102 cards.

The dealer doesn't know what's in your head, he'll never hear a question about the dummy cards, because you already know the necessary results to continue your algorithm.

Two things are relevant:

• you got the min&max of C' in the end
• you asked the dealer 3 questions less than you would have needed for 102 covered cards.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
see Wikisyntax for the Monastery}

¹) it doesn't matter if it was unlikely. What matters is that A is guaranteed to work with any starting pair.