Showing posts from 2012

Romanian Informatics Olympiad - Modified Huffman Encoding

Source: (Romanian Informatics Olympiad ONI'03, extended team selection)

( ^ Representative diagram of Huffman Encoding. No relevance in the problem)

A telegraph machine can transmit only lines and dots; it takes 2 seconds to transmit a line, but only 1 second to transmit a dot. We generally want to transmit texts containing letters of the English alphabet, and digits (so we have N<=36 symbols in total). Therefore, a prefix-free encoding using lines and dots is needed. Given the frequencies of the N symbols in a large text, find the minimum time it takes to transmit the text using a suitable encoding. The solution should run in O(N^4) time, and use O(N^3) space.

Coin Puzzle: Predict the Other's Coin

Source:Puzzle collection by Raphael Reischuk

Assume the following 3-player game consisting of several rounds. Players A and B build a team, they have one fair coin each, and may initially talk to each other. Before starting the first round, however, no more communication between them is allowed until the end of the game. (Imagine they are separated in different places without any communication infrastructure.)

A round of the game consists of the following steps:  (1) the team gives one dollar to player C.  (2) Both A and B toss their coins independently.  (3) Both A and B try to predict the other's coin by telling the guess to C. (No communication: A does not know the outcome of B's coin toss, and vice versa, nor the guess).  (4) If C verifies that both A and B guess the other's coin correctly, then C has to give 3 dollars back to the team. 
Should C play this game?

Previously Asked Coin Puzzles:
Coin Balancing
Coins Puzzle
Consecutive Heads
Five Thieves and Bounty

Pizza Distribution Puzzle

Source: xkcd wiki
The king of the universe has decided to play a game. To start, he selects 1 person. He then flips two fair coins - if they both come up heads, the person gets a free pizza and the game is over. For any other result, he sends the person home and selects 2 new people, where he does the same 2-coin flip to decide if they each get a pizza. If they don’t, he picks 4 people at random, then 8, and so on, doubling each round. If you are selected but don’t win, you can’t be selected again – and you can assume the population is extremely large so there’s no chance of running out of contestants.

You are sitting at home when you get a call – you have been selected to play the game. What is the chance that you will get a free pizza?

You don't know which round number it is, but if you ask, the king will tell you. Does it matter?

Disclaimer: Very easy problem!

Update (31 January 2013):
Title changed to "Pizza Distribution Puzzle" from "Pizza Paradox Puzzle&…

Most Popular Math Puzzles in 2012

Problem 1: Lion in a Circular Cage PuzzleOriginal Link:

Source: Asked to me by Pramod Ganapathi (PhD Student at Stony Brook University)

A lion and a lion tamer are enclosed within a circular cage. If they move at the same speed but are both restricted by the cage, can the lion catch the lion tamer? (Represent the cage by a circle, and the lion and lion tamer as two point masses within it.)

Problem 2: Geometry Puzzle: Center of Square in CircleOriginal Link:

Source: Asked to me by a lot of people from IIT Bombay on email and posted by a few on "Post a Question" page.

What is the probability that two uniform random points (to be precise: i.i.d. with respect to Lebesgue measure) in the square are such that center of the square lies in the circle formed by taking the points as diameter.

Problem 3: Consecut…

Snakes and Ladders Optimization

Source: Flipkart Interview Question from Interview Street (taken from Chinmay - CSE IITB Blog)

Find the smallest number of jumps (i.e. optimal number of dice throws) needed to win a snakes and ladders game. Assume you are given a board with all the necessary inputs like start/end positions of all ladders and snakes.

Geometry Contruction - Bisect Areas of 2 Triangles

Source: Asked to me by Sankeerth Rao (EE IITB 4th year Student)

Given any two triangles in a plane construct a line which bisects both their areas.

In fact the existence of such a line is true in a very general setting - for any two polygons in a plane there exists a line which bisects both their areas. In fact its true for any two Jordan measurable sets in a plane. Further generalized version is called the Ham Sandwich Theorem and is proved using Borsuk Ulam Theorem.

Spy Control Problem - Peter Winkler

Source: Video of a course in Algorithms on Udacity - Asked by Prof. Peter Winkler


A spy in an enemy territory is trying to convey information to her control, but the only means she has for conveying information is that there is a 15-bit radio broadcast every morning, and she has the ability if she wishes to alter 1 bit of that broadcast. But she doesn't know in advance what the broadcast will be. So, this is a case where, potentially, there are 16 different things she can do. There are 15 bits she can alter, or she can choose not to alter any bit, which means that in theory perhaps she could convey as many as 4 bits of information this way.

Well, surprisingly, she can actually do that.

