CSE Blog - quant, math, computer science puzzles

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. Solution: Highlight the part between the * symbols for the answer. * Answer: e = 2.71828... fills. Let X_i be the fraction dispensed on press i (uniform on [0,1]) and S_k = X_1 + ... + X_k. You press a (k+1)-th time exactly when S_k < 1, so the expected number of presses is 1 + su...

Source: Puzzle Tweeter who took it from Mind your decisions Problem: A camel is loaded with straws until it's back breaks. Each straw has a weight uniformly distributed between 0 and 1, independent of other straws. The camel's back breaks as soon as the total weight of all the straws exceeds 1. Find the expected weight of the last straw that breaks the camel's back. Update (18th June 2014): Solution posted by me (Pratik Poddar) in comments

Source: Mailed by Sudeep Kamath (EECS PhD Student, UC Berkeley, EE IITB 2008 Alumnus) Problem: A is a 300 x 300 matrix with 17 on the diagonal, and the rest of the entries being 11. What is det (A) ? Update: (21 June 2014): Solution posted by Gowtham R (Stanford), Justin Rising, Pavan Bharadwaj, Hansaplatz and gaurushh in comments! Thanks

Source: Mailed to me by Sudeep Kamath (PhD Student, UC at Berkeley, EE IITB Alumnus 2008) Problem: Tricky Question. Let f be a continuous, real-valued function on reals such that limit_{n \rightarrow \infty} f(nx) = 0 for all real x. Show limit_{x\rightarrow \infty} f(x) = 0. Solution: Highlight the part between the * symbols for the answer. * Proof (Baire category theorem; n ranges over the positive integers). Fix eps > 0 and for N = 1,2,... let E_N = { x >= 1 : |f(nx)| = N }. Each E_N is closed: it is an intersection of preimages of the closed interval [-eps,eps] under the continuous maps x -> f(nx). Since f(nx) -> 0 for every real x, every x >= 1 belongs to some E_N, so the E_N cover [1, infinity). By Baire's theorem some E_N has non-empty interior, i.e. it contains a closed interval [a,b] with 1 = N of the intervals [na, nb]. Now (n+1)a = a/(b-a), so beyond n0 = max(N, ceil(a/(b-a))) the intervals [na,nb] overlap or touch and their union contains the whole hal...

Source:  www.puzzletweeter.com Problem: Let A,B be 2x2 matrices with integer entries. Suppose the matrices A,A+B,A+2B,A+3B,A+4B are all invertible and their inverses are also integer matrices. Then show that A+5B is invertible and it's inverse is an integer matrix. Update (24 June 2014): Solution: Posted by Yashoteja Prabhu (Ex-RA at Microsoft Research, IITB CSE 2011 Alumnus) and Sanchit Gupta in comments!

Source: Introduced to me by Sudeep Kamath (PhD Student, UC at Berkeley, EE IITB Alumnus 2008) Problem: An N by N matrix M has entries in {0,1} such that all the 1's in a row appear consecutively. Show that determinant of M is -1 or 0 or 1. Disclaimer: I could not solve it but I have an awesome solution sent by Pritish Kamath (MSR Research Assistant, CSE IITB Alumnus 2012) Update (2/4/2013): Solution posted by Amol Sahasrabudhe (IITB 2004 Alumnus, Ex-Morgan Stanley Quant Associate, Deutsche Bank Quant Associate) and Piyush Sao (EE IITM Alumnus, Georgia Tech Grad Student) in comments! Thanks a ton. I have posted the solution provided by Pritish Kamath (MSR Research Assistant, CSE IITB Alumnus 2012). All three solutions are essentially the same.

Source: Asked to me by Sankeerth Rao (EE IITB 4th year Student) Problem: Given any two triangles in a plane construct a line which bisects both their areas. Background: In fact the existence of such a line is true in a very general setting - for any two polygons in a plane there exists a line which bisects both their areas. In fact its true for any two Jordan measurable sets in a plane. Further generalized version is called the Ham Sandwich Theorem and is proved using Borsuk Ulam Theorem. Solution: Highlight the part between the * symbols for the answer. * Key fact: in every direction there is a line that bisects a given triangle's area, and it moves continuously as the direction rotates. (For direction theta, sweep a line of that slope across the triangle; the area on one side goes continuously from 0 to the full area, so some position halves it - and the halving position varies continuously with theta.) Now parameterize by angle theta in [0, pi): let L(theta) be the bise...

