2
$\begingroup$

Suppose I always pay for things with exact change, if I have it, or the least amount over the cost of the item(s) if I don't have exact change (in which case I'll get change from the seller).

Also, assume my source of money is 20 bills (as from an ATM).

In the boundary case, where I have exactly \20 (possibly all in pennies, but however) and something costs exactly $20, I use the change I have. I only go to the ATM when something I'm going to buy costs more than I have.

Is it possible for the amount of change I have (the number of coins, say, not how much money the coins add up to) to increase without bound? That is, could there be some pathological sequence of prices of purchases in which the number of coins keeps increasing (overall)?

  • 0
    I $a$dded a clarification to the question.2012-09-20

2 Answers 2

5

Assuming you don't fetch bills from the ATM until you have to (i.e. because your change is not sufficient), you will never have more than 19.99 in change and hence never more than 1999 coins.

To see this note that for any amount x=k\cdot 20+r$ with $0\le r<20 you have to pay

  • either your current change c$ is $c\ge r$. In that case you will give $k$ bills plus something between $r$ and $c$ in change and will finally have only $c-r\le c in change
  • or c$. Then your smallest possible amount above $x$ is $(k+1)\cdot 20$ so that you will end with $c+(20-r)$ in change. But $c$ implies $c+(20-r)<20$.

Thus you will never have more than 19.99 in change if you start with no more than 19.99 in change. This bound is optimal because if the first item costs 0.01, you will in fact have 19.99 after that.

4

Once we have enough coins of each type so that we can make up exactly $20$ dollars, the number of coins cannot get larger. (Always pay with the smallest denomination coins possible.) A crude upper bound, for US currency, is $2000$ one cent pieces plus $400$ five cent pieces plus $\dots$.

  • 1
    @PaulReiners: it doesn't matter as the change is $\pmod {\$20}$. You get enough \$20's plus do the change.2012-09-20