10
$\begingroup$

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?

$\endgroup$
9
  • 4
    $\begingroup$ I don't understand where the puzzle is? Why can't she just spend all 100% on the first day? $\endgroup$ – Dmitry Kamenetsky Jun 12 at 3:19
  • 2
    $\begingroup$ @DmitryKamenetsky the percentage must be less than 100% $\endgroup$ – 102152111 Jun 12 at 3:42
  • 9
    $\begingroup$ For those of us not in the U. S., what are the denominations currently in circulation? $\endgroup$ – Kabir Kanha Arora Jun 12 at 4:37
  • 1
    $\begingroup$ @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. $\endgroup$ – piojo Jun 12 at 10:32
  • 1
    $\begingroup$ 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? $\endgroup$ – njzk2 Jun 12 at 12:34
13
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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! $\endgroup$ – justhalf Jun 12 at 7:08
  • $\begingroup$ @justhalf is the proof I added not enough? $\endgroup$ – Kabir Kanha Arora Jun 12 at 7:26
  • 1
    $\begingroup$ @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. $\endgroup$ – Steve Jun 12 at 8:11
  • $\begingroup$ 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. $\endgroup$ – Kabir Kanha Arora Jun 12 at 8:18
  • $\begingroup$ @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 $\endgroup$ – justhalf Jun 12 at 10:21
5
$\begingroup$

Going by the information regarding currency denominations available here, I think the answer is:

$1367.13

Possible strategy 1:

enter image description here

Possible strategy 2:

enter image description here

Possible strategy 3:

enter image description here

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – Kabir Kanha Arora Jun 12 at 5:13
  • 1
    $\begingroup$ Okay, I have now added a proof by exhaustion of sorts. $\endgroup$ – Kabir Kanha Arora Jun 12 at 5:37
  • $\begingroup$ 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). $\endgroup$ – Jaap Scherphuis Jun 12 at 5:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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