In the imaginary city of New Amsterdam, the subway system is run by the Mediocre Transit Authority (MTA). The subway system uses a single-fare system, where each ride costs $1 irreSpec- tive of the length of the trip. (As such, the cost correSponds just to the number of trips.) Recently, after only a few years of delay, the MTA rolled out their tap-to-pay fare payment system. To incentivize people to switch to the new system, they decided to introduce fare capping where one pays for at most M trips in a given week (starting on Mondays) when using the same payment card. You are a smart and frugal student who knows their ride schedule in advance. More concretely, you know that your semester consists of n weeks, and you know that in week i on the j-th day (where l S j S 7) you will take RE, j] many trips. (a) (2 points) Assume you only use a single payment card. Give a formula for the number of actually paid trips. Solution: INSERT YOUR SOLUTION HERE D You now wonder whether the MTA's fare capping program will automatically lead to the cheapest solution for you, or whether you should juggle multiple payment cards to manually optimize the scheme. More concretely, you have 1: payment cards and you are willing to use a different one each day, in search for the lowest cost, but want to carry at most one card at any given day. As such, a strategy Z is a function from week-day pairs (w,d) to the payment cards 1, . . . ,k you use on that day. The goal is to come up with a strategy that minimizes the number of paid trips. (b) (2 points) Given such a strategy Z, devise a cost function Fwy-(Z) that accounts for the number of paid trips for days 1, . . . , of week m. (In other words, only consider a single week w and only the rst *5 days thereof.) (Hint: You might nd the indicator function useful 1 Z(w1d) : p: 2' 'p( ) {0 otherwise, which for xed Z, w, and p determines whether Z uses p on day d of the given week 11).) Solution: INSERT YOUR SOLUTION HERE D (c) (5 points) Now show that within a xed week is using a single payment card is optimal using the "Greedy Always Stays Ahead" (GASA) strategy. In other words, let G be the strategy such that C(w, d) = 1 for any week w and day (i. Using induction over i, prove that Fw,i(G) S Fw,i(Z)

In the imaginary city of New Amsterdam, the subway system is run by the Mediocre Transit Authority (MTA). The subway system uses a single-fare system, where each ride costs $1 irrespec- tive of the length of the trip. (As such, the cost corresponds just to the number of trips.) Recently, after only a few years of delay, the MTA rolled out their tap-to-pay fare payment system. To incentivize people to switch to the new system, they decided to introduce fare capping where one pays for at most M trips in a given week (starting on Mondays) when using the same payment card. You are a smart and frugal student who knows their ride schedule in advance. More concretely, you know that your semester consists of n weeks, and you know that in week i on the j-th day (where 1 j 7) you will take R[i, j] many trips. (a) (2 points) Assume you only use a single payment card. Give a formula for the number of actually paid trips. Solution: INSERT YOUR SOLUTION HERE You now wonder whether the MTA's fare capping program will automatically lead to the cheapest solution for you, or whether you should juggle multiple payment cards to manually optimize the scheme. More concretely, you have k payment cards and you are willing to use a different one each day, in search for the lowest cost, but want to carry at most one card at any given day. As such, a strategy Z is a function from week-day pairs (w, d) to the payment cards 1,..., k you use on that day. The goal is to come up with a strategy that minimizes the number of paid trips. (b) (2 points) Given such a strategy Z, devise a cost function Fw,i (Z) that accounts for the number of paid trips for days 1,..., i of week w. (In other words, only consider a single week w and only the first i days thereof.) (Hint: You might find the indicator function useful 1Z,w,p(d) := Z(w, d) = 0 otherwise, = P, which for fixed Z, w, and p determines whether Z uses p on day d of the given week w.) Solution: INSERT YOUR SOLUTION HERE (c) (5 points) Now show that within a fixed week w using a single payment card is optimal using the "Greedy Always Stays Ahead" (GASA) strategy. In other words, let G be the strategy such that G(w, d) = 1 for any week w and day d. Using induction over i, prove that Fw,i(G) Fw,i(Z)