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.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
7
  • 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, 2014 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, 2014 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, 2014 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$
    – user88
    Oct 30, 2014 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, 2014 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.

Improve this answer
$\endgroup$
3
  • $\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, 2014 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, 2014 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, 2014 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

Improve this answer
$\endgroup$
1
  • 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, 2015 at 2:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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