CSE Blog - quant, math, computer science puzzles

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

Source: Asked to me by Piyush Sao (EE IITM 2011 Alumnus, Georgia Tech Grad Student). He got it from IBM Ponder This May 2012 ( http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/Challenges/May2012.html ) Problem: 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. 

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

Source: Asked to me by  Santosh Ananthakrishnan (EE IITB Fifth year undergraduate, To be Worldquant Analyst) Problem: At most, how many subsets can you find of the set A = {1, 2, ..., n} such that any two intersect in exactly one element? Solution: Highlight the part between the * symbols for the answer. * Answer: n. Construction (n subsets): {1}, {1,2}, {1,3}, ..., {1,n} - every pair intersects in exactly {1}. Upper bound: let A_1, ..., A_K be such a family and v_1, ..., v_K their 0-1 incidence vectors in R^n; the condition says v_i . v_j = 1 for i != j. The Gram matrix G (entries v_i . v_j) has |A_i| on the diagonal and 1 everywhere off it. If every |A_i| >= 2 then G = diag(|A_i| - 1) + J, a positive diagonal matrix plus a positive semidefinite one, hence invertible - so the v_i are linearly independent in an n-dimensional space and K <= n. If instead some set is a singleton, say A_1 = {x}: every other set must contain x (to meet A_1 in one element), and no two other...

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 Anuj Jain (EE IITB 2010 Graduate, MFE Student at Baruch College NY) Problem: 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. :-) Solution: Highlight the part between the * symbols for the answer. * O(n^2) algorithm: sort the array (O(n log n)). For each i from 1 to n, look for a pair (j, k) with i < j < k and a[j] + a[k] = -a[i] using two pointers: set j = i+1, k = n; if a[j] + a[k] equals the target, record the triplet and move both; if the sum is too small, j++; if too big, k--. Each pair-search is O(n) because the pointers only move toward each other, so the total is O(n^2) plus the one-time sort. Correctness: when a[j] + a[k] < target, no k' < k can work with this j (the array is sorted, sums only get smaller), so k is never needed again - and symmetrically for j - so no...