New answers tagged

2

Let $F$ be a function that maps integers from $0 \dots N-1$ to $\{0, 1\}$. We want to find $x$ (which is promised to be unique) such that: $$F(x) = 1$$ Now let's take two random integers $a$ and $b$ from $0 \dots N-1$ and output: $b$, if $F(a) = 0$ $a$, if $F(a) = 1$ For any fixed $x$ and $y$ we have: $$P_{a=x} = P_{b=x} = P_{a=y} = P_{b=y} = \frac{1}{N}...


1

Brute force If you want something easy to implement, brute force might be fast enough, assuming at least one round has been completed. There are $8! = 40320$ possible permutations of the athletes, so in any round, there are 40320 possible rankings. Assuming the first round has been completed, there are only $40320^2 \approx 1.6 \times 10^9$ possible ...


Top 50 recent answers are included