Source: Wikipedia article on Peg Solitaire Problem: The European version of the popular game "Brainvita" (or "Peg Solitaire") looks as follows: Y Y O O O Y Y Y O O O O O Y O O O O O O O O O O T O O O O O O O O O O Y O O O O O Y Y Y O O O Y Y Prove that the initial configuration as shown in the representation is not solvable. Background: The game fills the entire board with pegs except for the central hole. The objective is, making valid moves, to empty the entire board except for a solitary peg. A valid move is to jump a peg orthogonally over an adjacent peg into a hole two positions away and then to remove the jumped peg. Similar Problems: Rubik's Cube Sam Loyd Puzzle Solvability Update: Solution posted by Pritish Kamath (CSE IITB 2012 Alumnus, Assistant Researcher MSR Bangalore) in comments!

Source: Posted by Shubham Agarwal (B.Tech CSE, NIT Raipur) on his blog Problem: Prove the following inequality:    1/2 . 3/4 . 5/6 . .... 99/100 < 1/10 Bonus: Prove the generalized inequality:     1/2 . 3/4 . 5/6 . .... (2n-1)/2n < 1 / sqrt(2n) Update: (12 Sep 2012) 3 different solutions posted in comments by sriram, chetan, dvdreddy, insomniac and sarat Update: ( 4 Feb 2013) Solution by Sriram and Chetan needs explanation. So, we have 2 different solutions by  dvdreddy, insomniac and sarat.

Source: http://www.stanford.edu/~gowthamr/puzzles.html Problem: Suppose the starting point of a particle undergoing Brownian motion in 2 dimensions is chosen uniformly at random on an imaginary circle C_1. Suppose there is a solid circle C_2 completely inside C_1, not necessarily concentric. Show that the particle hits the boundary of C_2 with uniform distribution. Book: I strongly recommend the book by Steven Shreve for understanding Brownian Motion and its applications in Financial Modelling (Its expensive! Flipkart Link: Stochastic Calculus for Finance II ) Update (4th Feb 2013): Solution posted by me in comments!

Source: Discussions with BX Mumbai team on my flight from New York to Mumbai Problem: The flight from New York (Newark - EWR) to Mumbai (Bombay - BOM) takes the aerial route as shown in the figure. Why do the flights not take straightline distance to minimize cost? Hint: The answer is mathematical. Do not think of regulatory or political reasons. Update:  (19-07-2012) Assume earth is perfect sphere 

Source : Algo Muse, CSE, IIT Bombay Problem : An entry  a ij  in a matrix is called a  saddle point  if it is strictly greater than all the entries in the  i th row and strictly lesser than all entries in the  j th column or vice-versa. For example, the matrix shown below has two saddle points. What is the maximum number of saddle points an  n x n  matrix can have?  Update (December 14, 2011): Due to some reason I do not know of, the problem is not there on the Algo Muse website anymore. :P  Solution posted by Panna, Gold and Iron (Nikhil Pandey, CSE IITB 2009 Alumnus), Prasham Rambhia (Aero IITB Fifth Year Undergraduate Student, To be Morgan Stanley Quant) and Insomniac in comments!

Source : Quantnet Forums Problem : A question which is asked on interview in some software development companies. I guessed 3 natural numbers - x,y,z. You can ask me about two sums of these numbers with any coefficients - a,b,c. For example, you give me a, b and c and I tell you the result of the expression a*x+b*y+c*z. Give me the algorithm to find x,y and z. Observation/Hint : Irrespective of whether you get the solution, its interesting that you are solving a system of three variables using two equations. You are able to do that because the coefficient in the second equation depends on the answer of the first equation. :) Update (November 6, 2011): Solution : Posted by Harsh Pareek (Graduate Student at UT Austin, CSE IITB 2011 Alumnus), Rudradev Basak (IITD CSE Senior Undergraduate) and AnonymousD in comments!

Source: A linear algebra problem book Problem: Find the function f   ( member of span {1, sin x, cos x} ) that minimizes norm of ( sin 2x − f(x) ), where the norm comes from the inner product < f , g > = integral over x from -pi to pi [ f(x)g(x) ] Update (Oct 30, 2011): Solution posted by Harsh Pareek (Graduate Student at UT Austin, CSE IITB 2011 Alumnus) in comments.

