# Spending 1374.00 US dollars in three days

Jenny received 1374.00 US dollars which she has to spend all or a portion of within 3 days, with the following conditions.

1. The percentage (of her current dollars) which she is allowed to spend each day has to be an integer number less than 100.
2. She cannot spend more than the balance she has each day in her pocket (which can be everything she has left).
3. Each day the balance has to be in denominations currently in circulation.

What is the maximum amount of money she can spend in 3 days?

• I don't understand where the puzzle is? Why can't she just spend all 100% on the first day? Jun 12 at 3:19
• @DmitryKamenetsky the percentage must be less than 100% Jun 12 at 3:42
• For those of us not in the U. S., what are the denominations currently in circulation? Jun 12 at 4:37
• @KabirKanhaArora 1, 2, 5, 10, 20, 50, 100, 500. Probably not 1000, because although it exists and is legal currency, it is a collector's item. Cents are: 1, 5, 10, 25. I would argue that 50 cents is not in circulation though it exists. Jun 12 at 10:32
• how is the answer not "all of it"? 1% is 13.74$, which can be made from denominations currently in circulation, and from there any combination of x+y+z = 100 gives a valid result. What I am missing? Jun 12 at 12:34 ## 2 Answers The smallest currency denomination is 1 cent. This means she starts with 137400 cents in her wallet. Prime number factorization of 137400 gives 2 * 2 * 2 * 3 * 5 * 5 * 229 Percentage needs to be integer. You cannot get an integer percentage using 3 or 229. 3 * 229 = 687 At the end of day 3 she needs to have 6.87 dollar left in wallet Answer: The maximum amount she can spend in three days, following all the rules is 1367.13 There are multiple ways of achieving this, involving percentages consisting of the fractions of 2, 2, 2, 5 and 5. One random example: Day 1: 50% 68700 cents remaining, Day 2: 80% 13740 cents remaining, Day 3: 95% 687 cents remaining • Although this doesn't directly answer the question (doesn't provide how to get 1367.13 in 3 days) this is a very nice proof of optimality of Kabir's answer. Nice one! Jun 12 at 7:08 • @justhalf is the proof I added not enough? Jun 12 at 7:26 • @KabirKanhaArora a proof that actually uses maths that someone can follow by hand, and which explains why that is the answer and cannot be bettered is "nicer" than a brute force computer search that gives no clue as to why it is optimal. Jun 12 at 8:11 • Okay, yes, I agree. I could not think of a solid enough handwritten proof quickly, so I went for the brute-force one, in fear of getting ninja'd. Jun 12 at 8:18 • @KabirKanhaArora I didn't say that your proof wasn't enough. But it's just that, to me, this proof is more elegant, as it is more generalizable. Your proof is valid too, since the search space is integer (100x100x100) and there is not much to search. This proof also makes a construction easier too, by simply taking any three combinations of 2x2x2x5x5 that each is less than 100 Jun 12 at 10:21 Going by the information regarding currency denominations available here, I think the answer is:$1367.13

Possible strategy 1:

Possible strategy 2:

Possible strategy 3:

Why this is optimal:

We know that the total amount spent can be represented as a 0.XXXXXX fraction of 1374, since we are allowed to spend an integer percentage on each day, i.e., we need at most 6 (2*3) digits of precision to represent the overall percentage of 1374 spent in the 3 days. Now, brute-force testing all the values starting at 0.999999 and decrementing this number iteratively by 0.000001, the first valid balance at the end of three days is attained when 99.5000% of the money has been spent, the value of which corroborates my answer.

• At the moment, I am unable to construct a concrete proof. All I have is a hunch that this is the best we can do. Jun 12 at 5:13
• Okay, I have now added a proof by exhaustion of sorts. Jun 12 at 5:37
• You can prove it by rot13(ybbxvat ng gur cevzr snpgbevmngvba bs gur fgnegvat nzbhag va pragf, pbzcnevat gung jvgu gur snpgbevmngvba bs gur svany nzbhag va pragf, naq fubjvat jul gubfr svany snpgbef pnaabg or erzbirq). Jun 12 at 5:39