9
$\begingroup$

Suppose I make a 20x10 grid out of match sticks, using 21 columns of 10 match sticks and 11 rows of 20 match sticks:

 ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
 ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
 ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
 ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
 ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
 ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
 ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
 ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
 ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
 ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
 ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─

I am going to independently remove each match stick with 1% probability, leaving behind an average of 99% of the match sticks.

After I do that, you will count up how many squares are formed by the match sticks. Squares can be 1x1, 2x2, 3x3s, and etc up to 10x10 (or technically larger, but those wouldn't fit). A square must have all of the match sticks along its border present, but its insides don't matter.

Here's some examples of valid 2x2 squares:

 ─ ─      ─ ─      ─ ─      ─ ─ 
│ │ │    │   │    │ │ │    │   │
 ─ ─                 ─      ─ ─ 
│ │ │    │   │    │   │    │   │
 ─ ─      ─ ─      ─ ─      ─ ─ 

And some broken 2x2 non-squares that don't count (though there are still 1x1 squares in the examples):

 ─ ─      ─ ─        ─          
│ │      │   │      │ │    │   │
 ─ ─                 ─      ─ ─ 
│ │ │    │                 │   │
 ─ ─      ─ ─                   

Call the count N. What is the expected value of N?

For example, if we were working with a 1x1 grid instead of a 20x10 grid then the expected value of N would be ~0.9606 because there's only one possible square and it's present if and only if all four match sticks stay and that happens in (1 - 0.01)^4 ~= 96.06% of cases.

$\endgroup$
  • $\begingroup$ Seems a really hard combinatorics problem. I doubt you'll understand the solution even if it exists. Flagged as math problem. $\endgroup$ – ghosts_in_the_code Mar 24 '15 at 15:28
  • 3
    $\begingroup$ @ghosts_in_the_code Is there an FAQ delineating what's considered a not-puzzle? The solution to this problem is simple enough to do by hand, or in a single line of python. The puzzle is figuring out the trick to make it simple. $\endgroup$ – Craig Gidney Mar 24 '15 at 15:43
  • $\begingroup$ It isnt harder than island of stability, it looks a ok problem to me. $\endgroup$ – leoll2 Mar 24 '15 at 17:05
  • 1
    $\begingroup$ See this discussion for math puzzle vs math problem. It's a subjective distinction, but I'll explain why I don't think this math problem makes a good puzzle. It's mostly a straightforward and ugly mathematical calculation. Other than realizing to use linearity of expectation, you don't need much ingenuity, just work. You express the summation and sum it using generating-function methods or using code. If this summation collapsed to something nice or had a pretty combinatorial interpretation, it would be more puzzley. $\endgroup$ – xnor Mar 24 '15 at 22:30
10
$\begingroup$

Isn't that just linearity of expectation? The answer is approximately 810.927.

(1) For $k=1,\ldots,10$ the picture contains exactly $(21-k)(11-k)$ squares of sidelength $k$.

Proof: every $k\times k$ square has a unique upper left corner. The last $k-1$ points in every row are not possible, since then the square would overhang; hence there remain $20-(k-1)=21-k$ corner candidates in the row. Similarly, the last $k-1$ points in any column are not possible.

(2) For any fixed $k\times k$ square, the probability of surviving the removal process is $(1-p)^{4k}$ where $p=1/100$.

Proof: The square has $4k$ match sticks on its perimeter. It survives, if and only if each of these match sticks survives.

(3) The expected number of surviving squares is $N=\sum_{k=1}^{10}(21-k)(11-k)(1-p)^{4k}$ where $p=1/100$.

Proof: This follows by linearity of expectation.

(4) Evaluate the sum.

In python:

>>> sum((21-i)*(11-i)*0.99**(4*i) for i in range(1, 11))
810.9274873676787
$\endgroup$
  • $\begingroup$ Yup, just linearity of expectation. $\endgroup$ – Craig Gidney Mar 24 '15 at 18:28
  • $\begingroup$ Correct me if I'm wrong, but I'm not convinced that you can do this as the probability that a square survives the process is not independent of another square surviving. For example in a 2x2 grid (12 match sticks), given that the top left square does not survive, the probability that the whole 2x2 square survives is less than 1/2. $\endgroup$ – KSab Mar 24 '15 at 22:07
  • $\begingroup$ @KSab Yes, the probabilities are correlated, and one event happening impacts the probability of another even happening. But, the expectation of the sum is still the sum of the expectations, because expectation is linear. $\endgroup$ – xnor Mar 24 '15 at 22:33
  • $\begingroup$ Using Mathematica, the sum is exactly 810.92748736767871972002223942394696154993490886677347506294792434053010902805756011. $\endgroup$ – 2012rcampion Sep 28 '15 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.