The Ski-Rental Problem

You arrive at a ski resort. Renting skis costs $1 a day. Buying a pair costs $10, once, and then you ski for free forever. The catch: you have no idea how many days you'll ski. The weather, your knee, your budget — any day could be your last.

If you knew you'd ski 20 days, you'd buy on day one. If you knew you'd ski 3 days, you'd just rent. But you don't know. Every morning you must commit money before the future reveals itself.

This tiny dilemma is the ski-rental problem, and it is the friendliest gateway to online algorithms: making irreversible decisions as data arrives, one piece at a time, with no peek at what comes next. The surprise is that a one-line rule does almost as well as a fortune teller.

Below, each day costs $1 to rent and you can buy for $10 at any moment. You don't know when the season ends — but a hidden adversary does, and it will pick the ending that makes your choice look worst.

<p class="hint">{{hint}}</p>
<div class="ctrl">
  <label>{{buy_on_day}} <b id="dayLabel">10</b></label>
  <input id="day" type="range" min="1" max="20" value="10">
  <button id="never" type="button" class="ghost">{{never_btn}}</button>
</div>
<div class="btns">
  <button id="run" type="button">{{run_btn}}</button>
  <button id="reset" type="button" class="ghost">{{reset_btn}}</button>
</div>
<div class="status" id="status">{{pick_strategy}}</div>
<div id="bars" class="bars"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.ctrl { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .6rem; }
.ctrl label { font-size: .95rem; }
input[type=range] { flex: 1; min-width: 140px; accent-color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.bars { display: grid; gap: .5rem; margin-top: .6rem; }
.row { display: grid; grid-template-columns: 110px 1fr 90px; align-items: center; gap: .5rem; font-size: .85rem; }
.track { background: #e8eef3; border-radius: 6px; height: 22px; overflow: hidden; }
.fill { height: 100%; border-radius: 6px; }
.fill.you { background: #1d3557; }
.fill.opt { background: #0a7d33; }
.num { font-weight: 700; text-align: right; }

// Code not found

Try buying immediately, try renting forever, then try the break-even rule: keep renting until your rental spending would equal the purchase price, then buy. Against every ending the adversary throws at you, your total never exceeds twice what a perfect crystal ball would have paid. That factor of two is the famous competitive ratio.

What does it mean for a strategy to be "good" when you can't see the future? We compare against the optimal offline cost — what you'd pay if you'd known the number of days in advance — and ask how much worse the online choice is in the worst case. That worst-case ratio is the competitive ratio.

• The break-even rule is 2-competitive. Rent until accumulated rental cost reaches the buy price $B$, then buy. If the season ends early, you only ever rented — you paid the optimum. If it runs long, you paid at most $2B - 1$ while the optimum was $B$. So you never pay more than about twice the best-in-hindsight cost. This is a proven bound, not a heuristic.
• No deterministic strategy does better. An adversary can always end the season exactly when your fixed plan looks worst, forcing the ratio arbitrarily close to 2. So 2 is optimal for deterministic play — it's a matching lower bound.
• Randomization breaks the barrier. If you flip a biased coin to decide when to buy, the expected competitive ratio drops to $\frac{e}{e-1} \approx 1.58$, and that too is provably optimal (Karlin, Manasse, McGeoch, Owicki, 1990s). You can't beat the adversary every time, but on average you can do strictly better.

This is the heart of online algorithms: the question isn't "can we compute the answer?" — that's easy — but "how badly does not knowing the future cost us?"

"Pay a little repeatedly, or pay a lot once" is one of the most common decisions in computing — and almost always under uncertainty:

• Cloud costs: keep paying for on-demand instances (rent) or commit to a reserved/savings plan (buy)? The break-even rule is the textbook starting point.
• Power management: should a laptop keep a device spinning (rent energy) or power it down and pay the restart cost later (buy)? Spin-down timers are ski-rental in disguise.
• Caching and connections: hold a TCP connection or cache entry open (rent memory) versus tearing it down and re-establishing it (buy). The same trade-off sets keep-alive timeouts.
• Snow-removal and leasing: the original metaphor — lease equipment per use or purchase it — recurs across operations research.

Wherever a system must commit now without seeing demand, the ski-rental rule is the first thing engineers reach for. It also shares its DNA with the broader world of decision-under-uncertainty problems like P vs NP-flavored optimization.

The ski-rental problem is small enough to explain on a chairlift, yet it captures something profound: you can make smart, provably near-optimal choices without ever seeing the future. Rent until your spending equals the purchase price, then buy — and no matter how the season ends, you pay at most twice what perfect hindsight would have.

That factor of two isn't a lucky number; it's the price of not knowing, and it can't be beaten by any deterministic strategy. Flip a coin and you can shave it to about 1.58. The next time you face a "commit now or pay as you go" choice — a cloud plan, a gym membership, a subscription — remember the skier: the break-even line is already the best guess you can make against a future that's allowed to be cruel.