Answer: Tuesday Teaser #29
There are various strategies that could be employed to improve the expectation from simply pressing the + button several times. The best such strategy is to separate the tracks into two distinct groups - “far away” tracks and “close” tracks. For the “far away” tracks, the strategy is to hit shuffle until you end up on a “close” track. For the “close” tracks, the strategy is to navigate directly to the desired track (track 6) in the quickest possible fashion, using the + and - buttons.
In the first case, where there are 11 tracks and you desire to reach track 6, the best strategy is to use tracks 1-2 and 10-11 as the “far away” tracks and the remaining tracks 3-9 as “close” tracks. This gives an overall expectation of 22/7 (or 3.14268) button presses. This can be calculated in the standard way (which in this instance involves using an infinite sum) like so: http://goo.gl/M8mXZ.
This turns out to be the optimal solution, though I won’t show that here as the maths is a little involved. The question remaining though, is why choosing the “far away” tracks as tracks 1-2 and 10-11 is the optimal solution. We could equally define the “far away” tracks as 1 and 11, or as 1-3 and 9-11 in our strategy. Do either of these provide a better expectation? If not, why not?
To understand this, let’s generalise a little and suppose we have a total of n tracks. Let’s call the cut-off point x, so that a track is a “close” track if we are within x steps of the desired track. Given this, our strategy dictates that there will be 2x + 1 “close” tracks and n - (2x + 1) “far away” tracks.
Let’s suppose that E(k) is the expected number of button presses to reach the desired track if we are at track k. Note that if track k is a “far away” track, E(k) is exactly the same, regardless of which “far away” track it is. Given this, let’s try to calculate what E(k) is.
The probability of landing on another “far away” track is (n–(2x+1)-1)/(n-1). This is the number of “far away” tracks divided by the total number of tracks that can be landed on.
Similarly, the probability of landing on each of the “close” tracks is 1/(n-1), and the expectation from there is the number of tracks away from the desired track. So the expectation across all of the “close” tracks is (1/(n-1))*(x+…+2+1+0+1+2+…+x), which is equivalent to (2/(n-1))*(1+2+…+x).
Also, using the standard formula (1+2+…+x) = x*(x+1)/2, this simplifies even further to x*(x+1)/(n-1).
From all this, we can deduce the following equation:
Skipping the detailed algebra, we resolve for E(k) and find that:
Now, we know that it must be true that E(k) > x, since k is a “far away” track. But it also must be true that E(k) <= x+1, otherwise the optimal cut-off would be x+1 or greater. Thus, we can find the cut-off by setting E(k) = x and solving for x.
Which, rather nicely, leads to the conclusion that x = sqrt(n-1). Because of the inequalities, we should round down the answer to get the optimal number.
In the two cases mentioned, this leads us to the conclusion that for 11 tracks, we should choose x = 3 and for 101 tracks, we should choose x = 10.
In summary for 11 tracks:
- Use tracks 1-2 and 10-11 as “far away” tracks, and use tracks 3-9 as “close” tracks.
- This gives an expectation of 22/7, or 3.14268 button presses.
And for 101 tracks:
- Use tracks 1-40 and 62-101 as “far away” tracks, and use tracks 41-61 as “close” tracks.
- This gives an expectation of 10 button presses (calculated here: http://goo.gl/AYDUd).
