CSE Blog - quant, math, cse puzzles

Number Board Puzzle: Sum of Colours

2012-01-19T14:23:00.001+05:30

Source: Asked to me by Anuj Jain (EE IITB 2010 Graduate, MFE Student at Baruch College NY)

Problem:

You have a 8x8 square board with numbers in each cell.

1	2	3	4	5	6	7	8
9	10	11	12	13	14	15	16
17	18	19	20	21	22	23	24
25	26	27	28	29	30	31	32
33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48
49	50	51	52	53	54	55	56
57	58	59	60	61	62	63	64

Each number is given a colour (red or white) such that each row and each column has exactly the same number of red number and white numbers (i.e. four). Prove that the sum of 32 red numbers on the board is equal to the sum of the other 32 white numbers on the board.

Cheers!

Update (21 Jan 2012):
Solution: Posted by Piyush Sao (EE IITM Alumnus, Georgia Tech Grad Student) in comments!

Pile Puzzle

2012-01-11T18:58:00.002+05:30

You have 55 matches arranged in some number of piles of different sizes. You now do the following operation: pick one match from each pile, and form a new pile. You repeat this ad infinitum. What is the steady state? Is it unique?

Answer is intuitive :) Cheers!

Digit Permutation Puzzle

2012-01-04T19:40:00.001+05:30

Source: Taken from Thomer's Puzzle Website (http://thomer.com/riddles/)

Problem:
You have a number that consists of 6 different digits. This number multiplied by 2, 3, 4, 5, and 6 yields, in all cases, a new 6-digit number, which, in all cases, is a permutation of the original 6 different digits. What's the number?

Number of digits in 125^100

2011-12-23T16:54:00.002+05:30

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

2011-12-23T16:42:00.000+05:30

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

Crossing the Road

2011-12-19T18:49:00.000+05:30

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!

Shortest Curve dividing Equilateral Triangle

2011-12-16T14:41:00.000+05:30

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.

Matrix Saddle Points

2011-12-12T11:41:00.001+05:30

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 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!

Rubik's Cube

2011-12-04T11:35:00.001+05:30

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

2011-12-04T10:11:00.001+05:30

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!

Numbers on a circle - Minimum sum of consecutive differences

2011-11-21T21:25:00.001+05:30

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!

21 Problems in 21 Days left for Placements

2011-11-09T10:53:00.001+05:30

For 21 days left for IIT placements, Siddhant Agarwal (EE IITB 2011 Alumnus, CMI Grad student) and Vivek Jha (EE IITB 2011 Alumnus, Credit Suisse Analyst) have selected 21 problems out of ~200 problems on the blog, so that people can prepare for the placements in the last minute. Help yourself! Cheers! Best of Luck!

Locks and Switches
The Best Horse
Duplicate Integer
Stick Broken Into Three Pieces
Finding a hermit
Prime Number Strategy Game
Hats and Rooms
Need for Needles
Checkers Problem
King's Poisonous Wine II
Smallest Number in Decreasing Sequence
Increasing Sequence in Dice
Random point in a circle
Another Coin Problem
Painting Colored Balls
Another Hat Problem
Arrange in a Sequence
Russian Coins
Top Card
Ants on a Cube
Coin Balancing

Guess 3 numbers

2011-11-05T20:09:00.000+05:30

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!

Scaling a Square

2011-11-03T14:38:00.002+05:30

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!

Divisibility of 111...1111

2011-11-01T18:18:00.002+05:30

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

Sphagetti Breakfast

2011-10-31T16:51:00.002+05:30

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)

Distinct numbers in a sample draw

2011-10-13T04:24:00.001+05:30

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!

Function Inner Product

2011-10-11T05:47:00.000+05:30

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.

Difference between foo(void) and foo()

2011-09-11T14:59:00.000+05:30

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.

C code 32 bit vs 64 bit

2011-09-10T22:47:00.002+05:30

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

2011-09-10T21:26:00.001+05:30

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)

Arrange in a Sequence

2011-09-04T15:01:00.001+05:30

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.

Football Board

2011-08-27T11:50:00.001+05:30

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)?

	Played	Goals for	Goals against	Points
United	2	1	0	3
City	2	2	1	2
Albion	2	0	2	1

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?

	Played	Won	Lost	Drawn	Goals for	Goals against	Points
Athletic	3	2	*	*	4	4	*
Rovers	*	1	*	0	3	0	*
Town	*	*	*	0	1	1	*
Wanderers	*	*	*	*	*	*	*

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

Sacred Right Pan - IMO 2011 Problem

2011-08-17T23:02:00.005+05:30

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

Increasing Sequence in Dice

2011-08-16T20:44:00.001+05:30

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!

1	2	3	4	5	6	7	8
9	10	11	12	13	14	15	16
17	18	19	20	21	22	23	24
25	26	27	28	29	30	31	32
33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48
49	50	51	52	53	54	55	56
57	58	59	60	61	62	63	64

1	2	3	4	5	6	7	8
9	10	11	12	13	14	15	16
17	18	19	20	21	22	23	24
25	26	27	28	29	30	31	32
33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48
49	50	51	52	53	54	55	56
57	58	59	60	61	62	63	64

1	2	3	4	5	6	7	8
9	10	11	12	13	14	15	16
17	18	19	20	21	22	23	24
25	26	27	28	29	30	31	32
33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48
49	50	51	52	53	54	55	56
57	58	59	60	61	62	63	64