## Higher or Lower (Solution)

To start, it seems intuitively clear that if the current number is > 0.5, then you should guess “lower”, and otherwise guess “higher”. Let’s just agree that’s optimal.

Let’s call \(z(x)\) the value of the game if the “current number” (i.e. the last number generated) is \(x\). Given our symmetric strategy around 0.5, it’s also clear that \(z(\frac{1}{2}+x) = z(\frac{1}{2}-x)\). To simplify our equations, let’s define \(f(x)\) as the value of the game if the current number is \(x\) away from \(\frac{1}{2}\). In other words, \(z(x) = f(\vert x - \frac{1}{2}\vert)\). So, if the current number is 1, then the value of this game is \(z(1) = f(\frac{1}{2})\).

This equation accurately describes the value of the game, for any \(x\):

\[f(x) = \int_{0}^{\frac{1}{2}} (1 + f(y)) dy + \int_{0}^{x} (1 + f(y)) dy \\ f(x) = \int_{0}^{\frac{1}{2}} f(y) dy + \int_{0}^{x} f(y) dy + \frac{1}{2} + x\]But how to solve that… ugh.

Let’s define \(f(x) = g'(x)\), i.e. \(f(x)\) is the first derivative of \(g(x)\). Now we can rewrite our equations:

\[g'(x) = g(y) \bigg|_0^{\frac{1}{2}} + g(y) \bigg|_0^x + \frac{1}{2} + x \\ g'(x) = g(\frac{1}{2}) - g(0) + g(x) - g(0) + \frac{1}{2} + x \\ g'(x) = g(x) + x + g(\frac{1}{2}) - 2g(0) + \frac{1}{2}\]Not gonna lie, had to watch some khan academy videos to refresh myself on how to solve linear differential equations. You basically assume the equation is linear, \(g(x) = mx + b\), and then solve for \(m\) and \(b\).

\[g(x) = mx + b \\ g'(x) = m = g(x) + x + g(\frac{1}{2}) - 2g(0) + \frac{1}{2} \\ m = g(x) + x + g(\frac{1}{2}) - 2g(0) + \frac{1}{2} \\ m = mx + b + x + g(\frac{1}{2}) - 2g(0) + \frac{1}{2} \\ 0 = x(m+1) + b - m + g(\frac{1}{2}) - 2g(0) + \frac{1}{2}\]And since \(0\) is a constant, it can’t depend on \(x\), meaning that \(m+1 = 0\) and \(m = -1\). \(b\) doesn’t actually matter since I’m only interested in \(f(x)\), which depends on differences of \(g(x)\), meaning that the constant part of \(g(x)\) will always cancel out.

So, we now have this equation:

\[g(x) = -x + c_1 \\ g'(x) = -1\]We can plug this into our original equation for \(g(x)\) to check that it works:

\[g'(x) = g(x) + x + c_2 \\ -1 = -x + c_1 + x + c_2 \\ -1 = c_1 + c_2\]Constants aside, it looks good. But wait, there’s one more thing. These linear solutions actually aren’t the only solutions that work. You can add \(c e^{x}\) and the differential equation for \(g'(x)\) will still hold as follows:

\[g(x) = c_0 e^x - x + c_1 \\ g'(x) = c_0 e^x - 1 \\ g'(x) = g(x) + x + c_2\]Let’s incorporate an additional \(c_0 e^x\) into our solution for \(g(x)\).

\[g(x) = c_0 e^x + -x + c_1 \\ f(x) = c_0 e^x - 1\]I don’t care about \(c_1\) because the function I really want is \(f(x) = g'(x)\) and \(c_1\) won’t affect \(f(x)\). But \(c_0\) will affect \(f(x)\) so we need to figure that one out.

In order to solve for \(c_0\) we can use the fact that \(f(\frac{1}{2}) = 2f(0)\). This is from intuition. If the current number if 0.5, and you guess lower, and you’re right, then - on average - you’re in the same situation as if the current number is 1 and you guess lower. The only difference is that in the 0.5 case, you’re wrong half the time. \(f(\frac{1}{2}) = 2f(0)\).

\[f(x) = c_0 e^x - 1 \\ f(\frac{1}{2}) = 2f(0) \\ c_0 e^{\frac{1}{2}} - 1 = 2(c_0 - 1) \\ c_0 = \frac{-1}{e^{\frac{1}{2}}-2}\]Great, we have \(c_0\), so let’s finally solve for \(f(x)\).

\[f(x) = c_0 e^x - 1 \\ f(x) = \frac{-1}{e^{\frac{1}{2}}-2} e^x - 1\]Let’s use one last thing from intuition. \(f(0.5)\) is one more than the value of the game. You can think of it as “you get one freeby, then we’re going to play the game that I originally described”. Knowing this - the value of the game is:

\[game = f(0.5) - 1 \\ game = \frac{-1}{e^{\frac{1}{2}}-2} e^{\frac{1}{2}} - 2 \approx 2.7\]