# Stamp Collection And The Road to Redemption

Albert Y. C. Lai, trebla [at] vex [dot] net
November, 2015

## McCafe

McCafe drinks in Canada come with one sticker per cup. Seven stickers can be redeemed for one medium cup of drink (comes with one sticker again). How many drinks can you get for a given amount of money? For simplicity, assume \$1 per drink. (Stick to the medium size, focus on a single type of drink, and invent a new currency to make the price \$1 in the new currency.)

Example: Starting from \$13:

 \$13 → { spend \$13 for 13 drinks and 13 stickers } 13 drinks, 13 stickers → { redeem 7 stickers for 1 drink 1 sticker } 14 drinks, 7 stickers → { redeem 7 stickers for 1 drink 1 sticker } 15 drinks, 1 sticker

you can get 15 drinks (and 1 sticker leftover).

You should work out more examples by hand or by computer (write a program or make a spreadsheet) to get a feel on what can happen.

### Asymptotic (Large-Scale) Trend

When the amount of money—call it m—is large, the number of drinks you will get is approximately 7m/6 (not the intuitive 8m/7). There are several ways to see why.

A very slick way, hard to think up but easy to follow: If you are allowed to borrow 1 sticker from a friend and return a new sticker later, you can spend just \$6 to get 6 drinks and 6 stickers, then redeem 7 stickers for 1 more drink and 1 sticker, and finally return the new sticker to your creditor. So it is 7 drinks for \$6 if you may borrow and return. And if you may not borrow, you can still see how the number of drinks gets close to 7m/6 except for a few leftover stickers you can't redeem (negligible on a grand scale).

