CSE Blog - quant, math, computer science puzzles

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

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!

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: Geo metry Problem : Line of Sight Geometry Puzzle: Center of Square in Circle Shortest Curve dividing Equilateral Triangle

Source:  IBM Ponder This November 2012 Problem: 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).

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. 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 E

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.

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

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.

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!