Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Dec 23, 2011

Number of digits in 125^100

Source: Asked to me by Suman Kalyan Bera (M.Tech  Student IIT Delhi) on contact page

Problem:

How many digits does the number 125^100 have?

Very interesting problem and equally interesting solution :)

Update (25 December 2011):
You are not allowed to use your high school notes on values of log_10(2) or log_10(5)
Solution:
Posted by me in comments!

Array Problems - Contiguous Sum and Distinct Elements

Source: Posted by Algo Muse on contact page. Also posted on Algo Muse (December 2011) http://www.algomuse.appspot.com

Problem:

Two definitions:

1) Contiguous t-sum problem
Given an array A[1..n] and a number t as input, we want to find out if there exists a sub-array whose sum is t. For example, if the following array and t=8 is the input, the answer is YES since it contains the sub-array A[2..4] whose sum is t.

 1 4 -1 5 -8 5 -6 3 10 3

 2) Distinct-elements problem
Given an array A[1..n], find out if all the elements in the array are distinct. Return YES if all the numbers are distinct NO otherwise.

Real Problem:

Suppose we are given an algorithm that solves the t-sum problem in O(n) time. Design an algorithm that solves the distinct-elements problem in O(n) time.

Update (2nd January 2011):
Solution: Posted by Yashoteja (CSE IITB Alumnus, Microsoft Research RA) and Pseudonymous in comment. Thanks

Dec 19, 2011

Crossing the Road

Source: Quantnet Interview Questions




Problem:
If a car passes at the crosswalk on average every 10 seconds and you need 20 seconds to pass the road, how long does it take you on average to cross the road?

Note that since the problem is not very well specified, make reasonable assumptions to solve it. It would be fun if before solving mathematically, you try and guess a time estimate. :-)

Update (3rd January 2011):
Solution posted by Santosh Ananthakrishnan (EE Final Year DD Student IIT Bombay) and Animesh Saxena (Manager at Karvy Private Wealth) in comments!

Dec 16, 2011

Shortest Curve dividing Equilateral Triangle

Source: Asked to me by Dinesh Krithivasan (IITM Alumnus, Phd University of Michigan, Senior Qualcomm Engineer)

Finally a geometry problem for the blog. :) Thanks Dinesh! :)

Problem:
We have an equilateral triangle ABC of unit side length. We want to find a curve C of the smallest length that cuts this triangle into 2 halves of equal area. Obviously, the altitude of length sqrt(3)/2 will do the job but can we do better? Note that there is no other restriction on C - it need not pass through any of the triangle vertices for instance.






Dec 12, 2011

Matrix Saddle Points

Source: Algo Muse, CSE, IIT Bombay

Problem:
An entry aij in a matrix is called a saddle point if it is strictly greater than all the entries in the ith row and strictly lesser than all entries in the jth column or vice-versa. For example, the matrix shown below has two saddle points.

What is the maximum number of saddle points an nxn 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!

Dec 4, 2011

Rubik's Cube

Source: Asked to me by Piyush Goyal (CSE IITD Senior Undergraduate, To be Goldman Sachs Quant)

Problem:
Given a Rubik's Cube, find a path from centre of face to centre of cube going via each cell of cube only once.

Hint:
Its not possible. Try to prove it. Cheers!

Update (Dec 11, 2011):
Solution:
Posted in comments by: Ankush Agarwal (Senior Undergraduate, CSE, IITB), Prasham (Senior Undergraduate, Aero, IITB & To be Morgan Stanley Quant), Piyush Sao (EE IITM Alumnus, Georgia Tech Grad Student), Siddhartha, Rudradev Basak (Senior Undergraduate, CSE, IITD), Yashoteja (CSE IITB Alumnus, Microsoft Research RA), Kashyap (IITM), Gaurav Sinha (chera, IITK 1996 Graduate, Indian Revenue Service). Thanks!


Linked List Delete

Source: Asked to me by Ankush Jain (CSE IITB 2011 Alumnus, Morgan Stanley Quant)

