Is the amount of change in my pocket bounded?

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)? - What if you have two possible ways to pay an amount, one involving also cash and one with change only? For example, suppose you manage to have 20 dollars in change, and the next item is 20 bucks exactly. Would you pay with a bill or with the whole change? I am not so convinced you can reach 20 dollars, in fact, but just looking for an upper bound for now. – Niccolò Sep 20 '12 at 19:24 I added a clarification to the question. – Paul Reiners Sep 20 '12 at 19:30 2 Answers 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<r$. 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<r$ 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.

-

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$.

-
Right. We can never get more change than a thing costs. And we get another $20 bill if and only if we need it. So, if there is a bound on the cost of things, then there would be a bound on the amount of change. What happens if prices aren't bounded? – Paul Reiners Sep 20 '12 at 19:34 @PaulReiners: it doesn't matter as the change is$\pmod {\$20}$. You get enough \\$20's plus do the change. – Ross Millikan Sep 20 '12 at 19:40