Here's a direct proof for problem 3 that doesn't use any contradiction (perhaps someone will find it clearer). Say you have N gas stations. For any n between

Here's a direct proof for problem 3 that doesn't use any contradiction (perhaps someone will find it clearer). Say you have N gas stations. For any n between 1 and N, say: * f_n is the amount of fuel in the nth station, and * d_n is the distance from the nth station to the (n+1)th. You want to make sure that at each step along your path, you have more fuel than the distance you need to travel. Using our notation, for each step along the path, we want the sum of the f_n so far to be larger than the sum of the d_n. That's the same as saying the sum of (f_n - d_n) should never dip below zero. So how do we show that we can visit all the gas stations while keeping the sum of (f_n - d_n) non-negative? Well, since we have just enough gas to get around the track, we know that the sum of (f_n - d_n) along the entire path is zero. In other words, if we write out the partial sums: S_1 = f_1 - d_1 S_2 = f_1 - d_1 + f_2 - d_2 ... S_N = f_1 - d_1 + ... + f_N - d_N then S_N is zero, since the distances and the fuel amounts cancel each other out. Now look through this list and find the smallest partial sum. Call it S_m. If we change our path to visit gas station 'm' last (and start at station 'm+1'), we get these updated partial sums as we move along our new path (call them U_n): U_1 = f_{m+1} - d_{m+1} U_2 = f_{m+1} - d_{m+1} + f_{m+2} - d_{m+2} ... U_{N-m} = f_{m+1} - d_{m+1} + ... + f_N - d_N U_{N-m+1} = f_{m+1} - d_{m+1} + ... + f_N - d_N + f_1 - d_1 ... U_{N-1} = f_{m+1} - d_{m+1} + ... + f_N - d_N + f_1 - d_1 + ... + f_{m-1} - d_{m-1} U_N = f_{m+1} - d_{m+1} + ... + f_N - d_N + f_1 - d_1 + ... + f_m - d_m Now note that: U_1 = S_{m+1} - S_m U_2 = S_{m+2} - S_m ... U_{N-m} = S_N - S_m U_{N-m+1} = S_N - S_m + S_1 ... U_{N-1} = S_N - S_m + S_{m-1} U_N = S_N - S_m + S_m Since S_N is zero, all the U_n are of the form S_i - S_m (for various i). And S_m is the least partial sum -- that means S_i >= S_m for all the S_i in the list. So each U_n is greater than or equal to zero, just like we wanted. Therefore our last stop should be the gas station with the biggest fuel deficit compared to its distance from the next station (and we should begin our trip at that next station to guarantee we never run out of gas).