Before revealing your spoiler or following the link in the original post, here is my attempt to solve the puzzle.

I cannot prove this being optimal and I don't even have an idea about how to prove it. Tough stuff.

I'm curious to look at the hidden/linked resources.

Update: I had expected more information from following the link. Waiting for lanx's proof 😀.

My spoiler has only the task, I didn't want to show it verbatim because of the authors copyright.

If you follow the links you'll see that your solution is optimal.

But I would hide your number behind spoiler tags too. :)

I'll wait some days before showing my proof.

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

> Update: I had expected more information from following the link

Behind the link is another link to the "solution", with another comment section. With various so called proofs, which I didn't find understandable or convincing.

Ignore the comments about "less vs fewer"

Except the one saying there should be a special hell for people nagging about grammar in a math blog.

> Waiting for lanx's proof

Please remind me next weekend. :)

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

For those involved with computers, just remember:

"less" is analog,
"fewer" is digital.

Hey

> > Waiting for lanx's proof

> Please remind me next weekend. :)

I got messages asking me when I'm posting the proof.

I wanted everybody interested to have a chance to see the task and attempt to find a(nother) proof.

Please /msg [lanx] if you want me to wait till the weekend. Otherwise I'll post it tomorrow.

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

An algorithm A was shown to calculate the min_max of a set of 100 sortable elements in a set C in o(A,C) = 148 comparisons. It was maintained that this solution is optimal.

I'm shying away from a full formal proof, because of

• lack of mathematical notation possible.
• avoiding Tl;dR

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.

Greetings,
🐻

$gryYup$d0ylprbpriprrYpkJl2xyl~rzg??P~5lp2hyl0p$

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

There is a subtlety in this puzzle. While it is possible to find min and max in the given number of operations, it can be done with one operation less, with a chance of about 0.163. In the other cases this causes on more operation. Compared to a lottery, there is a very high chance of winning the game :-)

This makes a proof more difficult IMHO.

No probabilities, no subtlety.

Algorithms and complexities are by default calculated for the worst case.

FWIW: I just saw a probabilistic approach to prime factorization which is very successful but also very slow in worst case.

But this kind of algorithms play in a different league and are off topic for the task at hand.

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

Update

> This makes a proof more difficult IMHO.

My proof isn't difficult, and once you've seen it it feels "natural"