Repeating the problem to make sure that we understand the setup here. So, I'm a spy, and I'm in enemy territory, and I've got a message --0110-- that I need to transmit to my boss. Now, that's going to be tricky to do, because I don't want anybody to know that I'm a…

Hanging Picture Puzzle

Source: Mailed to me by Sudeep Kamath (PhD Candidate UC Berkeley, EE IITB 2008 Alumnus)


Suppose we have a portrait hung on a wall using one nail. Now, suppose we hammer another nail next to the existing one and try to use both nails to hang the portrait. If any nail breaks, the portrait continues to hang safely. Can we hang the portrait in such a way that if any one nail breaks the portrait must fall down?

Generalize to k nails: Hang a portrait on k nails such that if any one nail breaks, the portrait must fall down.

Multilingual Hedge Fund - Combinatorics Puzzle

Source: Quantnet Forums
Problem: A hedge fund has 70 employees. For any two employees X and Y there is a language that X speaks but Y does not, and there is a language that Y speaks but X does not. At least how many different languages are spoken by the employees of this hedge fund?

Update: (Dec 17, 2012)
Correct answer posted by Nikhil Jain (IT BHU Alumnus 2008), Paul Wong and Tuhin (IITB 4th year student) in comments.

Similar Problem:
A very similar but more difficult problem posted a couple of years back:

European Peg Solitaire Solvability

Source: Wikipedia article on Peg Solitaire


The European version of the popular game "Brainvita" (or "Peg Solitaire") looks as follows:

Prove that the initial configuration as shown in the representation is not solvable.
The game fills the entire board with pegs except for the central hole. The objective is, making valid moves, to empty the entire board except for a solitary peg. A valid move is to jump a peg orthogonally over an adjacent peg into a hole two positions away and then to remove the jumped peg.

Similar Problems: Rubik's Cube
Sam Loyd Puzzle Solvability

Solution posted by Pritish Kamath (CSE IITB 2012 Alumnus, Assistant Researcher MSR Bangalore) in comments!

Geometry Puzzle: Crush the Rebellion

Source: CMU Puzzle Toad


Ten rebel encampments have sprung up on the plane of Usyan. The Martian Federation plans to send flying saucers to deal with them. They are pretty ruthless. They will simply land on top of the encampments. The encampments are small and the saucers are huge. It must be done simultaneously, or the rebels will flee. Also, the saucers must not overlap when they land. Can the Martians prevail?

Mathematically, the encampments are points in the plane and the saucers are non-overlapping disks of equal radius.

So, The problem is  Given Radius r > 0 of circle, is it possible to arrange 10 points on the plane such that no number of non-overlapping circles of radius r would be such that all 10 points lie in a circle.

Recent Geometry Puzzles on CSE Blog: Geometry Problem : Line of Sight
Geometry Puzzle: Center of Square in Circle
Shortest Curve dividing Equilateral Triangle

Geometry Problem : Line of Sight

Source: IBM Ponder This November 2012


A gardener plants a tree on every integer lattice point, except the origin, inside a circle with a radius of 9801. The trees are cylindrical in shape and all grow together at the same rate.

As the trees grow, more and more points outside the circle of trees stop having a direct line of sight with the origin. What will be the trees' radius when the origin first loses its line of sight with all the points outside the circle? Please give your answer as a decimal number with an accuracy of 13 digits (13 significant digits).

The image is a sketch of a forest of radius 5 and a light beam entering the origin (center of the forest).

Sam Loyd Puzzle Solvability

Source:15 Puzzle
Problem: The15-puzzle(also calledGem Puzzle,Boss Puzzle,Game of Fifteen,Mystic Squareand many others) is asliding puzzlethat consists of a frame of numbered square tiles in random order with one tile missing. The object of the puzzle is to place the tiles in order (from figure at left to figure at right) by making sliding moves that use the empty space. Prove that the 15 puzzle in the configuration as shown on the left is not solvable.

Related Links:
I made this fb game yesterday night - 9 Puzzle over Movie Posters - Movie Sliding Puzzle
Sam Loyd published some great puzzles in his time. One book that gets recommended a lot is "Sam Loyd's Cyclopedia of 5000 Puzzles tricks and Conundrums" (Amazon , Flipkart)

Update: (24/12/2012)
Solution provided by Raghuram Kowdeed (IIT Kanpur) in comments!

Update: (24/12/2012)
Same solution posted by Sai Teja Pratap (IIT Bombay CSE Final Year Student) and Eeshaan Malhotra (IIT Bombay) on Quora Board.

Update: (20/12/2014)
I …

Math Olympiad Problem - Milk Distribution

