Break a dollar (Posted on 2004-07-14)

	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!

	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