CSE Blog - quant, math, computer science puzzles

Source: Asked to me by a friend - who was asked this question in an interview at Facebook Problem: Given n points on a 2D plane, find the equation of the line with maximum number of collinear points. What is the time complexity of your algorithm? Solution: Highlight the part between the * symbols for the answer. * O(n^2) algorithm: the optimal line passes through at least two of the points (otherwise rotate/translate it until it does without losing collinear points). So for each point p, compute the slope from p to every other point and tally frequencies in a hash map (use exact rational slopes dy/dx reduced by gcd, plus a sentinel for vertical lines - avoid floating point). The most frequent slope from p, plus p itself, gives the best line through p. Take the maximum over all p. Complexity: n points x O(n) slope computations and hash updates = O(n^2) expected time, O(n) space per round. (Deterministic O(n^2 log n) via sorting slopes instead of hashing.) This is worst-...

Source: http://nrich.maths.org/ Problem: A mad robot sets off towards the North East on a journey from the point (0,0) in a coordinate system. It travels in stages by moving forward and then rotating on the spot. It follows these pseudo-code instructions: SUB JOURNEY     DISTANCE = 1000     WHILE (DISTANCE > 0.001)         MOVE DISTANCE         STOP         ROTATE(90, DEGREES, CLOCKWISE)         DISTANCE = DISTANCE / 2     END WHILE     EXPLODE END SUB Where does the robot explode? Update (23 Oct 2014): Solution:  Posted by me (Pratik Poddar) in comments!

Source: FunctionSpace.org Problem: Given the polygons P and Q as shown in the grid below, cut P into two polygons P1 and P2 such that, when pasted together differently, they form Q. Update ( 21 June 2014 ) : Solution by Varun and Adwait in comments!

Source: Quantnet Problem: Roll a penny around another fixed penny in the center with edges in close contact. After moving half circle around the center penny, you will find the penny in motion has rotated 360 degrees. Why? Update (29/06/2013): Solution posted by Sanket Patel and Suyash Jain (IITB Mech 2008 Aumnus, Ex-Credit Suisse Analyst, Ex-Deutsche Bank Analyst) in comments!

Source: Asked to me by Sankeerth Rao (EE IITB 4th year Student) Problem: Given any two triangles in a plane construct a line which bisects both their areas. Background: 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. Solution: Highlight the part between the * symbols for the answer. * Key fact: in every direction there is a line that bisects a given triangle's area, and it moves continuously as the direction rotates. (For direction theta, sweep a line of that slope across the triangle; the area on one side goes continuously from 0 to the full area, so some position halves it - and the halving position varies continuously with theta.) Now parameterize by angle theta in [0, pi): let L(theta) be the bise...

Source: Mailed to me by Sudeep Kamath (PhD Candidate UC Berkeley, EE IITB 2008 Alumnus) Problem: 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. Solution: Highlight the part between the * symbols for the answer. * Yes, for every k. Think of the string as a word in the nails: passing clockwise around nail i writes the letter i, counter-clockwise writes i^-1. The picture hangs iff the word is non-trivial (cannot be cancelled away), and it falls when, after deleting every occurrence of the broken nail's letter, the remaining word cancels to nothing. Two nails: loop the string around nail 1 cl...

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 Solution: Highlight the part between the * symbols for the an...

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). Solution: IBM Ponder This official answer, posted in comments!

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

Source: Asked to me by Pramod Ganapathi (PhD Student at Stony Brook University) Problem: 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.) Solution: Highlight the part between the * symbols for the answer. * Answer: surprisingly, no - the tamer can avoid being caught forever. This is the famous Lion and Man problem, posed in the 1930s and settled by Besicovitch; the proof appears in Littlewood's "A Mathematician's Miscellany" (and opens Bollobas's "The Art of Mathematics"). What the lion CAN do (Rado's strategy): move to the center, then always stay on the radius through the tamer, using any spare speed to move outward. Since the lion runs on a smaller circle, it can match the tamer's angular position while steadily increasing its radiu...

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. Solution: Highlight the part between the * symbols for the answer. * Answer: a circular arc of about 0.6734, much shorter than the altitude (0.866) or the bisecting parallel line (1/sqrt(2) = 0.707). Suppose the curve joins sides AB and AC, enclosing area 1/2 * sqrt(3)/4 = sqrt(3)/8 with vertex A. Reflect the triangle five more times around A to tile the full 360 degrees; the curve becomes a closed curve enclosing 6 * sqrt(3)/8 with 6 copies...

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!

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!

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/

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)

Source : Asked to me by Nigel Coldwell (now posted on his blog) Problem : Two creepers, one jasmine and other rose, are both climbing up and round a cylindrical tree trunk. jasmine twists clockwise and rose anticlockwise, both start at the same point on the ground. before they reach the first branch of the tree the jasmine had made 5 complete twists and the rose 3 twists. not counting the bottom and the top, how many times do they cross? Related video : Solution : My solution posted on Nigel's Blog here . Slightly different solution posted by Gaurav Sinha (1996 CSE IITK passout, now at Indian Revenue Service) in comments! A more general argument by Aaditya Ramdas (CMU Grad Student - CSE IITB 2009 Alumnus - Ex Tower Research Analyst) in comments!

Source : William Wu Puzzle Page Problem : Draw an equilateral triangle (all sides same length). Divide it into four identical shapes. remove the bottom left hand shape. now divide the resulting shape into four identical shapes. Update (18 Oct 2010): Solution : Identical solutions posted independently by Siddhant Agarwal (Senior Undergraduate, EE, IITB) and Shaunak Chapparia (Senior Undergraduate, CSE, IITB) in comments.

Source: CMU Spring 2010 Course on Great Theoretical Ideas in Computer Science Problem: 10% of the surface of a sphere is colored green, and the rest is colored blue. Show that no matter how the colors are arranged, it is possible to inscribe a cube in the sphere so that all of its vertices are blue. Hint: Use probabilistic analysis. Consider a random cube and calculate the expected number of vertices that are blue. (Update 23/06/10): Solution: Posted by connect2ppl - Giridhar Addepalli (CSE, IITK alumnus and Yahoo! Sr. Software Engineer) in comments!

Source: http://www.math.utah.edu/~cherk/puzzles.html Problem: Salt Lake City looks like a rectangle crossed with M streets going from North to South and with N streets going from East to West. The city is frequently visited by tourists who suppose to run around in the buses. The Utah governor wants to vigil all moves of the buses. He plans to put policemen at some intersections to watch all the buses moving on the streets visible from that intersections. What is the minimum number of policemen needed for the bus watch? Update (26/03/10) Solution: Posted by Ashu and Aman in comments!!