the ski-rental problem

You are about to take up skiing, but you have no idea whether you will love it and ski for years, or quit after one cold weekend. Each day on the slopes you can rent skis for 1 dollar, or you can buy a pair once for B dollars and never pay rental again. If you knew the future — exactly how many days you will ski — the choice is trivial: ski many days, buy on day one; ski few days, just rent. The catch is you do NOT know the future, and each morning you must decide again, rent or buy, with no take-backs. This tiny puzzle is the cleanest illustration of the whole online-algorithms idea.

Here is the classic strategy and why it is good. Rent for the first B-1 days; if you are still skiing on day B, buy. Compare your cost to OPT, the cost you would pay if you had known the total number of ski days T. If T < B, the optimum was to rent all T days (cost T), and you also only rented (cost T) — you match OPT exactly. If T >= B, the optimum was to buy on day one (cost B), while you rented B-1 days then bought, paying (B-1) + B = 2B - 1. So in every case your cost is at most 2*OPT - 1: this rule is 2-competitive. The intuition is balance: you refuse to buy until renting has already cost almost as much as buying, so a wasted purchase can never have hurt you by more than a factor of two.

Ski-rental matters far beyond skis: it is the template for every 'pay-as-you-go versus pay-once' decision under uncertainty — keep a database connection open (rent) or cache the result (buy); spin a cloud server down and up repeatedly or reserve it; keep a spinlock spinning or pay to context-switch. The 2-competitive guarantee is the best any deterministic online strategy can do here; cleverly flipping a coin (randomization) can push the expected ratio down toward e/(e-1), about 1.58. The honest caveat: the clean factor of 2 assumes you know B; if rental prices or B itself drift, the analysis must be redone.