1. Go compare! Guardian's algortithm riddle and mathematical proof

[LanX]

FWIW: It's not too off topic because it's about an algorithm

The Guardian asked in a recent Monday puzzle for an optimal strategy to find the smallest and the biggest in a deck of 100 cards.

https://www.theguardian.com/science/2025/may/12/can-you-solve-it-are-you-craftier-than-a-cat-burglar

(It's not the rope riddle)

While my strategy was optimal like the proposed solution, they claimed the formal proof that there can't be any better solution to be "too technical" to be published there. (Pierre de Fermat giggles in his tomb).

The attempts in the comment section didn't impress me either.

Anyway I spent the last hours figuring out an elegant proof for a general formula of any numbers of cards.

But the comment section there is long closed and I thought the local crowd here would like to try their best too ...:)

So here the task again: (copied from above link)

<Reveal this spoiler or all in this thread>

¹) It's quite rich to ask for an optimal strategy without presenting one...

[LanX]

Here the promised proof.

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
A sketch should be sufficient, feel free to ask if something is unclear
<Reveal this spoiler or all in this thread>

[jo37]

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.

[LanX]

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

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

[jo37]

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.

<Reveal this spoiler or all in this thread>

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

[LanX]

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.

[LanX]

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

[tybalt89]

For those involved with computers, just remember:

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

[LanX]

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.

[jo37]

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.

[LanX]

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.

Update

> This makes a proof more difficult IMHO.

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