Problem:
You are given a pointer to a node (not the tail node) in a singly linked list. Delete that node from the linked list. Write code in C.

Update (December 13, 2011):
Solution posted by Siddhartha in comments! Interesting comment by me in comments!

Nov 21, 2011

Numbers on a circle - Minimum sum of consecutive differences

Source: Asked to me by Anuj Jain (MFE Grad Student at Baruch College in New York, EE IITB 2010 Alumnus)

Problem:
Place the numbers 1, 2, ... 9 around a circle in the positions x_1, x_2, ..., x_9 so that the sum of difference between consecutive terms defined by
Sum over | x_{ i+1 } - x_{ i } | for i = 1, 2, ..., 9 is minimized (Note: x_10 is x_1).

Also count the number of such arrangements where the "sum of difference between consecutive terms" is minimum.

Update (December 13, 2011):
Solution: Partial Solution posted by Chiraag Juvekar (IITB EE Fifth year undergraduate, To be McKinsey Business Analyst) in comments! Complete solution posted by Rudradev Basak (IITD CSE Senior Undergraduate) and Gaurav Sinha (chera, IITK 1996 Graduate, Indian Revenue Service) in comments!

Update (June 22, 2014):
Very generic solution posted by Aashay Harlalka (IITB EE 2014, Two Roads Quantitative Analyst) in comments!

Nov 5, 2011

Guess 3 numbers


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!

Nov 3, 2011

Scaling a Square

Source: Saurabh Joshi, IIT Kanpur

Problem: On a table you have a square made of 4 coins at the corner at distance 1. So, the square is of size 1×1. In a valid move, you can choose any two coin let’s call them mirror and jumper. Now, you move the jumper in a new position which is its mirror image with respect to mirror. That is, imagine that mirror is a centre of a circle and the jumper is on the periphery. You move the jumper to a diagonally opposite point on that circle. With any number of valid moves, can you form a square of size 2×2? If yes, how? If no, why not?

Update (November 4, 2011)
Solution: Posted by Siddhant Agarwal (EE IITB Alumnus, CMI Grad student) and Rudradev Basak (IITD CSE Senior Undergraduate) in comments!


Nov 1, 2011

Divisibility of 111...1111


Source: Asked to Russian 7th Graders - Taken from Wild For Math Blog

Problem:
Is it true that among the numbers consisting of only "1"s (1; 11; 111; 1111; etc.) there is a number (maybe many) that is divisible by 572,003?

Here 572,003 is taken arbitrarily. Is it true for all numbers?

Update (November 02, 2011):
Solution posted in comments by NG a.k.a Nikhil Garg (IITD CSE Senior Undergraduate), Rudradev Basak (IITD CSE Senior Undergraduate, IMO Bronze Medalist), Yashoteja Prabhu (RA at Microsoft Research, IITB CSE 2011 Alumnus), Siva, Garvit Juniwal (IITB CSE Senior Undergraduate)! Thanks



Oct 31, 2011

Sphagetti Breakfast

Source: Very standard problem in Quant interviews (Taken from quantnet, xkcd forums)



Problem:
A bowl of spaghetti contains n strands. Thor picks two ends at random and joins them together. He does this until no ends remain.

What is the
a) expected number of spaghetti loops in the bowl?
b) expected average length of the loops? (in strands)
c) expected number of k-hoops? ( a k-hoop is a loop made from k strands)

Oct 13, 2011

Distinct numbers in a sample draw


Source: Asked to me by Chinmay Chouhan, Junior Undergraduate, CSE IITB

Problem:
Given the set of numbers from 1 to n: { 1, 2, 3 .. n }

We draw n numbers randomly (with uniform distribution) from this set (with replacement). What is the expected number of distinct values that we would draw?

Update (Oct 30, 2011):
Solution posted by Yashoteja Prabhu (RA at Microsoft Research, IITB CSE 2011 Alumnus), Garvit Juniwal (IITB CSE Senior Undergraduate), Dinesh Krithivasan (IITM Alumnus, Phd University of Michigan, Senior Qualcomm Engineer), Nikhil Garg (IITD CSE Senior Undergraduate) and Avinash in comments!



