Optimal Money-Saving on the NYC Metro

You are on vacation in New York City. You didn't bring your car, and it's currently around $-50^\circ C$, so it's probably a good idea to take the NYC metro subway to move around.

You need a metro card to ride the subway, and after paying an initial fee of $\$1.00$for the card, you can add balance to it. Reading up on the system, it's kinda dumb. http://web.mta.info/nyct/fare/FaresatAGlance.htm Here are the important parts: • Each ride is$\$2.75$.
• Your deposit to the card must be a multiple of $5$ cents (e.g. $\$101.15$is allowed, but not$\$200.17$).
• If your deposit is $\$5.50$or greater, you get a$5\%$bonus to the deposited amount. The bonus is rounded to the nearest integer number of cents. It's dumb because you're going to waste money. For example, let's say you want to ride the metro$3$times. When you deposit$\$8.25$, we get a $5\%$ bonus of $\$8.66$. After those three rides, we end up with$\$0.41$.

Now imagine how painful it would be to use all of that! It's nearly impossible to have an empty account ever again with such an ugly number. So, you're wasting money! Unacceptable!

You know you're going to use the metro more than once. And we need to be frugal, so you want to deposit the right amount so that after an integer number of rides, your account balance will be $\$0.00$. Assuming that you are only going to make a single deposit, how much money should you deposit into your metro card? Perhaps more objectively, what is the least amount of money that you can deposit onto your metro card to satisfy the above conditions? (I like this problem because it is a very real world application of seemingly useless math!) • I saw the title and thought this was a spam post for a moment :-P – Rand al'Thor Jan 4 '18 at 1:19 • Considering that you're never gonna lose money you own, all that extra money on the card is the metro's own money. Frugal time-saving me would just leave it and laugh at all the accounts the Metro has that are NEVER gonna be used again. What a waste. – Jakob Lovern Jan 4 '18 at 1:29 • To close an obvious loophole: you can't deposit more than once, right? – ffao Jan 4 '18 at 1:31 • @ffao Yes, we'll assume we cannot make more than one deposit. – greenturtle3141 Jan 4 '18 at 1:34 • There's probably bigger things to worry about than extra cents if the temperature is −50°C. – Alpha Jan 4 '18 at 6:43 5 Answers A bit more generically than Rubio's solution, if we denote by$x$our deposit in multiples of 0.05 and the number of trips by$y$, we must have, with integer$x$and$y$: $$55y - 0.1 \le 1.05x < 55y + 0.1$$ Or, multiplying everything by 20: $$\frac{1100y - 2}{21} \le x < \frac{1100y + 2}{21}$$ For$x$to be integer, we must have 1100y mod 21 in {-1, 0, 1, 2}. This happens iff y mod 21 is in {0, 8, 13, 16}, giving us the four families of solutions: • y = 8: Spending 20.95 + 55k • y = 13: Spending 34.05 + 55k • y = 16: Spending 41.90 + 55k • y = 0: Spending 55.00 + 55k (+55k means that you can add any integer multiple of$55.00 to those solutions to produce another solution)

Of those solutions, the smallest is to spend $20.95. • Oh, sure, use actual math. ;) – Rubio Jan 4 '18 at 1:55 • @Rubio I am very tempted to answer with the old "why don't we replace the numbers with numbers in the billions and see how you do it now" :P – Quintec Jan 4 '18 at 2:18 • Yes, yes. I tried 2 rides, then 4, saw a trend, and figured it would be brute forceable before reaching the obvious maximal minimum you found in your answer. My next stab hit paydirt, and walking backwards proved there were no lower solutions, but for more intractable numbers @ffao's approach would be needed — and the proper method anyway. – Rubio Jan 4 '18 at 2:22 • @Aequitas 55k indicates 55*k, where k is an integer. In other words, you can add 55 dollars as often as you like. – Lolgast Jan 4 '18 at 8:13 • It might be worth italicizing the k, just for clarity. – Ethan Jan 4 '18 at 21:06 If you deposit$20.95

You will get credited with

$\$20.95 \times 105\% =~$21.9975 →$\$22.00$

That will give you

Exactly 8 rides at $2.75 Since you are riding more than once, the lower trivial solution of just depositing$2.75 wouldn't satisfy your desire for frugality.

There are no lower solutions than this one -
because the amount to deposit must be a multiple of 5¢ and for any non-trivial solution the actual amount credited will be 5% greater than the deposited amount, these two require that the solution be a multiple of 5 cents near a multiple of $2.75, and it is quick work to demonstrate that no lower number of rides will work out evenly. • I believe this is the correct minimum value. Do you have a proof of minimality? – greenturtle3141 Jan 4 '18 at 1:37 • (Was just adding that. It's there now) – Rubio Jan 4 '18 at 1:41 • +1 because I can understand this answer, I was lost 10 words in on the other one – Tas Jan 4 '18 at 4:44 • For what it's worth, this is considered a "real enough" issue that there are apps for iPhone and Android phones out there specifically to calculate this - and they'll also do it if you have a pre-existing balance, as well. – Jeff Zeitlin Jan 4 '18 at 18:35 Not the smallest, but the best quick real world solution would be to Deposit an amount that 2.75 is 5% of. So 2.75/0.05 gives you 55, so depositing$55 and getting 2.75 extra would give you 21 rides.

• which is interesting because 21 is about how many work days there are in a month – Aequitas Jan 4 '18 at 5:46
• @Aequitas That depends on how long the month is and which days the first/last days of the months are. For 2018, April and June have 21 working days, but January and May have 23, February has 20 and March and July have 22. Haven't checked passed July. – Lolgast Jan 4 '18 at 8:18
• @Lolgast that's why I said "about" – Aequitas Jan 4 '18 at 13:27

Ok, so there's only one way you could do this, and that's multiple deposits. Consider that 8.25/1.05 is a little over 7.85. If you deposited 7.90, then when your rides were over, you'd be left with four and a half cents. Hardly enough to buy a bum's earwax! But if you first deposit 5. 45, then deposit an additional 2.80, you've stayed below the limit AND you've gotten your money in for three free rides.

• Crap, I missed that the number of rides was not set. Ignore this, then. – Jakob Lovern Jan 4 '18 at 2:10

Your deposit must be:

34.05\$ which allows you to make 13 trips.

Thanks Excel for that ;)

• did...you read the other answers before posting this one? – greenturtle3141 Jan 4 '18 at 18:09
• And did you notice the "no-computers" tag? – Peregrine Rook Jan 5 '18 at 3:51