Apr 8, 2012

Original Puzzle: Pattern Lock - Combinatorics Puzzle - Number of Possible Passwords


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

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...