Source: 1977 All Soviet Union Math Olympiad Problem

Seven dwarfs are sitting at a round table. Each has a cup, and some cups contain milk. Each dwarf in turn pours all his milk into the other six cups, dividing it equally among them. After the seventh dwarf has done this, they find that each cup again contains its initial quantity of milk. How much milk does each cup contain, if there were 42 ounces of milk altogether?

A few other Math Olympiad Problems on the blog:

Math Olympiad Problems
Russian Coins
Moscow Math Olympiad Problems
Math Olympiad Problem : Overlapping Coins
USA Maths Olympiad Problem - 200th Puzzle


Update (24/12/2012):
Correct answer posted by Akshay Kumar in comments! Detailed solution posted by me.

Quick Probability Questions for Interviews

1) If cor(a,b)=0.5 and cor(a,c)=0.0, what is the range for cor(b,c)

2) A deck of pokers. Three choices: A: 26 black, 26 Red; B: 13 black, 13 Red; C: random 26 card from the deck. Take the first two cards, if same color, the win $1, otherwise lose $1. Which deck is best for you if you are playing? Why?

3) What is the probability of a random generator generating 10 consecutive numbers in ascending order (assume it is a perfect random generator)

Update (24/12/2012):
Solution posted by AH in comments! Solution explained in detail by me. Thanks

Geometry Puzzle: Center of Square in Circle

Source: Asked to me by a lot of people from IIT Bombay on email and posted by a few on "Post a Question" page.

What is the probability that two uniform random points (to be precise: i.i.d. with respect to Lebesgue measure) in the square are such that center of the square lies in the circle formed by taking the points as diameter.

Edit: Problem wording made more mathematical.

Update: (24/12/2012)
Correct solutions by Barun Kumar Kejriwal, Akhil Kumar, Aastha Airan, Arpit Goyal and Yashoteja in comments! Thanks a ton.

Math Olympiad Problem : Overlapping Coins

Source: On Quora

Problem: A rectangular table has 100 coins placed on it (centers must be on the table) such that none of the coins overlap, and it is impossible to place any more coins on the table without causing an overlap.
Prove that using 400 coins and allowing overlaps, we can cover the entire table.

Update (2/2/2013):
1) Coins are identical and round.
2) You are given a configuration of 100 coins satisfying the first condition. You are to prove that there exists a fresh configuration of 400 coins satisfying the second condition.
3) Covering the table means for all points on the table, there is at least one coin above that point
4) Coins placed on the table means that the center of the coin is on the table

Solution posted by Stephen Rong in comments!

Number of 1s in 2's complement representation

Source: Interview Street CodeSprint (slightly modified)

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 ?

Two integers A and B

The number of 1s

-2^31 <= A <= B <= 2^31 - 1

Find the asymptotically optimal algorithm.

Hour Glass - Euclid Algorithm

Source: Quora - Asked in a Google Interview


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!

Strategy Game - Similar to Nim

Source: Posted at "Post a Question"


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?

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!

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

a) What is yo…

Inequality Problem

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.

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!

Arithmetic Puzzle: Broken Calculator

Source: Quantnet Forum

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.

IBM Ponder This July 2012 - Colouring Balls

Source:IBM Ponder This July 2012
Problem very similar toCSE Blog: Painting Coloured Balls ( Link: )
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 expected time for N=81 and greater fo…

Pairwise Product Set Cardinality

