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.