I Should Have Stopped Later (for gas, not to get married) - Today's Math Lesson

I was driving to Chicago the other day to go out to lunch with Nathan, and I noticed as I left home that I needed to buy gas before I got on the Kennedy Expressway. With the weird things that have been happening to gas prices lately, I was trying to figure out when I should stop for gas. What I mean is that between my house and the interstate, there are about 10 gas stations. I wanted to get the best price for my gas, but the only way to do that perfectly would be to drive past all 10 stations, then go back to the one that had the lowest price. I like to save money, but that seemed a little stupid, so the question was, if  I don't want to go backwards, and I don't know the gas price of any station until I get to it, when should I stop? Let's look at a simpler problem. For example, if there were three gas stations and after the fact I could rank them 1 2 and 3 with 1 the best price, when should I stop? There are 6 possible orders that the stations could occur in: 1 2 3; 1 3 2; 2 1 3; 2 3 1; 3 1 2; 3 2 1. Here, for example, 3 1 2 means that I first pass the 3rd lowest gas station (that is, the highest price), then the lowest one, then the 2nd lowest one. If I use as my rule, stop at the first gas station I see, then 2 of the 6 arrangements would leave me buying gas at the cheapest station: 1 2 3 and 1 3 2. Therefore 1/3 of the time I would be buying the cheapest gas possible. I would have the same probability of buying the cheapest gas (1/3) if I always went to the second gas station. Then 2 1 3 and 3 1 2 (but none of the others) would have the cheapest gas at the second station. However, suppose my rule was stop at the first gas station that had a cheaper price than the first gas station I passed. That is, remember the price of the first station, then stop at the next station that is lower than it. The arrangement 2 1 3 would be good here. The second gas station is cheaper than the first, so I would stop here, and it has the cheapest gas (it's a 1!). 3 1 2 would also work - again the second gas station is better than the first so I would stop there and it is ranked number 1. And 2 3 1 would work - the first station better than station 1 (which is ranked second) would be the third station, and it's ranked number 1. I wouldn't stop at the second station because its price is higher (ranked 3rd) than the first station. The other 3 arrangements would be losers. 3 2 1 for example would cause me to stop at the second station - it's better than the first station - but it turns out it's not the cheapest I could get - the third station is. So 3 of the 6 arrangements give me the best price with this rule - 1/2 the time I would be getting the best price. This turns out to be the best you can do with 3 gas stations. So, what about 10 gas stations? Should you stop at the first gas station better than the first one, or the first gas station better than the first two stations, or check the prices on the first three stations, then stop at the next one you see that is better than all three of them? How many stations should I pass before I start my comparisons. Well, it turns out, using some calculus, that the answer to that is that you should let the first 36.8% of the stations go by, then choose the next one that is better than all the ones you passed by. For those of you with some math background, it won't surprise you, since calculus is involved, that .368 happens to be an approximation for 1 / e. So for our 10 stations, 10 times 36.8% is 3.68, which rounds to 4. You should pass by the first four gas stations, then stop at the first gas station better than the first four. If you do this, you will get the best price about 40% of the time and that's the best you can do. If there were 50 gas stations, then 36.8% of 50 is about 18, so I should go past the first 18 stations, then stop at the next one that is better than all of the first 18. (In this case unfortunately I would probably run out of gas before I stopped.) This problem is an optimal stopping problem, but when I used to teach it in my Senior Topics class, it was called the Secretary Problem. It assumes you know how many applicants you are going to interview for the secretary job and it assumes you will offer the job to someone as you interview them, that is, each applicant is either let go or hired at the end of their interview. It also assumes you can't go back and offer the job to someone you had interviewed previously.  I've also seen it called the Marriage (or Fiancee) Problem. Based on our results, it says that if you expect to date 10 people seriously in your life, you should let the first 4 go, then marry the next one who is better than all of the first four. About 40% of the time, you will end up choosing the best possible mate. OK, maybe we'll just use it for buying gas.