CSE Blog - quant, math, computer science puzzles

Source: Sent to me by Pritish Kamath (http://www.mit.edu/~pritish/) Problem: Have you ever played "SET"? You have to play it. http://www.setgame.com/learn_play http://www.setgame.com/sites/default/files/Tutorials/tutorial/SetTutorial.swf Even if you have not played the game, the game can be stated in a more abstract way as follows: There are 12 points presented in  F 3 4  and the first person to observe a "line" amongst the 12 given points gets a score. Then the 3 points forming the line are removed, and 3 random fresh points are added. Problem 1: How many points in  F 3 4  are needed to be sure that there exists a line among them? Problem 2: Given 12 random points in  F 3 4 , what is the probability that there exists a line among them? Disclaimer: We have not solved the problem yet. It can be very difficult or very easy. Update (22/12/14): It turns out to be a very very difficult problem. Paper: http://www.math.rutgers.edu/~maclagan...

Disclaimer: It is a made up problem. Not to be attempted by light hearted. Problem: I have a 300 word text. I have a large list of indexed strings (Length of string ~ 20, Number of strings ~ 1M). I need to figure out phrases in the 300 word text that match exactly to one of the strings in the large list of strings I have. A naive approach: Taking all 45000 (300 C 2) phrases, search in the large list of strings. Can we do better than this? We need to minimize calls to list of indexed strings!

Source: Original problem adapted from the "Ants Problem" (Link removed) at "CMU ACM Programming Contest" . Extension to the 4 year old problem on CSE Blog - Walking Ants Puzzle  . Problem also available at  J. Paulson Programming Blog Problem: You have a bunch of ants on a meter stick, each walking 1cm/s in some direction. If an ant hits the end of the stick, it falls off. If two ants collide, they both reverse direction. Walking Ants Puzzle  earlier essentially asked: Given the starting positions and directions of all the ants, how long until the last ant falls off? The new problem is : Given the starting positions and directions of all the ants, which ant(s) are the last to fall off? Disclaimer: I do not have the solution to the problem. It just looks like an interesting problem to solve. ( Readers Please ignore: Technorati claim:  6QVZ8YSY6XSD ) Update (24 June 2014): Solution:  Posted by Strilanc and me in comments!

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: One of the very few original problems on the blog. Remember ' Mathematics of Housie '? Please share if you like! Problem: Assumptions: 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 e...