Oct 11, 2011

Function Inner Product

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.

Sep 11, 2011

Difference between foo(void) and foo()

Source: http://stackoverflow.com/

Problem:
Consider these two function definitions
void foo(){ ... }
void foo(void){ ..... }
What is the difference between these two functions?

Hint: The answer depends whether this is C code or C++ code.

Sep 10, 2011

C code 32 bit vs 64 bit

Source: http://www.gowrikumar.com

Problem:
The following C program segfaults of IA-64, but works fine on IA-32.

  int main()
  {
      int* p;
      p = (int*)malloc(sizeof(int));
      *p = 10;
      return 0;
  }
 
Update (Oct 30, 2011):
Wrong problem. Sorry for the trouble.

C++ Macro Concatenation

Source: http://www.gowrikumar.com
Problem: What is the output of the following C++ code?
  #include <stdio.h>
  #define f(a,b) a##b
  #define g(a)   #a
  #define h(a) g(a)

  int main()
  {
          printf("%s\n",h(f(1,2)));
          printf("%s\n",g(f(1,2)));
          return 0;
  }


Update (14 Sept 2011):

Solution posted in comments by Prathmesh Prabhu (CSE IITB 2010 Alumnus and Wisonsin Madison II-year Graduate Student)


Sep 4, 2011

Arrange in a Sequence

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.

Aug 27, 2011

Football Board

Source: The Hidden Mathematics of Sport

Problems:

Football tables have been the basis of many a brainteaser over the years. These two puzzles ask you to work out what the scores were in all matches played so far this season.

Puzzle 1: Each team played the others once, what were the scores in each match (2 points for a win, 1 for a draw)?




PlayedGoals forGoals againstPoints
United2103
City2212
Albion2021


Puzzle 2: The league table below got smudged in the rain, and is only partly legible. Eventually each team will play the others once, but the tournament isn't over yet. Can you find all the results?




PlayedWonLostDrawnGoals forGoals against Points
Athletic32**4 4*
Rovers*1*03 0*
Town***01 1*
Wanderers***** **


Update (27 Aug 2011):
Solution posted by Gautam Kamath (EE, Senior Undergraduate, IIT Bombay) in comments!

Aug 17, 2011

Sacred Right Pan - IMO 2011 Problem

Source: IMO 2011 Problem (sent to me by Dinesh Dharme, CSE IITB 2011 Alumnus, Credit Suisse Analyst)


Problem:
Let n > 0 be an integer. We are given a balance and n weights of weight 2^0, 2^1, . . . , 2^(n−1). We are to place each of the n weights on the balance, one after another, in such a way that the right pan is never heavier than the left pan. At each step we choose one of the weights that has not yet been placed on the balance, and place it on either the left pan or the right pan, until all of the weights have been placed.

Determine the number of ways in which this can be done.

Disclaimer:
As expected from an IMO problem, very difficult! But interesting solutions at www.math.leidenuniv.nl/~desmit/pop/2011_imo_final6.pdf

Update  (25 Aug 2011):
I did not write in clearly in the post. One of the solutions provided in the pdf is an oral 3 line solution to the problem. It cannot get smaller than this :P. Even if you have solved the problem, do have a look at the pdf

Aug 16, 2011

Increasing Sequence in Dice


Source: A book on probability puzzles

Problem:
Suppose we play a game with a die where we roll and sum our rolls as long as we keep rolling larger values. For instance, we might roll a sequence like 1-3-4 and then roll a 2, so our sum would be 8. If we roll a 6 first, then we’re through and our sum is 6.

Three questions about this game:

(a) What is the expected value of the sum?

(b) What is the expected value of the number of rolls?

(c) If the game is played with an n-sided die, what happens to the expected number of rolls as n approaches infinity?

