I've been thinking about a solution for a problem presented in a game. I intuitively understand why I think my solution is correct, but don't know how to prove it mathematically.
The game goes like this:
The game is comprised of 100 levels, and you start the game from Level 1. When you complete a level, you unlock ${X}$ levels above your current level, which you can complete ($X$ varies according to the level you hit, but every succeeding $X$ never larger than the preceding $X$.
EDIT: $X_{n+1}=X_n OR\ X_{n+1} = X_n-1, n\ \epsilon\ Z^+, n < 100$ (Thanks to nicomezi for helping me realize my statement was defined incorrectly!)
The twist is: You don't have to complete every level. Instead, there are various "prize" levels scattered throughout the list (represented by $P_0, P_1,$...$P_{a}$). Your goal is to hit all these "prize" levels at least once with the smallest number of levels played. For simplicity, let's assume Level 100 is also one of these "prize" levels, so you MUST hit Level 100.
I believe that the solution (in plain English) is:
- Always pick the next "prize" level closest to, but above the last played level, and
- Always pick the highest possible level if no "prize" level is available.
Am I mistaken here? How do I prove that my solution is always correct for any arbitrary distribution and number of prize levels, numbers of levels, and any values of $X$?
From your description, the number of levels that are available to play at any given time is always an interval $[1,n]$ for some $n \le 100$ (we consider only the integer points of the interval).
That can easily seen by mathematical induction: It is true for the beginning of the game ($n=1$), and after you chose to play level $k$ from $[1,n]$ you get the levels of the interval $[k+1,k+X_k]$ in addition. But since $k \le n$, we have $[1,n] \cup [k+1,k+X_k] = [1,\max(n, k+X_k)]$ (remember, integer points only considered).
Let's denote the highest available level to play after round $i$ as $n_i$, so we start with $n_0=1$.
Since one needs to reach level $100$, the goal is to have all $100$ levels available and having played all the prize levels. So playing a level on round $i+1$ can only have 2 goals: It can be a prize level, then it must be played to win the game by definition. If it is not a prize level, the only affect it has on the task is increasing the upper bound $n_{i+1}$ of the available levels.
If you play the highest available level at round $i+1$, you get $n_{i+1}=n_i+X_{n_i}$. If you play the next lower level instead, you get $n'_{i+1}=\max ((n_i-1)+X_{n_i-1}],n_i)$. Since we know that $X_{n_i} \ge X_{n_i-1}-1$, we have $(n_i-1)+X_{n_i-1} \le (n_i-1)+X_{n_i}+1 = n_i+X_{n_i}$ and also $n_i \le n_i+X_{n_i}$, so we get
$$n'_{i+1} \le n_{i+1}$$
That same argument can be repeated for starting 2 levels below the maximum available (so in a sense this is again mathematical induction).
So we see that starting below the maximal available level is not better to get a higher available level after this round than just playing the maximal available level.
This proves your inution: The only reason to play a non-prize level is to expand the available levels as much as possible, and that can be done by playing the highest available levels. Maybe in some cases playing the second highest level would also work, but playing the highest is never wrong.