5
$\begingroup$

Bob goes to a vending machine to buy a can of soda. He opens his wallet, and, to his surprise, has no dollar bills or any bills for that matter. The soda costs exactly $1 USD. Bob also has change in his wallet, but even still, he can't buy the soda. What is the maximum amount of change Bob can have without exact change for a dollar?

I know, there's a lot of extra fluff in that question, but that's roughly how I remember seeing it in a puzzle book a while ago. The answer is fairly easy to find out, but I have another question. Is there a general method, formula, or any other way to solve these puzzles without brute-force? This, at least to me, seems to be a recurring problem in books, yet they are often phrased differently and have different currencies, amounts of change required, or other factors changed.

$\endgroup$
10
$\begingroup$

The answer to the question is $1.19. He has 3 quarters, 4 dimes, and 4 pennies.

The unusual answer to this question relies on the fact that the quarter is not an exact multiple of the dime. If every unit of currency was an exact multiple of the next highest one, then you essentially have a positional number system, in which case you cannot have any amount of change higher than a dollar without some subset of that making a dollar.

In general, this sort of problem can't be solved directly like some equations might. There are algorithms, but no known efficient ones. You'd need to depend on clever tricks like the above.

Such change problems are examples of knapsack problems in computer science, specifically subset-sum problems. There's a lot of theory on these problems, and I'd encourage you to check it out if you're really interested.

$\endgroup$
  • 1
    $\begingroup$ The equivalent answer in British money is even higher: one 50 pence coin, four 20s, a 5 and four 2s (and no 10s or 1s), totalling £1.43 without being able to make exactly £1. $\endgroup$ – IanF1 Oct 30 '14 at 7:37
  • 1
    $\begingroup$ (The British money equivalent is also more unwieldy to describe, as we don't have cute names for each coin) $\endgroup$ – IanF1 Oct 30 '14 at 7:50
  • 8
    $\begingroup$ @user2021 Technically the British solution would be infinite, any number of £2 coins can't make exactly £1 $\endgroup$ – RTL Oct 30 '14 at 9:45
  • 1
    $\begingroup$ @Joe: In Canada, we also have $2 coins, and we consider them change, but I wouldn't consider them to be a valid denomination for this problem. $\endgroup$ – Joe Z. Oct 30 '14 at 16:30
  • 1
    $\begingroup$ Agreed, it does invalidate the problem slightly, and should not normally be accepted for this style of puzzle (along with commemerative £5 coins)... however in the spirit of underhanded puzzles it could well be a gotcha $\endgroup$ – RTL Oct 30 '14 at 19:03
1
$\begingroup$

An attempt at the general problem: given a target value $T$ and a number of denominations of coins $x_1, x_2...x_n$ (ordered from highest to lowest), find the maximum total of coins it's possible to have without being able to make exactly $T$.

If there is an $x_i$ which doesn't divide $T$ exactly then you can have an unlimited number of coin $i$ and the puzzle becomes uninteresting.

At the other extreme, if $x_i$ is always an exact multiple of $x_{i+1}$, then we always get a maximum total of $T-x_n$.

The following algorithm is my attempt at the remaining cases:

Step 1: Add $(T / x_1) - 1$ of coin 1 to the selection.

Step $i$, for $i > 1$: find all possible totals of subsets of coins selected in previous steps, which are less than $T$. For each total find the gap to $T$. If any gap is divisible by $x_i$, find the smallest such gap $G$, otherwise set $G = T$. Add $(G/x_i) - 1$ of coin $n$ to the selection.

$\endgroup$
  • $\begingroup$ Thanks to whoever edited to tidy up the maths symbols (the android app doesn't show me who). +1 to you if i could! $\endgroup$ – IanF1 Oct 30 '14 at 17:08
  • $\begingroup$ It's worth noting that changing the U.S. coinage so a dime was worth \$.09, or worth \$0.11, would change things so that in one case the "greedy" algorithm would no longer always yield a unique optimal solution (\$0.36 could be 4x\$0.09, or \$0.25+2x\$0.05+\$0.01--four coins either way), and in the other it would sometimes yield a sub-optimal solution (\$0.33 would be 3x\$0.11, vs \$0.25+\$0.05+3x\$0.01--three coins vs five). $\endgroup$ – supercat Oct 30 '14 at 17:14
  • $\begingroup$ @supercat Hang on - i thought the question was about max total money without being able to get exactly T, not max number of coins. $\endgroup$ – IanF1 Oct 30 '14 at 17:21
-1
$\begingroup$

Joe Z. answered "The answer to the question is $1.19. He has 3 quarters, 4 dimes, and 4 pennies."

Other options are:

  1. 1 quarter, 9 dimes and 4 pennies... which also equals $1.19

  2. 1 half dollar, 1 quarter, 4 dimes and 4 pennies... also $1.19

$\endgroup$
  • 1
    $\begingroup$ Welcome to puzzling.se Based on site practice, this would be more appropriate as a comment instead of an answer to the question. $\endgroup$ – Len Oct 3 '15 at 2:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.