Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Feb 18, 2015

Buying in Rocket Ships and Selling in Fire Sale

Source: Asked to me by Ankush Jain (CSE IITB 2011, Morgan Stanley Quant Associate). He took it from Algorithms Design book by Tardos and Kleinberg

Problem:
Easy case:
You’re trying to buy equipments whose costs are appreciating. Item i appreciates at a rate of r_i > 1 per month, starting from $100, so if you buy it t months from now you will pay 100*((r_i)^t). If
you can only buy one item per month, what is the optimal order in which to buy them?

Difficult case:
You’re trying to sell equipments whose costs are depreciating. Item i depreciates at a rate of r_i < 1 per month, starting from $100, so if you sell it t months from now you will get 100*((r_i)^t). If
you can only sell one item per month, what is the optimal order in which to sell them?



9 comments:

  1. Are all items priced at $100? If they are, what's wrong with buying (and selling) the one with highest r_i first (and then in order of decreasing r_i)?

    Put more formally, considering n items, I would use a grid:
    1,(1+r1),(1+r1)^2,.....(1+r1)^n-1
    .
    .
    1,(1+rn),(1+rn)^2,.....(1+rn)^n-1

    The question is now to select one no. from each row and column to minimise the sum. It can be proven that this happens when you select in order of decreasing r_i.

    I feel like I'm missing something big here.. What part of above is incorrect?

    ReplyDelete
    Replies
    1. it is correct, it is a greedy solution. the solution is simple, i think it is the correctness proof that requires some clever arguments

      Delete
    2. For the selling case, consider the following rates( in absolute terms ) :
      99, 99, 1, 0.5

      If you sell them in order of decreasing rates, you will get the following returns :
      100/(1) + 100/(100) + 100/(2*2) + 100/(1.5*1.5*1.5 ) = 155.63

      This is not the best selling sequence. A better sequence is : ( 99, 1, 0.5, 99 )
      100/(1) + 100/(2) + 100/(1.5*1.5) + 100/(100*100*100 ) = 194.44

      Delete
  2. For the selling case, I think, we'd need to select in the order of increasing r_i. Since, we're trying to maximise the sum in that case. Correct?

    ReplyDelete
  3. How to solve the second part apart from an exponential method

    ReplyDelete
  4. just a thought, is there an optimized way, even if initial prices of items differ ? like p,q,r,...instead of all being 100. i guess we should seek the sum of the entire column instead of just looking for r_i

    ReplyDelete
  5. For selling:

    I think we should calculate decrease in price at each time step for each remaining item and sell the one which might depreciate the most in value if we do not sell it immediately. This way we are greedily minimizing the total loss incurred.

    Proof doesn't seem to be obvious, but it works on toy cases I constructed. Has anyone proved this or has a link to a solution?

    ReplyDelete
  6. what happens if the cost of each of the items are different ??
    My hypothesis is that we can, while buying, make a grid similar to what has been suggested by John and buy the most expensive item each month, deleting that row and column every month. In the limiting case of all items costing the same, the solution reduces to that of John.

    ReplyDelete
  7. what happens if the cost of each of the items are different ??
    My hypothesis is that we can, while buying, make a grid similar to what has been suggested by John and buy the most expensive item each month, deleting that row and column every month. In the limiting case of all items costing the same, the solution reduces to that of John.

    ReplyDelete