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. Solution: Highlight the part between the * symbols for the answer. * Answer: 4. This is the Erdos-Szekeres theorem: any sequence of (a-1)(b-1) + 1 distinct numbers contains an increasing subsequence of length a or a decreasing subsequence of length b. With 10 = 3*3 + 1 soldiers, some monotone subsequence of length 4 always exists. Quick proof: label each soldier with (i, d) = (length of the longest increasing subsequence ending at him, longest decreasing one). If two soldiers got the same label, the taller-later / shorter-later comparison would extend one of the two subsequences - so all labels are distinct. If no monotone subsequence had length 4, all lab...

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 Solution: H...

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? Solution: Highlight the part between the * symbols for the answer. * Part I (12 people): cut along the radii pointing at the 12 hour marks - they are evenly spaced at 360/12 = 30 degrees, giving 12 equal slices. Part II (11 people): use the 11 moments in 12 hours when the hour and minute hands exactly overlap (12:00, ~1:05:27, ~2:10:54, ..., ~10:54:33). The minute hand gains 330 degrees per hour on the hour hand, so successive overlaps are 12/11 hours apart, and the overlap direction advances by exactly 360/11 degrees each time. Those 11 radii are therefore equally spaced - cutting along them divides the pizza into 11 equal slices. Bonus extension from the comments: minute and second hands overlap 59 times an hour - the ...

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? Solution: Highlight the part between the * symbols for the answer. * Buying (appreciating, r_i > 1):...

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. Solution: Posted by GoKu in comments!

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). Solution: Posted by Alex_IITD in comments!

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 Solution: Highlight the part between the * symbols for the answer. * First, the whole colouring is forced into one shape: pick any G > 1 and let gold = multiples of G, silver = everything else. Proof: 1 is silver (if 1 were gold, then silver x 1 would have to be gold by rule 2 - contradiction). Let G be the smallest gold number, so 1..G-1 are silver. Rule 1 (silver + gold = silver) then makes every non-multiple of G silver (write it as kG + r, 0 < r...