Help with an Abstract Binary Math Problem

[Deagonx]

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 shouldn't 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?

 

[Office_Shredder]

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?

 

[Deagonx]

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.

 

[Office_Shredder]

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.

 

[Deagonx]

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?

 

[Office_Shredder]

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

 

[Deagonx]

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?

 

[Office_Shredder]

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)

 

[Deagonx]

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 anyone 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.

 

[Office_Shredder]

The answer is two. Does that mean I need to divide the answer by 10?

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

 

[Deagonx]

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.

 

[jbriggs444]

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.

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.

 

[Deagonx]

Everyone on this website is absolutely brilliant. Thanks, but I can settle for 133 trillion.

 

[Office_Shredder]

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
$$\binom{n}{k} = \frac{n!}{k! (n-k)!}$$
For example, 81 choose 10 would be defined as
$$\binom{81}{10} = \frac{81!}{10! 71!} = \frac{81\cdot 80 \cdot... \cdot 73 \cdot 72}{10!}$$
which of course is the answer we already calculated