Where is the cheapest gas station?

Let the 3 gas stations in order of appearance be A-B-C.

Strategy 1: Stop at A and fill the gas right there.

• With this strategy, your probability of picking the cheapest gas station is simply $\frac13.$

Strategy 2: Check all 3 gas stations in the sequence A-B-C.

• With this strategy, you have no other choice but to select C (because you can't go back), and the probability of picking the cheapest gas station is again $\frac13.$

Strategy 3: Check the price at A, and then go to B.

• Case 1: The price at B is cheaper than at A (for short, A > B) with probability $\frac12.$ $\big($ Comparing only A and B, this probability is $\frac12,$ not $\frac13.\big)$

  • Then what's happening must be one of the following three: (1) A > B > C, (2) A > C > B, (3) C > A > B.
    That is, given the information A > B, the probability of B being the cheapest price is $\frac23,$ while the probability of C being the cheapest price is $\frac13.$
    
  • So, in Case 1, you will fill the gas at B, making your probability of picking the cheapest gas station $\frac12 \times \frac23 = \frac13.$
    $$
    

• Case 2: The price at B is higher than at A (i.e. A < B) with probability $\frac12.$

  • Then what's happening must be one of the following three: (1) A < B < C, (2) A < C < B, (3) C < A < B.
    That is, given the information A < B, the probability of A being the cheapest price is $\frac23,$ but unfortunately you can't go back. However, buying gas at B is not optimal because it's already been proven that B is not the cheapest gas station.
  • So, you will proceed to the next gas station C, hoping that it is the cheapest one (i.e. C < A < B) with probability $\frac13.$ Then, in Case 2, your probability of choosing the cheapest gas station is $\frac12 \times \frac13 = \frac16.$

Therefore, with Strategy 3, your probability of picking the cheapest gas station is $\frac13+\frac16=\frac12,$ implying you will definitely choose Strategy 3 over Strategy 1 and Strategy 2.

Now, with Strategy 3, you go to B with probability 1.

• Once you check the price at B and it turns out that A > B, you buy the gas at B, in which case your probability of picking the most expensive gas station is 0.
• If you check the price at B and it turns out that A < B with probability $\frac12,$ then you go to the next station C, and your probability of picking the most expensive gas station (i.e. A < B < C) is $\frac13.$

Therefore, the probability that you end up picking the most expensive gas station is $\frac12 \times \frac13=\frac16.$ $_\square$

$$
Note:

1. This unfortunate event always happens at the last gas station C.
2. You never fill the gas at station A in this setup, regardless of where its price ranks among the three.

Assume stations are labeled A, B and C in the order you encounter them.

Optimal strategy: Note price at A and keep going. If B is less than A fill up there, otherwise fill up at C.

Looking at the sequence of stations in order of ascending prices, there are six possibilities (ABC, ACB, BAC, BCA, CAB, and CBA).

Only ABC results in paying the highest price (1/6 probability).

ACB and CBA result in paying the middle price (1/3 probability).

BAC, CAB, and BCA all result in the lowest price (1/2 probability).

1.2.3. Most expensive decision. Buy at third
1.3.2. Buy at third
2.1.3. Second
2.3.1. Third
3.1.2. Second
3.2.1. Second
At first station, you ask for the price and do not buy it.
At second, if the price is lower than before, you buy it and if not, don't buy it.
At third, if you hadn't buy it, you must buy it.

I imagine the simplest solution is as follows: The probability to stop at any one of the gas stations is 1/3. The probability of the picked station being the most expensive is 1/2. Therefore, the final answer is 1/6.

Let the three stations be represented as A, B and C with prices ascending in that order. The six possible arrangements are (1) ABC, (2) ACB, (3) BAC, (4) BCA, (5) CAB, (6) CBA.

METHOD ONE: Suppose your first method is to buy gas at the first station. The probability of being the highest price is 1/3.

METHOD TWO: Note the price of gas at the first station but do not buy it. If the price at the second station is cheaper than the first, buy it there. These are options (3) BAC, (5) CAB and (6) CBA. If the second station is more expensive than the first, then continue to the third station, where you must buy the gas. These are options (1) ABC, (2) ACB and (4) BCA. Only scenario (1) ABC forces you to buy the most expensive gas. Thus, P=1/6.

METHOD THREE: Pass the first two stations and but at the third. The probability of the most expensive gas is 1/3.

The best method is METHOD TWO, with a probability of 1/6.

First, we need to enumerate the strategies.

Pure strategies: S1: buy gas at the first station. S2: skip the first station and buy gas at the second station, ignoring the prices S3: skip the first two stations and buy gas at the third station, ignoring the prices.

Clearly with all three of these strategies the probability of getting the cheapest gas is 1/3 and the probability of getting the most expensive gas is 1/3. Also, S1 is the only strategy that results in purchasing gas at the first station.

What kind of other strategies are there? Well, when we reach the second station, we have information about the first two prices, and a decision as to whether to go on or not. That's the only information we have that can affect a choice. Any information gotten at the third station doesn't inform our decision-making process. Because the decision is made at the second station.

There are two possible bits of information we can receive at the second station, and each can direct our decision-making according.

A strategy then consists of the pair (D1, D2) of what we do if the second price is lower or higher than the first price, respectively. Notice S2 = (buy at 2, buy at 2) and S3 = (buy at 3, buy at 3). So the only two other strategies are S4=(buy at 2, buy at 3) and S5=(buy at 3,buy at 2).

Consider what happens with S4. I'll consider all the permutations of {1,2,3} to correspond to the ordering, from cheapest to most expensive, of the three gas stations.

123: we go on and buy at the most expensive station 132: we go on and buy as the middle-priced station 213: we buy at the second station, the cheapest 231: we buy at the third station, the cheapest 312: we buy at the second station, the cheapest 321: we buy at the second station, of middle price

So with S4, we buy the cheapest gas with probability 1/2 and the most expensive gas with probability 1/6. This strategy is clearly better than any of the pure strategies.

Now for the sake of completeness we consider S5, the mirror of S4. Recall that S5 requires us to buy gas at the second station exactly when it's more expensive than the first station. 123: we buy the midde-priced gas at the second station 132: we buy the most expensive gas at the second station 213: we buy the most expensive gas at the third station 231: we buy the most expensive gas at the second station 321: we buy the cheapest gas at the third station 312: we buy the middle-priced gas at the third station

S5 is the worst strategy, yielding a probability of 1/2 of buying the most expensive gas and only probability of 1/6 of buying the cheapest gas.

Thus the optimal strategy is S4, and the probability of buying the most expensive gas using this strategy is 1/6.

We know the following:

• There are three gas stations of differing prices. (1)
• We can assume that we do not know the exact prices. (2)
• We must calculate the probability, assuming we have the used the strategy which maximises the chance of buying gas at C.
• We cannot go back to an earlier station.
• If you arrive at the third gas station without picking, you must pick the third gas station. (3)

Let the different gas stations be named A (most expensive), B and C (least expensive). In this diagram, the direction of travel is to the right. For example, for the first possibility (ABC), you will encounter A first, then B, then C. Then we can construct all the possibilities:

1 2 3

A B C

A C B

B C A

B A C

C A B

C B A

According to (2), we cannot use the prices of all of the gas stations. For example, if I am at my first station, I cannot use the prices of future stations because I have visited them yet. At station 1, I cannot do any comparison because I don't have enough information At station 2, I can only compare 1 and 2. At station 3, comparisons would not matter because I would be forced to pick 3. (according to (3))

1. If I were to pick the station 1, I would have $\frac {1}{3}$ of a chance to arrive at C
2. If I were to pick the station 3, I would have $\frac {1}{3}$ of a chance to arrive at C
3. If I were to evaluate at station 2, I could compare 1 and 2. I would have 2 strategies:

• if 1>2, pick 2, else pick 3
• if 1<2, pick 2, else pick 3

Going by strategy 1, I would have the following results: B, C, C, C, B, A. Therefore, I would pick C $\frac {1}{2}$ of the time.

Going by strategy 2, I would have the following results: C, B, A, A, A, B. Therefore, I would pick C $\frac {1}{6}$ of the time.

It is clear that strategy 1 (which compares by 1>2) is the best strategy (producing the largest chance of picking C). Therefore we will use its results to answer the question. Remember the that the stations which we may pick are:

B, C, C, C, B, A

Doing 1 divided by 6, we arrive at the answer: the chance of picking A is $\frac {1}{6}$ .

Note: We do not have to worry about two stations having the same price (refer to (1)), therefore I do not mention it in the solution.

Your knowledge about gas station 3 will not help in the decision making: when you get there, you have to get gas there! Also, your knowledge about gas stations 1 and 2 does not tell you anything about gas station 3. Therefore,

the odds of picking the cheapest or most expensive gas are $\tfrac13$ , unless you decide to stop at gas station 2.

If you know that station 2 is more expensive than station 1, it cannot possibly be the cheapest. In that case, you will therefore gamble on gas station 3.

This leaves the situation when station 2 is cheaper than station 1. The odds of it being the cheapest gas station are $\tfrac23$ , better than the usual $\tfrac13$ odds; therefore you will want to make this choice. In this situation, you will never have the most expensive gas.

Together, this suggests the following strategy:

• Pass the first gas station.

• Stop at the second station if it is cheaper than the first.

• Otherwise, stop at the third station.

The odds of getting the cheapest gas are $\tfrac12\cdot \tfrac23 + \tfrac12\cdot \tfrac13 = \tfrac12;$ the odds of getting the most expensive gas are $\tfrac12\cdot 0 + \tfrac12\cdot \tfrac13 = \boxed{\tfrac16}.$