Sep 25, 2012

USA Maths Olympiad Problem - 200th Puzzle

200th Puzzle of the CSE Blog

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

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!

Sep 15, 2012

IQ Measurement Puzzle - Statistics Problem

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

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 second time.

a) What is your prediction for the outcome of this second measurement if standard deviation = 3?
b) Answer the same question if standard deviation = 20?

Update (Sep 15, 2012):
Minor change in the question as suggested by Akshay Soni

Update (5th Feb 2013):
Solution posted by Akshay Soni (IITB Mech Senior Undergraduate) , AB and Nikhil Simha R (Amazon India SDE, CSE IITB 2012 Alumnus) in comments! Rephrased and improved formatting of the solution and posted by me in comments!

Sep 11, 2012

Inequality Problem

Posted by Shubham Agarwal (B.Tech CSE, NIT Raipur) on his blog

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.

Sep 10, 2012

Brownian Motion in Circles Puzzle


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!

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...