January 2021 – Zachary's Challenges

This challenge pertains to algebraic limits, and can be solved through calculus, clever arithmetic, graph theory, or other methods, though is only classified as the foremost.

n \in \mathbb{N} \\[4pt] \operatorname f : \mathbb{R}, \mathbb{Q} \to \mathbb{Q} \\[8pt] \operatorname f {(p, x)} = \begin{cases} p > x : x-\frac1{2n} \\[4pt] p < x : x+\frac1{2n} \\[4pt] p = x : x \end{cases}

The function f id defined above. Consider evaluating f recursively, starting at 0.5, with x as the previous result and p a random number from 0 to 1. Eventually an integer would be reached, and the average time to reach one could be found given n. The challenge is to find this average for as many n as possible, then infinitely many, and perhaps all.

solution

This challenge was to find the optimal strategy for player 5 of a certain game. This must be solved with probability density. Let the PDF before the guess of player n be f_n, and that player’s best guess, x₀. The derivative of the expected value must be zero, which can be simplified to:

x_0 \operatorname{f_n}x_0 = \int_0^{x_0}\operatorname{f_n}x \delta x

Solving for player 1, we get 3x₀ = 2, and so x₀ = 3/2. Using a the same process for players two through 5, we can find the answer. Shown is a table of the best guess, chance of victory, and expected value for players one two five, as well as the probability density function for the weight of the prize before each guess. The answer is thus a guess of exactly 0.1 kilograms, and you will win it exactly half the time.