1. ## Applied mathematics question

OK, this is something that's been bugging me now for about four years - as long as I've had my current phone...

It's a no-name Android, and to unlock it you're presented with a 3x3 array of points. You know the deal - you trace a figure over these points with your finger.

Rules: the figure can start anywhere, and you can move in any direction, including diagonally. Only straight lines are allowed between points (so you can't, for instance, start at A1 and curve your figure around A2, directly to A3 - if you try this, it'll draw a straight line and consider A2 a part of the pattern anyway). If you touch a point that's already been touched, the second touch will be ignored, and the line will go directly to the next point. A figure must touch at least four points, and may touch any number more, up to all nine.

How do you work out: how many valid figures are there?

2. ## Re: Applied mathematics question

Getting an exact number will be a bit tedious because of the way intermediate points are treated and I do not see a clean way of solving that. Getting the upper bound is pretty easy when you lift the restriction and allow the user to pick any point as the next. In that case you just have:
9*8*7*6 = 9!/5! 4-point patterns
9!/4! 5-point patterns
...
9! 8-point patterns
9! 9-point patterns

This gives an upper bound of 985824. The actual number can be significantly lower than that though, since the restriction on intermediate points can be applied to a given path many times and cuts up to 3 choices.

3. ## Re: Applied mathematics question

From a short google search everyone seems to be doing the same what I would do, writing code to bruteforce it. (Which apparently gives 389112 for those rules.) If there is a neat math way to figure it out I am curious too. I guess you could calculate how often many invalid combinations there are and substract them from 985824, but there the trouble is that all combinations "containing 1 9 but not after a 5" will overlap with some of the other invalid combinations so you shouldn't triple count "1 9 3 7".

4. ## Re: Applied mathematics question

I would say using graph theory, there should be a way to calculate this, but I don't now much about graph theory to help unfortunately

5. ## Re: Applied mathematics question

Originally Posted by asda fasda
I would say using graph theory, there should be a way to calculate this, but I don't now much about graph theory to help unfortunately
That certain points become invalid, based on position really messes with the calculation. You can exploit symmetries and use probability trees. But they blow up real fast too.

Even graph theory uses combinatorial methods to solve those questions.

Invalid paths can even become valid later when the mid point is already taken. So the graph is time/path dependant. Its really messy.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•