CSE Blog - quant, math, computer science puzzles

Source: Interview Street CodeSprint (slightly modified) Problem: One of the basics of Computer Science is knowing how numbers are represented in 2's complement. Imagine that you write down all numbers between A and B inclusive in 2's complement representation using 32 bits. How many 1's will you write down in all ? Input: Two integers A and B Output: The number of 1s Constraints: -2^31 <= A <= B <= 2^31 - 1 Find the asymptotically optimal algorithm.

Source: Quora - Asked in a Google Interview Problem: Using only a four-minute hourglass and a seven-minute hourglass, measure exactly nine minutes–without the process taking longer than nine minutes. Bonus made-up Question: Can you come up with a generalized solution of the hour glass problem? This is a more involved version of  the "Die Hard III Problem: A classic water bottle riddle. How to produce exactly 4 gallons with a 3 and a 5 gallon pan" whose solution can be found here Update: (26/12/2012): Assume that equal amount of sand slipped down measures equal intervals of time, i.e. amount of sand slipped to measure the first minute is same as the last minute. Solution posted by Gold and Iron (Nikhil Pandey, CSE IITB 2009 Alumnus), Mohit Johari (Civil IITB 2011 Alumnus) , Nikhil Simha R (Amazon India SDE, CSE IITB 2012 Alumnus)  and Sravan Kumar (EE IITB Final Year Student) in comments!

Source: Posted at " Post a Question " Problem: Two players compete in the following game: There is a pile containing n chips; the first player removes any number of chips except that he cannot take the whole pile. From then on, the players alternate moves, each person removing one or more chips but not more than twice as many chips as the preceding player has taken. The player who removes the last chip wins. (For example, suppose that n = 11; player A removes 3 chips; player B may remove up to 6 chips, and he takes 1. There remain 7 chips; player A may take 1 or 2 chips, and he takes 2; player B may remove up to 4, and he picks up 1. There remain 4 chips; player A now takes 1; player B must take at least one chip and player A wins in the his next chance. What is the best move for the first player to ensure his win if possible if there are initially n chips?

200th Puzzle of the CSE Blog Source: I got hold of the super awesome book I read 6 years back: "A Path to Combinatorics for Undergraduates: Counting Strategies" . A must have for any math/olympiad enthusiast (Flipkart link to Imported Edition and Indian Edition ) - Example 5.8 - USAMO 1990 Problem: Let n be a positive integer. Find the number of positive integers whose base n representation consists of distinct digits with the property that except for the leftmost digit, every digit differs by +1 or -1 from some digit further to the left. Update (26/12/2012): No correct solution provided. Solution posted by me in comments!

Source: 40 Puzzles and Problems in Probability and Mathematical Statistics (Interesting book by Wolfgang Schwarz) Inspiration: This problem demonstrates clearly the shortcomings of out grading system through exams Problem: Peter has an IQ of 90 whereas the IQ of Paula is 110. However, due to unsystematic biological or psychological day-to-day variation that is unrelated to the IQ per se, any single measurement of either IQ is distorted by an independent additive measurement error that has a zero-mean normal distribution with some variance. For example, if Paula’s IQ were measured repeatedly, the outcomes would be normally distributed with a mean of 110 (her “true” IQ) and some standard deviation. Suppose that either Peter or Paula is selected at random (p = 0.5), and his/her IQ is measured. You do not know who was selected, but you are told that the result of this first measurement is 105. Now the same person —whose identity is unknown to you — is measured a secon...

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!