Update (Aug 31, 2011)
Solution posted by Gaurav Sinha (chera, IITK 1996 Graduate, Indian Revenue Service) and Siva in comments!


Jul 6, 2011

Expectation of Max Frequency

Source: Sent to me by Nikhil Garg (CSE Senior Undergrad, IITD) - who got this from Rudradev Basak

Problem:
There are K balls in a sack numbered 1 to K. Bob chooses a ball at random notes down its number and puts it back in sack. He does this process for N times. What is the expected value of the frequency of the most frequent element ?

Best of Luck! I do not have the solution. So, tell me if you get one. Thanks.

Jun 9, 2011

Coin Chain Reaction

Source: Asked to me by Prateek Srivastava (IITB CSE Alumnus 2010 and Yahoo! Software Engineer) (also asked in a quant firm placement test)

Problem:
We have an unlimited number of dice at our disposal. Let's roll the die. If the outcome is 1, 2, or 3, we stop; otherwise, if it is 4, 5, or 6, a corresponding number of dice are rolled. For example, if the first roll gives 5, then we roll 5 dice, and so on. This procedure continues for every rolled dice whose outcome is 4, 5, or 6. Let N denote the N-th round of rolls. What is the total expected value at the end of the N-th round of rolls?

Update (17 July 2011):
Solution posted by Unknown in comments. There is a slight ambiguity in the problem statement, so please do not waste a lot of time. Thanks.

Jun 3, 2011

