Support the GITP forums on Patreon
Help support GITP's forums (and ongoing server maintenance) via Patreon
Results 1 to 5 of 5
  1. - Top - End - #1
    Troll in the Playground
     
    Kobold

    Join Date
    May 2009

    Default 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?
    "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

  2. - Top - End - #2
    Troll in the Playground
    Join Date
    Jan 2007

    Default 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.
    In a war it doesn't matter who's right, only who's left.

  3. - Top - End - #3
    Bugbear in the Playground
    Join Date
    Nov 2013

    Default 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. - Top - End - #4
    Pixie in the Playground
     
    Kobold

    Join Date
    Aug 2020

    Default 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. - Top - End - #5
    Dwarf in the Playground
     
    Kobold

    Join Date
    Aug 2019

    Default Re: Applied mathematics question

    Quote Originally Posted by asda fasda View Post
    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.
    Last edited by Rydiro; 2020-09-30 at 04:37 AM.

Posting Permissions

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