CSE Blog - quant, math, computer science puzzles

Source:  Alok Goyal's Puzzle Page Problem: In a line up of 10 soldiers, what is the least number of soldiers that can be picked in order of either ascending or descending heights? Assume that no two soldiers have the same height. Soldiers can be picked from anywhere in the line, but their order of standing cannot be changed.

Source: Sent to me by Prateek Chandra Jha (IIT Bombay) Problem: This problem is inspired by the Cheryl's Birthday Puzzle ( FB Post , Guardian Link ). Paul, Sam and Dean are assigned the task of figuring out two numbers. They get the following information: Both numbers are integers between (including) 1 and 1000 Both numbers may also be identical. Paul is told the product of the two numbers, Sam the sum and Dean the difference. After receiving their number, the following conversation takes place: Paul: I do not know the two numbers. Sam: You did not have to tell me that, I already knew that. Paul: Then I now know the two numbers. Sam: I also know them. Dean: I do not know the two numbers. I can only guess one which may probably be correct but I am not sure. Paul: I know which one you are assuming but it is incorrect. Dean: Ok, I also know the two numbers. What are the two numbers? Disclaimer: Its not a puzzle for 14-15 year olds like Cheryl's

Source: Alok Goyal Puzzle Page ( http://alokgoyal1971.com/ ) . Alok is ex-IIT Delhi, Partner at Helion VC Problem: Part I (Easy): Using a clock, divide a pizza among 12 people Part II (Difficult): Using a clock, divide a pizza among 11 people?

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?

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.

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).

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