Moscow Math Olympiad Problems

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 :(

May 26, 2011

Coloured Run of Cards

Source: http://www.quantnet.com/forum/threads/colored-runs-of-cards.6508/

Problem:
There are 26 black(B) and 26 red(R) cards in a standard deck. A run is a maximum block of consecutive cards of the same color. For example, a sequence RRRRBBBRBRB of only 11 cards has
6 runs; namely, RRRR, BBB, R, B, R, B.

Find the expected number of runs in a shuffled deck of cards.

Update (29-05-2011):
Solution:
Posted by Siddhant Agarwal (EE IITB 2011 Alumnus) in comments!
Select the text between * to see the solution.
* Let us have n red cards and n black cards. Consider any sequence X_1,X_2..X_2n. Now define
Y_1 = 1,
Y_i = 1 if X_i and X_(i-1) are of diff colours
Y_i = 0 otherwise.

Clearly we have to find E[Y_1 + ..+Y_2n]
E[Y_1] = 1 by def.
E[Y_i] = E[Y_j] for all i,j>=2
by symmetry.

Also E[Y_i] = $2*(\binom{2n-2}{n-1})/($\binom{2n}{n})

so ans = 1+(2n-1)*E[Y_i] = n+1 *

May 24, 2011

Bad BarCode


Source: IBM Ponder This - May 2011 Problem

Problem:
A barcode is composed of a series of variable-width white and black bars.
One of the important features of the barcode is that no bar be too wide; otherwise, the reader might get out of synchronization. Suppose we use the following barcode system, where we take a completely random sequence of bits and use it to build the bars. For example, the 7-bit-long sequence 0111001 will generate four bars of varying lengths: white(1), black(3), white(2), black(1). Such a system will generate, every once in a while, bars that are too wide. Let's call any black bar whose width is 20 bits or more a "bad bar".
What is the expected number of bits in the bars that are between two adjacent bad bars?

Other IBM Ponder This Problems on the blog:
http://pratikpoddarcse.blogspot.com/2010/01/ibm-ponder-this-january-2010-puzzle.html
http://pratikpoddarcse.blogspot.com/2009/11/ibm-ponder-this-november-challenge.html
http://pratikpoddarcse.blogspot.com/2009/10/ibm-ponder-this-puzzle.html

Update (29-05-2011)
Solution:
Posted by me in comments! (This solution was accepted by IBM Research as a correct solution).




May 23, 2011

Wrong Solution

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: x2 + 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


May 16, 2011

Need for Needles

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!

Apr 11, 2011

Smallest Number in Decreasing Sequence

Source: Quantnet Forums

Problem:
You pick random numbers between 0 and 1 (uniformly at random) x1, x2, x3.. as long as they keep decreasing x1 > x2 > x3 > ...

What is the expected value of the smallest number you pick?

Update (26-05-2011):
Solution: Posted by Gaurav Sinha (chera, IITK 1996 Graduate, Indian Revenue Service) in comments!
Interesting approach (although wrong) by Gautam Kamath (EE, Senior Undergraduate, IIT Bombay) in comments - Corrected by me!

Mar 20, 2011

Keynesian beauty contest

Problem:
Pick a number from 0 to 100. The winner is the person who chooses the number closest to 2/3rds of the group's average response. What is the rational answer?

Related thought:
Once you get the solution, you would be surprised to see the implications. A Keynesian beauty contest is a concept developed by John Maynard Keynes and introduced in Chapter 12 of his work, "General Theory of Employment Interest and Money" (1936), to explain price fluctuations in equity markets. Read wikipedia article to appreciate it: http://en.wikipedia.org/wiki/Keynesian_beauty_contest

Update: (23 March 2011):
Solution posted by Gautam Kamath (EE, Senior Undergraduate, IIT Bombay) in comments!

Mar 13, 2011

Dividing a Plane

Source: Concrete Mathematics, Donald Knuth

Problem:
Let's say we have a plane. Draw N straight lines on the plane, any way you wish. Try to divide the plane into as many different regions as possible. How many regions is that? For example, if we draw 1 line on the plane, we can divide it into two regions. If we draw 2 lines, we can divide it into four regions.

Followup questions:
Source: http://skepticsplay.blogspot.com/
Draw N perfect circles on a plane, of any size, anywhere you want. Into how many regions can you divide the plane? Next, draw N perfect ellipses on another plane. Into how many regions can you divide the plane?

King's Poisonous Wine II

Source: Puzzle Corner, Australian Mathematical Society

Problem: The king has 500 barrels of wine, but one of them is poisoned. Anyone drinking the poisoned wine will die within 12 hours. The king has four prisoners whom he is willing to sacrifice in order to find the poisoned barrel. Can this be done within 48 hours?

Related Problem:
King's Poisonous Wine Puzzle - CSE Blog

Update (16/03/2011):
Solution posted by Tejas Hiremani (IITB EE Alumnus, Goldman Sachs Quant), Siddhant Agarwal (IITB EE Senior Undergraduate), Mehul Tikekar (IITB EE Alumnus, MIT PhD Candidate) and Gaurav Sinha (chera, IITK 1996 Graduate, Indian Revenue Service) in comments!

Feb 25, 2011

Coin Toss Bankruptcy

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 1996 Graduate, Indian Revenue Service) in comments!

Derangement - Complete FAIL!

Source: Interview at one of the quant firms

Problem:
As posted in problems this and this, this is an extension to the derangement problem.
There are n men, n hats, one hat belonging to each person. A random permutation of hats is picked by the men. What is the probability that no person gets the correct hat?

Update (March 6, 2011)
Solution: Posted by Vipul Verma (Engineer at Portware, IIT KGP and University of South California Alumnus) in comments!

Feb 6, 2011

Equal Heads and Tail

Source: Posted by chera (Gaurav Sinha, IITK 1996 Graduate, Indian Revenue Service) in comments on Consecutive Heads Problem

Problem:
Suppose you have a fair coin and you toss it until you have got equal number of heads and tails. What is the expected number of tosses? Note that probability that the game stops in odd number of tosses is 0. The probability that the game stops in 2 tosses = 0.5

Solution:
Different solutions posted by Kalyan Parhi (EE IITB Alumnus), Abhash, Siva, Gaurav Sinha (CSE IITK 1996 Alumnus, Indian Revenue Service), Dinesh Krithivasan (IITM Alumnus, Phd University of Michigan, Senior Qualcomm Engineer) in comments!

Jan 31, 2011

Comparison without relational operators