Source: Asked to me by Amol Sahasrabudhe (IITB 2004 Alumnus, Worked at Morgan Stanley Quant Division, Deutsche Bank) Problem: You are given 2n numbers ( 1 to n and 1 to n ). You have to arrange these numbers in a sequence such that between any two i `s , there exists exactly i-1 numbers. Is it possible for all n ? If no, what are the values of n for which this is possible? Disclaimer: I have not been able to solve it. Sudhanshu Tungare (IITB 2008 EE Alumnus, Morgan Stanley) claims to have a solution. Cheers! Update (November 1, 2011): Part solution posted by Nishant Totla (CSE IITB Senior Undergraduate), Richie and Sarat in comments! Complete solution posted by Siddhant Agarwal (EE IITB Alumnus, CMI Grad student) in comments! Thanks a ton.

Problem 1: Each cell in a square table contains a number. The sum of the two greatest numbers in each row is  a , and the sum of the two greatest numbers in each column is  b . Prove that  a = b . Problem 2:  Given some m x n table, and some numbers in its fields. You are allowed to change the sign in one row or one column simultaneously. Prove that You can obtain a table, with non-negative sums over each row and over each column. Update (11th June 2011): Solution to both problems posted by NG [Nikhil Garg (CSE IIT Delhi final year undergraduate student)] in comments! Thanks. Confession: I could never solve Problem 1 even after spending hours. :P :(

Source: Very interesting problem taken from Tanya Khovanova’s Math Blog Problem: I found this cute problem in the Russian book Sharygin Geometry Olympiad by Zaslavsky, Protasov and Sharygin. Find numbers p and q that satisfy the equation: x 2 + px + q = 0. The book asks you to find a mistake in the following solution: By Viète’s formulae we get a system of equations p + q = − p , pq = q . Solving the system we get two solutions: p = q = 0 and p = 1, q = −2. What is wrong with this solution? Update (26-05-2011) Solution: Posted by Sudeep Kamath  (EECS PhD Student, UC Berkeley, EE IITB 2008 Alumnus) in comments and of course on Tanya Khovanova’s Math Blog

Source: Quantnet Forums Problem: You are given a stick of length 1 and a supply of n identical needles of length h. Drop the n needles at random on the stick, subject to the following "needle discipline": needles should fit entirely within the stick (they cannot stick out). What is the probability that no two needles overlap? Let us assume that the stick is one-dimensional, so that the needles can only lie along the length of the stick. Update (26-05-2011) Solution: Posted by Siddhant Agarwal (EE IITB 2011 Alumnus), Ameya Ranade (CSE IITB 2009 Alumnus) and me in comments!

Source: Mailed to me by Sudeep Kamath  (EECS PhD Student, UC Berkeley, EE IITB 2008 Alumnus) Problem: Three people start with integer amounts a,b and c. In each round, each one tosses a fair coin. If not all faces are the same, the person with the different face gets a rupee from each of the other two. If all faces are the same, no money is exchanged. This process is repeated till one of them gets bankrupt. What is the expected number of rounds till the game ends? Related Problems: http://pratikpoddarcse.blogspot.com/2009/10/lets-say-keep-tossing-fair-coin-until.html http://pratikpoddarcse.blogspot.com/2010/11/source-credit-suisse-placement-test-at.html http://pratikpoddarcse.blogspot.com/2011/02/equal-heads-and-tail.html Update (15/03/2011): Hint: Given away by Sudeep. (* Define a martingale of the form Y_n=A_n*B_n*C_n + some other term (where A_n,B_n,C_n are the fortunes of the three players at time n). *) Solution: Posted by chera (Gaurav Sinha, IITK 1...

Problem: Design a 3-input 3-output logic circuit that negates the 3 signals. You have an infinite supply of AND and OR gates but only two NOT gates I have read and solved many problems like these. Can people post some similar interesting problems using gates. I was asked one such question in my Deutsche Bank Interview which I was not able to answer. Update(09/02/10): Solution: Solution posted by Sid in comments!! Update(23/06/14): Solution: Interesting link shared by divby0 in comments!