Posts

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?

Box in Box problem

Source: Sent to me by Sudeep Kamath Problem: Airline check-in baggage has size restriction by ​so-called ​linear dimension: length + breadth + height should not exceed 62 inches. Prove that you can't "cheat" by packing a box with higher linear dimension into a box with ​lower​ linear dimension.

Fibonacci Multiple Puzzle

Source: Mailed to me by Kushagra Singhal, Ex-IIT Kanpur, PhD Student at University of Illinois at Urbana-Champaign Problem: Prove that for any positive K and a natural number n, every (n*K)th number in the Fibonacci sequence is a multiple of the Kth number in the Fibonacci sequence. More formally, for any natural number n, let F(n) denote Fibonacci number n. That is, F(0) = 0, F(1) = 1, and F(n+2) = F(n+1) + F(n). Prove that for any positive K and natural n, F(n*K) is a multiple of F(K).

Gold Silver Numbers Puzzle

Source: Mailed to me by JDGM ("regular commenter JDGM") Problem: The integers greater than zero are painted such that: • every number is either gold or silver. • both paints are used. • silver number + gold number = silver number • silver number * gold number = gold number Given only this information, for each of the following decide whether it is a gold number, a silver number, or could be either: 1.) gold number * gold number 2.) gold number + gold number 3.) silver number * silver number 4.) silver number + silver number

Mathematics of SET game

Source: Sent to me by Pritish Kamath ( http://www.mit.edu/~pritish/ ) Problem: Have you ever played "SET"? You have to play it. http://www.setgame.com/learn_play http://www.setgame.com/sites/default/files/Tutorials/tutorial/SetTutorial.swf Even if you have not played the game, the game can be stated in a more abstract way as follows: There are 12 points presented in  F 3 4  and the first person to observe a "line" amongst the 12 given points gets a score. Then the 3 points forming the line are removed, and 3 random fresh points are added. Problem 1: How many points in  F 3 4  are needed to be sure that there exists a line among them? Problem 2: Given 12 random points in  F 3 4 , what is the probability that there exists a line among them? Disclaimer: We have not solved the problem yet. It can be very difficult or very easy. Update (22/12/14): It turns out to be a very very difficult problem. Paper: http://www.math.rutgers.edu/~maclag...

Expected Number of Attempts - Broken Coffee Machine

Source:   Mind Your Decisions Blog Related Problem:   Expected Length of Last Straw - Breaking the back of a Camel - CSE Blog Problem: Your boss tells you to bring him a cup of coffee from the company vending machine. The problem is the machine is broken. When you press the button for a drink, it will randomly fill a percentage of the cup (between 0 and 100 percent). You know you need to bring a full cup back to your boss. What’s the expected number of times you will have to fill the cup? Example:  The machine fills the cup 10 percent, then 30 percent, then 80 percent–>the cup is full plus 20 percent that you throw away or drink yourself. It took 3 fills of the cup.