A longer way, easy to think up (especially if you're economically inclined) but requires knowing geometric series to finish: \$1 buys 1 drink and 1 sticker. That 1 sticker is worth 1/7 drinks and 1/7 stickers. And that 1/7 stickers are worth (1/7)2 drinks and (1/7)2 stickers. Etc etc ad infinitum. So \$1 is worth these many drinks:

1 + (1/7) + (1/7)2 + (1/7)3 + ⋯

Now use the formula for geometric series to get 7/6.

This large-scale trend may be unimportant to individuals like you and me, but is a matter of life and death for the McCafe business as a whole. At their level, they are selling millions of drinks for millions of dollars, per day. If they mistakenly think that they are selling merely 8m/7 drinks, they will collapse and they won't know why. Even marketing people need to be good at algebra and calculus, if only to calculate the counterintuitive costs of their creative promotion and loyalty programs. HR people, you know what you need to do in the next hiring round: skip marketing applicants who skipped math.

### Exact Formula

Starting with \$m, we can first spend all of it to buy drinks and stickers:

 \$m → { spend all money } m stickers, m drinks

If m≥7, we can redeem 7 stickers for 1 sticker and 1 drink, i.e., stickers go down by 6 and drinks go up by 1:

 m stickers, m drinks → { assume m≥7, redeem 7 stickers } m-6 stickers, m+1 drinks

If m-6 ≥ 7 still, we can do it again, etc. So this is subtracting 6 from m stickers as many times as needed until 1 to 6 stickers remain. The number of drinks goes up by the number of times we subtracted.

Let me put this in a more standard way. Assume m≥1. Separate the m stickers into 1 lone sticker and a pile of m-1 stickers. Don't touch the lone 1 sticker anymore. But do subtract 6 from the pile of m-1 stickers as many times as needed (may be 0 times) until the remainder is 0 to 5. The number of drinks goes up by the number of times we subtracted. In other words, we divide m-1 by 6, the quotient “(m-1) div 6” is added to the drinks, and the remainder “(m-1) mod 6” re-joins the lone 1 sticker.

 m stickers, m drinks → { assume m≥1, redeem like there is no tomorrow } ((m-1) mod 6) + 1 stickers, ((m-1) div 6) + m drinks = { exercise } ((m-1) mod 6) + 1 stickers, (7m-1) div 6 drinks

When m≥1, \$m can get (7m-1) div 6 drinks, and there is a leftover of (m-1) mod 6 + 1 stickers.

## Beer, Bottles, Caps

The McCafe problem was my warm-up problem to help me step up to the following more elaborate one from a friend:

A brewer is selling beers at \$1 per bottle of beer. (The original uses \$2; I'm simplifying it by an exchange rate again.) In addition, you can redeem 2 empty, capless bottles for 1 beer (plus bottle, plus cap). And don't throw away the caps: you can redeem 4 caps for 1 beer (plus bottle, plus cap). How many beers can you get, starting from a given amount of money?

(The original just asks about \$10 in the original currency, or \$5 in my currency. But that's too easy. Answer: 15 beers, 1 leftover bottle, 3 leftover caps.)

### Asymptotic Trend

1 bottle is worth 1/2 beers, 1/2 bottles, and 1/2 caps. 1 cap is worth 1/4 beers, 1/4 bottles, and 1/4 caps. Altogether, 1 bottle and 1 cap are worth 3/4 beers, 3/4 bottles, and 3/4 caps.

\$1 is worth 1 beer, 1 bottle, and 1 cap. That 1 bottle and 1 cap are worth 3/4 beers, 3/4 bottles, and 3/4 caps. Those 3/4 bottles and 3/4 caps are worth (3/4)2 beers, (3/4)2 bottles, and (3/4)2 caps. Ad infinitum. So \$1 is worth these many beers:

1 + (3/4) + (3/4)2 + (3/4)3 + ⋯

Now use the formula for geometric series to get 4.

That's right, the price of 1 beer gets you 4 beers on the large scale.

An argument based on borrowing is possible, just harder to think up what to borrow. Here is one: Borrow 1 bottle and 2 caps. Then \$1 gets you 4 beers:

 1 bottle, 2 caps, \$1 → { buy } 1 beer, 2 bottles, 3 caps → { redeem 2 bottles } 2 beers, 1 bottle, 4 caps → { redeem 4 caps } 3 beers, 2 bottle, 1 caps → { redeem 2 bottles } 4 beers, 1 bottle, 2 caps

Return 1 bottle and 2 caps to the creditor. It's 4 beers for \$1.

The brewer is either in real trouble or has to mark up the price to sustain this incredible business.

### Exact Formula

Starting with \$m, we first spend all of it:

 \$m → { buy en masse } m beers, m bottles, m caps

If m≥3, we can proceed with the following redemptions:

 m beers, m bottles, m caps → { note m≥3, redeem 2 bottles } m+1 beers, m-1 bottles, m+1 caps → { note m+1≥4, redeem 4 caps } m+2 beers, m bottles, m-2 caps → { note m≥3, redeem 2 bottles } m+3 beers, m-1 bottles, m-1 caps

In other words, if m≥3, we can trade 1 bottle and 1 cap for 3 beers. If m-1 ≥ 3 still, we can perform these steps again, etc. Overall, we can do this for m-2 times until 2 bottles and 2 caps are left, but then the number of beers will go up by 3(m-2):

 m beers, m bottles, m caps → { if m≥3, do the above for m-2 times } m + 3(m-2) beers, 2 bottles, 2 caps

The 2 bottles can still be redeemed. One last step:

 m + 3(m-2) beers, 2 bottles, 2 caps → { redeem 2 bottles } m + 3(m-2) + 1 beers, 1 bottle, 3 caps = 4m-5 beers, 1 bottle, 3 caps

The above is also good for m=2: m-2 = 0, so we perform 0 times of “trading 1 bottle and 1 cap for 3 beers”, but we can still perform the last step.

To sum up, when m≥2, \$m can get 4m-5 beers, and there is a leftover of 1 empty bottle and 3 caps.

(Exercise: If at this point you may borrow 1 bottle and 2 caps, you can reach 4m beers.)

Go to Blog of Albert Y. C. Lai