1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Help with an Abstract Binary Math Problem

  1. Jun 10, 2013 #1
    So I was trying to figure out a straightforward method to calculating the possible number of combinations on a beginner minesweeper game (81 squares, 9x9, 10 mines)

    I figure that i can attribute this to binary. Because the 9x9 part shouldnt really matter.


    It is essentially a 81 bit binary number, where you know that only 10 of the bits are 1.

    How would I go about calculating this?
     
  2. jcsd
  3. Jun 10, 2013 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You have 81 squares, and you have to choose 10 of them to have 1s.

    Do you know a mathematical function which tells you how many ways to choose a certain number of elements from a set?
     
  4. Jun 10, 2013 #3
    Not off the top of my head, I do not. Which may or may not be kind of embarassing, considering I am on my way to Calculus next school year.
     
  5. Jun 10, 2013 #4

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    OK well this is a fun combinatorial exercise. If I have 81 objects and I want to pick 1 of them, how many ways can I make that decision?

    Now suppose I want to pick 2 of them. First I have to pick one of my 81 objects, then I have 80 objects left which I have to pick one of. So how many total ways were there to pick 2 objects? Watch out! Picking object A then object B, or picking object B then object A is irrelevant if all I care about is that A and B are my two picked objects.
     
  6. Jun 10, 2013 #5
    81 ways.

    So, that would be 1/81.

    Now that 1 of the squares is absolutely, unvariably determined. We essentially have a problem with 80 objects and 1 mine.

    So would it be....

    1/81 * 1/80 * 1/79 ... * 1/71?
     
  7. Jun 10, 2013 #6

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I don't understand why you are taking 1/81 or 1/80 instead of just 81 and 80

    Also you have to worry about double counting. If I pick the first mine to go in the top left corner, then the second mine to go directly beneath it, you counted that as being different from the first mine going one below the top left corner, and the second mine in the top left corner
     
  8. Jun 11, 2013 #7
    Sorry, I think my mind skipped back to when I found out how many combinations there are of lottery tickets.

    Ehm, from here I believe I may have to abdicate from the position of "someone smart" as so callously put in your signature. Care to pick up my slack?
     
  9. Jun 11, 2013 #8

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Let's do a simpler example: If I have 6 objects and want to pick 2 of them how many ways are there to do it?

    Let's suppose the objects are a,b,c,d,e,f. There are 6 ways to pick the first object, then 5 ways to pick the second object. That gives 30 ways to pick the object. But we have counted some of these too many times. For example:
    first object: a. second object: b
    and
    first object: b. second object: a

    were both counted as two different ways of picking two objects. So what do I need to divide 30 by in order to get the correct answer?

    (Notice the key difference between this problem and most lottery ticket problems is that for lottery tickets the order in which you pick your numbers matters, but for this problem it does not)
     
  10. Jun 11, 2013 #9
    The answer is two. Does that mean I need to divide the answer by 10?

    If that is the case, you will get 48,395,803,610,547,993,600. Also known as 48 quintillion. Also Also known as 48 billion billion

    However, 9x9 leaves you with a perfect square. Which means that any one of those arrangements is repeated 4 different times in the manner of rotation. So we should divide it by 4.

    12,098,950,902,636,998,400.

    However, I am not sure that this is the exact number. Because I'm sure there are multiple arrangements in which rotating it would keep it the same. So overall, we have 3 arrangements we need to top off for every example like that.

    However, I am not willing to dig that deep and I doubt the number as a whole would be seriously affected.


    I was so very interested in solving this problem for two reasons. The first being that I could not find an answer online.


    The second being, that of the 12 quintillion possible arrangements of beginner minesweeper. I have finished 10,000 of them. I imagine that the chance of me repeating one with such a fantastic total is very low.
     
  11. Jun 11, 2013 #10

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Not quite, but we're almost there! Let's consider the same situation where I pick three objects out of a,b,c,d,e,f. That would be 6*5*4 = 120 ways to pick to start How many ways did I overcount by? Well, it's the same as the number of ways I can arrange three objects. For example:

    a,b,c
    a,c,b
    b,a,c
    b,c,a
    c,a,b
    c,b,a

    are all different ways to pick the set {a,b,c}. So we would need to divide 120 by six in order to get the correct answer of 30.

    Now we're ready to answer the big question. If I pick 10 objects, there are 81*80*79*78*77*76*75*74*73*72 ways of doing it with overcounting. To get rid of the overcounting I need to divide by the number of ways I could have picked those ten objects. We've seen the number of ways to arrange two objects is 2, the number of ways to arrange three objects is 6, and I'll tell you (you should check for yourself if you don't see why this is true) the number of ways to arrange four objects is 24.

    I'm a bit confused by your rotation part. Do you mean that you want to consider a game which has just one mine in the top left corner to be the same as a game which has just one mine in the top right corner? That should be solvable but is a bit tricky, I'll think about how to attack it
     
  12. Jun 12, 2013 #11
    I think I'm getting it. So instead of dividing by 10 I need to divide by the factorial of 10?

    That leaves us with 133 trillion.

    And yes, you're right, with a square board the puzzles would be the same essentially, so I would consider it over counting because we count each puzzle 4 times as a result of each rotation.
     
  13. Jun 12, 2013 #12

    jbriggs444

    User Avatar
    Science Advisor

    There is another tricky bit that I imagine Office_Shredder was considering. What if a possible arrangement of mines was already symmetric so that a 90 degree rotation does not change it? Then you would be counting that arrangement 1/4 times instead of one time.

    To illustrate that problem, consider a simpler case -- one mine on a 3x3 grid.

    There are nine possible layouts. If you divide by four for rotation, that gives 2.25 possibilities. But that's clearly ridiculous. That is because one of the possibilities was with one mine exactly in the center. You should not have divided that possibility by four.

    As Office_Shredder indicated, it gets tricky. I would be thinking about an attack that tries to count the ways of allocating mines with complete rotational symmetry and with only 180 degree rotational symmetry. Then do an inclusion/exclusion counting scheme to find the number of asymmetric arrangements.

    Total equivalent positions =
    asymmetric arrangements / 4 +
    180 degree (but not complete) symmetric arrangements / 2 +
    completely symmetric arrangements

    Then you could try to factor in reflections.
     
  14. Jun 12, 2013 #13
    Everyone on this website is absolutely brilliant. Thanks, but I can settle for 133 trillion.
     
  15. Jun 12, 2013 #14

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You know that that answer is correct to within a factor of 4 if you include rotations, so if you're just trying to get an order of magnitude for probability you repeat a game this should be good enough.

    To wrap up what my original post said, the function I was describing is appropriately enough named n choose k: with two inputs of n and k, it is defined as
    [tex] \binom{n}{k} = \frac{n!}{k! (n-k)!} [/tex]
    For example, 81 choose 10 would be defined as
    [tex] \binom{81}{10} = \frac{81!}{10! 71!} = \frac{81\cdot 80 \cdot.... \cdot 73 \cdot 72}{10!} [/tex]
    which of course is the answer we already calculated
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Help with an Abstract Binary Math Problem
  1. Math problem help (Replies: 4)

  2. Abstract maths (Replies: 4)

Loading...