CSE Blog - quant, math, computer science puzzles

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!

Source: Quantnet Forum Problem: There is a calculator in which all digits(0-9) and the basic arithmetic operators(+,-,*,/) are disabled. However other scientific functions are operational like exp, log, sin, cos, arctan, etc. The calculator currently displays a 0. Convert this first to 2 and then to 3. Update (8/7/2012): Solution posted in comments by Siddhartha, Sumit, Salman Khan and Kapil Dubey. Thanks. Interesting generalisation proposed by Siddhartha.

Source: IBM Ponder This July 2012 Problem very similar to   CSE Blog: Painting Coloured Balls  ( Link:  http://pratikpoddarcse.blogspot.in/2010/10/painting-coloured-balls.html  ) Problem: Alice and Bob are playing two games: they start simultaneously and the first one to win his game is the winner. Alice is given an urn with N balls, colored in N different colors and in every second she randomly picks two balls, colors the first ball in the color of the second ball and returns both to the urn. Her game is over once all the balls in the urn have the same color. Bob is given an urn with M balls, all colorless, and in every second he picks a random ball, color it, and puts it back to the urn. Bob's game is over once all his balls are colored. Our question is: what are the possible values of M for which (on average) Bob is expected to lose for N=80 and win for N=81?  We ask for possible Ms for which the expected time of Bob's game is smaller than Alice's...

Source: Nick's Mathematical Puzzles Problem: Let n be a positive integer, and let S n  = {n 2  + 1, n 2  + 2, ... , (n + 1) 2 }.  Find, in terms of n, the cardinality of the set of pairwise products of distinct elements of S n . For example, S 2  = {5, 6, 7, 8, 9}, 5 × 6 = 6 × 5 = 30, 5 × 7 = 7 × 5 = 35, 5 × 8 = 8 × 5 = 40, 5 × 9 = 9 × 5 = 45, 6 × 7 = 7 × 6 = 42, 6 × 8 = 8 × 6 = 48, 6 × 9 = 9 × 6 = 54, 7 × 8 = 8 × 7 = 56, 7 × 9 = 9 × 7 = 63, 8 × 9 = 9 × 8 = 72, and the required cardinality is 10. Update (Sept 12, 2012): Solution posted by Parakram Majumdar (CSE IITB Alumnus, Morgan Stanley Strats and Modeling Analyst) - Detailed explanation of the solution by unknown in comments!