Source: Quant interview at Religare Technova

Problem: Write a C program to compare two integers without using relational operators (== != < <= > >=)
 

Jan 30, 2011

Sum of 2001 powers of digits

Source: Problems on Algorithms (Ian Parberry and William Gasarch)

Problem: 
Let f be a function which takes a number x (number with say n digits, digit i represented by d_i) as input and outputs sum of the 2001 powers of the digits. So, f(327)=3^2001 + 2^2001 + 7^2001. Show that for any x, the set {f(x), f(f(x)), f(f(f(x))),..} is finite.

Update (31 January 2011)
Solution: Posted by Sudeep Kamath (UC Berkeley PhD Student & EE IITB Alumnus) in comments!

Jan 27, 2011

Expectation of 2^(Cycle Length)

Source: Mailed to me by Sudeep Kamath (EECS PhD Student, UC Berkeley, EE IITB 2008 Alumnus), Taken from Anand Sarwate (Postdoc at UC San Diego, PhD from UC Berkeley)

Problem:
Given a permutation p of length n, let c(p) be the number of cycles in p. Suppose p is drawn uniformly from the set of all permutations. Show that
Expectation of 2 raised to the power of number of cycles is n+1, i.e E[2^c(p)]=(n+1)

Hint:
1) There is no high funda group theory/number theory involved. I could solve this in 15 minutes \m/ \m/
2) After you are done, you might want to read this (*Spoiler Alert*)

Solution:
Hint posted by Nikhil Garg (CSE, IIT Delhi third year undergraduate student) in comments! Solution posted by Kalyan in comments! Kalyan's comment explained in detail by me in comments! A simpler solution posted by Gaurav Sinha (chera) (CSE IITK 1996 Alumnus, Indian Revenue Service) in comments!

Jan 20, 2011

CMU Puzzle Toad: Abduction


Source: CMU Puzzle Toad

Problem: Farmer Brown is standing in the middle of his perfectly circular field feeling very content. It is midnight and there is no moon and unknown to the farmer, Martian zoologists are landing randomly at points on the circumference of his field. They land at one minute intervals, starting at midnight. As soon as there are martians at points A,B,C such that triangle ABC contains the center of the field, Farmer Brown will be teleported to the waiting space-ship and transported to spend the rest of his life as an exhibit in a Martian zoo. What is the expected time until he is abducted?

Related Problem: http://pratikpoddarcse.blogspot.com/2009/10/semi-circle-covering-n-points-puzzle.html

Solution: Posted on CMU Puzzle Toad (http://www.cs.cmu.edu/puzzle/solution33.pdf). Check my name in the acknowledgments \m/ \m/

Car Problem

Source: www.quantstudy.com

Problem: Let A and B be two cities, with two different roads connecting them. Suppose that two cars can travel from A to B on different roads, keeping a distance that does not exceed 1 mile between them.  Is it possible for two cars to travel one from A to B, the other from B to A such that the distance between them is always greater than one mile?

Update: (23 January 2011)
Solution: Posted by Gaurav Sinha (chera) (CSE IITK 1996 Graduate, Now working at Indian Revenue Service) in comments! A more general solution with clear explanation posted by Ameya Ranade (Microsoft Software Engineer, CSE IITB 2009 Graduate)

Jan 7, 2011

Birthday Game

Source: Asked to me by Piyush (Third year Undergraduate Student, CSE, IITD)

Problem: There is a big line of people waiting outside a theater for buying tickets. The theater owner comes out and announces that the first person to have a birthday same as someone standing before him in the line gets a free ticket. Where will you stand to maximize your chance.

Solution: Solution posted by me in comments!

Jan 4, 2011

Expected number of draws

Source: http://deltaepsilons.wordpress.com/

Problem: Consider a set of n objects from which m are drawn randomly at a time, with replacement.  What is E(n,m), the expected number of draws I have to make to have drawn all of the objects?

Note that we solved a similar problem and got the value of E(n,1) some time back in this problem.