All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Break a dollar (Posted on 2004-07-14)
In the USA, there are coins of 1 cent, 5 cents, 10 cents, 25 cents, 50 cents and 1 dollar.
You can pay one dollar using either one coin (100), or two coins (50 + 50), or three (50 + 25 + 25), or four (25 + 25 + 25 + 25), etc.

What is the smallest number such that you cannot pay \$1 with that many coins?

 Submitted by Federico Kereki Rating: 3.2500 (4 votes) Solution: (Hide) 77 -- it's impossible to pay \$1 with 77 coins. Since all coins are multiple of 5 cents, you need 5P pennies to make a dollar, with P<20. The remaining 100-5P cents are 77-5P coins, worth at least 5 cents each, 100 - 5k >= 5 * (77 - 5k) By algebra: 20 - k >= 77 - 5k 4k >= 57 k >= 57/4 = 14.25 Since k is an integer, k >= 15, i.e. we must have at least 5*15 = 75 pennies. We can't have more because 5*16 = 80 is already greater than 77. But then we must find exactly two coins to add up to the remaining 25 cents. By exhaustive search we show there is no such combination. To complete the solution, it can be shown that for any number less than 77, there IS a solution... an exercise left to the reader!

Comments: ( You must be logged in to post comments.)
 Subject Author Date Mint Condition Dej Mar 2008-04-01 11:54:08 Answer K Sengupta 2008-03-31 15:27:24 No Subject joe 2004-11-27 02:54:42 re: i think i have the answer Richard 2004-07-19 22:39:23 i think i have the answer sherwin 2004-07-19 06:01:59 Other observations Eric 2004-07-14 09:10:53 The Bully method! Juggler 2004-07-14 09:09:29 Solution Eric 2004-07-14 08:58:50

 Search: Search body:
Forums (0)