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

Nov 26, 2012

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: http://pratikpoddarcse.blogspot.in/2009/12/number-of-locks-and-keys.html

Nov 15, 2012

European Peg Solitaire Solvability

Source: Wikipedia article on Peg Solitaire

Problem:


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

Y Y O O O Y Y
Y O O O O O Y
O O O O O O O
O O O T O O O
O O O O O O O
Y O O O O O Y
Y Y O O O Y Y

Prove that the initial configuration as shown in the representation is not solvable.

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

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

Nov 12, 2012

Geometry Puzzle: Crush the Rebellion

Source: CMU Puzzle Toad

Problem:

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:

Nov 11, 2012

Geometry Problem : Line of Sight

Source: IBM Ponder This November 2012

Problem:

challenge sketch
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).


Nov 10, 2012

Sam Loyd Puzzle Solvability

Source: 15 Puzzle

Problem: The 15-puzzle (also called Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square and many others) is a sliding puzzle that 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.


File:15-puzzle-loyd.svgFile:15-puzzle.svg



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 have taken the facebook game down.

Nov 8, 2012

Math Olympiad Problem - Milk Distribution

Source: 1977 All Soviet Union Math Olympiad Problem

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

Enjoy!

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

Nov 7, 2012

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.

Problem:
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.

Nov 5, 2012

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):
Assumptions: 
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!