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

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.

Greetings,
🐻

$gryYup$d0ylprbpriprrYpkJl2xyl~rzg??P~5lp2hyl0p$
  • Comment on Re: 1. Go compare! Guardian's algortithm riddle and mathematical proof

Replies are listed 'Best First'.
Re^2: 1. Go compare! Guardian's algortithm riddle and mathematical proof
by LanX (Saint) on Jun 10, 2025 at 13:52 UTC
    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"

[reply]

In Section Meditations