How many possible games of minesweeper are there? There are 480 squares, and 99 of them are mines. Explain your answer. Thanks PS my best time is 128 sec
I won't give you an answer since I don't know if that is your homework or just you asking a question in general, what I will do though is suggest you consider how you would work out how many potential combinations there are in total for a lottery ticket, since the mathematics has some similarities.
Think about it. For the first mine, you have 480 choices of where to put it. For the second one, how many choices? And the third? And the ninety-ninth? So, what's the answer?
(James, I think your guidance advocates the wrong mental picture since mines are indistinguishable from each other, and your mental model has them numbered.) We need a function that tells us how many possibilities there are if were have n squares without mines and m squares with mines, f(n,m). We can probably find that function if we think about the problem, not in terms of total squares and placing mines, but in terms of empty squares and squares with a mine. If you had 0 squares with mines, and 0 squares with a mine, how many possibilities would there be? (1) So f(0, 0) = 1 ... If you had 3 squares without mines and 0 squares with a mine, how many possibilities would there be? (1) So f(3, 0) = 1If you had 2 squares without mines and 1 square with a mine, how many possibilities would there be? Let's work this case out for f(2, 1). The first square is either a mine or not a mine. If it is a mine, then the possibilities for the remaining two squares are: f(2,0) and if it is not a mine, then the possibilities for the remaining two squares are: f(1,1) So f(n,m) = f(n-1,m) + f(n, m-1) when m and n are both more than 0. As f(2,0) = 1 and f(1,1) = f(0,1) + f(1,0) we get f(2,1) = f(2,0) + f(1,0) + f(0,1) = 3 So we have every reason to believe f(n,1) = 1 + nIf you had 1 square without mines and 2 squares with a mine, how many possibilities would there be? (See the symmetry?) So we have every reason to believe f(n, m) = f(m, n)If you had 0 squares without mines and 3 squares with a mine, how many possibilities would there be? (1) ... If you had 4 squares without mines and 2 squares with a mine, how many possibilities would there be? f(4,2) = f(4,1) + f(3,2) = 5 + f(3,1) + f(2,2) = 5 + 4 + f(2,1) + f(1,2) = 5 + 4 + 3 + 3 = 15 5 is larger than 2 or 4, but not larger than 2+4. How does 15 relate to 2, 4 and 6?Does this allow us to compute f(n,m) as a single term instead of a long sum?... If you had 480 squares without mines and 0 squares with a mine, how many possibilities would there be? (1) If you had 479 square without mines and 1 square with a mine, how many possibilities would there be? If you had 478 squares without mines and 2 squares with a mine, how many possibilities would there be? ... Spoiler \(\begin{array}{l|ccccc} {\small n}^{\small m} & 0 & 1 & 2 & 3 & \dots \\ \hline \\ 0 & 1 & 1 & 1 & 1 & \dots \\ 1 & 1 & 2 & 3 & \ddots \\ 2 & 1 & 3 & 6 & \ddots \\ 3 & 1 & 4 & 10 & \ddots \\ 4 & 1 & 5 & 15 & \dots \\ \vdots & \vdots& \vdots& \vdots& \ddots \end{array} \)
Yes. You're right, of course. I was thinking permutations when I should have been thinking combinations. Please Register or Log in to view the hidden image! Also, I was thinking: this doesn't answer the question of how many games there are - unless we assume that "how many games" means "how many different initial positions", which is probably what was meant. Once we start playing the game, we have a different - though similar - problem.
Mine had been 89, but then I got a much faster computer with a much later OS and a neato laser mouse... and I could't break 98. Hmmm.
Short answer: You have 480 squares and you want to know how many ways you can choose 99 of them to be bombs. CHOOSE is the keyword here; it's a combination problem. Do you know what a factorial is? If so, this is easy. n "choose" k = \( \binom nk = \frac{n!}{k!(n-k)!} \) so 480 "choose" 99 = \( \binom {480}{99} = \frac{480!}{99! 381!} \) The actual answer is an enormous number but you can ask Google to do it if you're lazy.
\(\begin{array}{l|ccccc} {\small n}^{\small m} & 0 & 1 & 2 & 3 & 4 & \dots \\ \hline \\ 0 & \frac{(0+0)!}{0! \, \times \, 0!} & \frac{(0+1)!}{0! \, \times \, 1!} & \frac{(0+2)!}{0! \, \times \, 2!} & \frac{(0+3)!}{0! \, \times \, 3!} & \frac{(0+4)!}{0! \, \times \, 4!} & \dots \\ 1 & \frac{(1+0)!}{1! \, \times \, 0!} & \frac{(1+1)!}{1! \, \times \, 1!} & \frac{(1+2)!}{1! \, \times \, 2!} & \frac{(1+3)!}{1! \, \times \, 3!} & \frac{(1+4)!}{1! \, \times \, 4!} & \ddots \\ 2 & \frac{(2+0)!}{2! \, \times \, 0!} & \frac{(2+1)!}{2! \, \times \, 1!} & \frac{(2+2)!}{2! \, \times \, 2!} & \frac{(2+3)!}{2! \, \times \, 3!} & \frac{(2+4)!}{2! \, \times \, 4!} & \ddots \\ 3 & \frac{(3+0)!}{3! \, \times \, 0!} & \frac{(3+1)!}{3! \, \times \, 1!} & \frac{(3+2)!}{3! \, \times \, 2!} & \frac{(3+3)!}{3! \, \times \, 3!} & \frac{(3+4)!}{3! \, \times \, 4!} & \ddots \\ 4 & \frac{(4+0)!}{4! \, \times \, 0!} & \frac{(4+1)!}{4! \, \times \, 1!} & \frac{(4+2)!}{4! \, \times \, 2!} & \frac{(4+3)!}{4! \, \times \, 3!} & \frac{(4+4)!}{4! \, \times \, 4!} & \ddots \\ \vdots & \vdots & \ddots & \ddots & \ddots & \ddots & \ddots \end{array} \) \(f(n,m) = \frac{( n + m )! }{n! \, \times \, m!} = \frac{( m + n )! }{m! \, \times \, n!} = f(m,n) \\ f(1+n,m) + f(n, 1+m) = \frac{( n + m + 1 )! }{(1 + n)! \, \times \, m!} + \frac{( n + m + 1 )! }{n! \, \times \, (m + 1)!} = \frac{( n + m + 1 )! }{n! \, \times \, m!} \left[ \frac{1}{1+n} + \frac{1}{1+m} \right] = \frac{( n + m + 1 )! }{n! \, \times \, m!} \, \times \frac{m + n + 2}{(1+n)(1+m)} = \frac{( n + m + 2 )! }{(1 + n)! \, \times \, (1 + m)!} = f(1+n, 1+m) \\ f(n,0) = \frac{( n + 0 )! }{( n + 0 )! \, \times \, 0!} = 1 \\ f(n,1) = \frac{( n + 1 )! }{n! \, \times \, 1!} = \frac{(n+1) \, \times \, n!}{n! \, \times \, 1!} = n+1 \\ f(n,2) = \frac{( n + 2 )! }{n! \, \times \, 2!} = \frac{(n+2) \, \times \, (n+1) \, \times \, n!}{n! \, \times \, 2!} = \frac{(n+2) \, \times \, (n+1)}{2!} = \frac{(n+2) \, \times \, (n+1)}{2} \\ f(99, 381) = \frac{480!}{99! \, \times \, 381!} = \frac{\prod_{k=1}^{99} (381 + k)}{\prod_{k=1}^{99} k} = 560\underbrace{\dots\dots\dots}_{99 \; \textrm{digits omitted}}600\)
It is easy Compination proble. A single mine can be placed in 480 ways, second in 479 ways and so on till 99th mine has 360 ways. Total no of games = 480!/[100! x 381!}