Source: Nick's Mathematical Puzzles
Problem:Let n be a positive integer, and let Sn = {n2 + 1, n2 + 2, ... , (n + 1)2}.  Find, in terms of n, the cardinality of the set of pairwise products of distinct elements of Sn.
For example, S2 = {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!

Shortest Distance from NewYork to Mumbai

Source: Discussions with BX Mumbai team on my flight from New York to Mumbai

Problem: The flight from New York (Newark - EWR) to Mumbai (Bombay - BOM) takes the aerial route as shown in the figure. Why do the flights not take straightline distance to minimize cost?

Hint: The answer is mathematical. Do not think of regulatory or political reasons.

Update: (19-07-2012) Assume earth is perfect sphere

Permutations and Combinations Puzzle: Cube with Equal Faces

Source: Asked to me by Sumit Yadav
Problem: Is it possible to label the edges of a cube using the numbers 1 through 12, in such a way that the sums of the numbers on any two faces of the cube are equal?
Update: (19-07-2012)
Solution posted by Rakesh Roy (SAP Labs, Bangalore) and Praveen Reddy Vaka (Mechanical Engg IITM Alumnus 2006, CSE IIT Kanpur Alumnus 2011) in comments!

Scheduling Problem

Source: Asked to me by Piyush Sao (EE IITM 2011 Alumnus, Georgia Tech Grad Student). He got it from IBM Ponder This May 2012 (


There are six sets of jobs. Each set is performed on a different server and each set contains jobs that take 1,2,3,...,10 minutes to run.
Obviously, all six sets would end up in 55 minutes.

Schedule all the sets such that if all six servers start together, on minute 0, a job would end on every minute from 1 to 54, and all six servers would end on minute 55 together.
Please supply the solution as six lines of ten numbers.

A solution for a smaller problem of four sets of six jobs ending every minute from 1 to 20 is: 2 1 5 4 6 3 1 3 6 4 5 2 5 2 4 6 3 1 6 3 4 2 1 5
Update: (19-07-2012) Solution posted by Piyush Sao(EE IITM 2011 Alumnus, Georgia Tech Grad Student) in comments! I could not solve it. 

Original Puzzle: Pattern Lock - Combinatorics Puzzle - Number of Possible Passwords

Source: Discussion with Ankush Jain (CSE IITB 2011 Alumnus, Morgan Stanley Analyst) a few months back. Discussion revived by Sangram Raje (CSE IITB 2008 Alumnus, Tower Research Analyst) today.

Ever seen a pattern lock in Galaxy S2? Password is a series of connected line strokes. How many possible password combinations can you have?

Some description about the problem:
1) Assuming the dots on the screen are like (1, 2, 3 in the first row), (4, 5, 6 in the second row) and (7, 8, 9 in the third row), you cannot go to 8 from 2, without going through 5. So, a password like * * 8 2 * * is not possible.
2) You cannot move over two lines twice You can move to a used point, but you cannot move to another used point from a used point
I do not see a simple way to solve this. But even coding this looks very difficult to me. Any takers?
Update: (19-07-2012) This is essentially an open ended question

Maxima Property Subset

Source: Asked to me by Santosh Ananthakrishnan (EE IITB Fifth year undergraduate, To be Worldquant Analyst)

At most, how many subsets can you find of the set A = {1, 2, ..., n} such that any two intersect in exactly one element?

Lion in a Circular Cage Puzzle

Asked to me by Pramod Ganapathi (PhD Student at Stony Brook University)

A lion and a lion tamer are enclosed within a circular cage. If they move at the same speed but are both restricted by the cage, can the lion catch the lion tamer? (Represent the cage by a circle, and the lion and lion tamer as two point masses within it.)

Algorithm Puzzle: Triplets in Array

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

Given an array of n integers, find an algorithm to find triplets in the array such that sum of the three numbers is zero.

What is the order of your algorithm? Make sure its quadratic in size of array. :-)

Original Problem : ATM Money Withdrawal Puzzle

Source: One of the very few original problems on the blog. Remember 'Mathematics of Housie'? Please share if you like!

a) I have infinite money in my account
b) The daily limit of amount of money that can be withdrawn from an ATM is finite
c) You can login into an ATM Machine only once a day
d) If you login into the machine and enter a large number to withdraw, you will not get anything. And hence, you will not be able to withdraw anything from the ATM for the day.
e) I do not know what the daily limit is.

What strategy should I choose so that I can withdraw N rupees in minimum number of days?

Of course, you can do it in N days (withdrawing only one rupee daily)
you could do it in N-limit + ceiling(N/limit)-1 days (check N, check N-1, .. check limit. Once you know the limit, and you have already withdrawn 'limit' rupees, you will take ceiling ((N-limit)/limit) days more.

Can you do better?

Update: (19-07-2012)
This is essentially an open ended quest…

Lazy Walking Strategy Puzzle

Source: Quantnet Interview Questions

Problem: You are standing on the middle of a East-West street. A row of closed doors in front of you, and you have a key on hand which can only open one specific door. Compose a strategy so that X/N is least under the worst situation. X is the distance you covered when arriving at the correct door. N is the distance between the door and the original point.

Number Board Puzzle: Sum of Colours

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


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

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.


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

Pile Puzzle

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!

Update (15th Feb 2012):
Assume steady state exists and try to solve the problem.
A much difficult version: Prove that steady state always exists.


Solution posted by Avradeep Bhowmik (aletterdoesnotblush), Sumanth Puram (IITM Alumnus, Engineer at Netapp), Mayur Agrawal (Agmay, IIT KGP Alumnus, PhD Student at Purdue University) in comments!

The difficult version posed by Nishant Totla (CSE IITB Senior Undergraduate) and solved by Gaurav Sinha (chera, IITK 1996 Graduate, Indian Revenue Service). Thanks a ton!

Digit Permutation Puzzle

Source: Taken from Thomer's Puzzle Website (

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?