Results 1 to 5 of 5
Thread: Applied mathematics question

20200915, 04:26 AM (ISO 8601)
 Join Date
 May 2009
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 noname 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?"None of us likes to be hated, none of us likes to be shunned. A natural result of these conditions is, that we consciously or unconsciously pay more attention to tuning our opinions to our neighbor’s pitch and preserving his approval than we do to examining the opinions searchingly and seeing to it that they are right and sound."  Mark Twain

20200915, 05:24 AM (ISO 8601)
 Join Date
 Jan 2007
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! 4point patterns
9!/4! 5point patterns
...
9! 8point patterns
9! 9point 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.In a war it doesn't matter who's right, only who's left.

20200915, 05:53 AM (ISO 8601)
 Join Date
 Nov 2013
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".

20200929, 05:46 AM (ISO 8601)
 Join Date
 Aug 2020
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

20200930, 03:19 AM (ISO 8601)
 Join Date
 Aug 2019
Re: Applied mathematics question
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.Last edited by Rydiro; 20200930 at 04:37 AM.