The theme of this puzzle is "FROGGER", as we're told by the entry in the center; the crossword was constructed so that you can get from a square at the bottom to a square at the top going via only squares that contain letters in the word FROGGER. A picture of the solved crossword with just the FROGGER letters is at the left.As it turned out, I'd been absent-mindedly flipping through Percolation
by Geoffrey Grimmett right before taking a break to do this crossword. One of the standard results in the theory of percolationis that if we start with an infinite grid and fill in some proportion p of the squares at random, then with probability 1 there will be an infinitely large filled cluster containing the origin when p > 1/2, and if p < 1/2 there's an infinite filled cluster containing the origin with probability 0. (Usually one talks about open and closed bonds -- the lines connecting the sites -- instead of open and closed sites, but since the square lattice is self-dual that doesn't matter.) So it's noteworthy that this is possible here; it wouldn't be possible in a random crossword. We wouldn't be able to get "far away" from a given site using only letters that are taken from some small set. The transition isn't going to be quite so sharp in the non-infinite cases, and the standard 15-by-15 crossword isn't all that close to infinity. Furthermore, finding a long path is even less likely in a crossword than in an ordinary square lattice, because in a crossword there are some black squares.
Furthermore, percolation theory usually assumes that sites are independent; this isn't true in a crossword, because the letters in sites adjacent to each other are correlated. For example, if a given square contains a T, the letter to the right of it or below it is probably more likely to be an H than otherwise, because the pair of letters "TH" is quite common. Any serious attempt to think about percolation in crosswords -- although I can't imagine anyone would study that seriously -- would have to take this into account.
A brief explanation, What is... Percolation by Harry Kesten, was published in May 2006 in the notices of the AMS.
4 comments:
I think that this crossword is a pretty good confirmation of percolation theory. There are 169 cells, of which 75 contain EFGOR. 75/169 is pretty close to 50%, so this suggests to me that the author simply kept increasing the number of EFGOR letters until a connecting path appeared. (Rather than carefully laying them down to form a path, in which case many fewer would have been required.
Of course, random text doesn't have nearly this many ERGOR's. According to Wikipedia, only about 30% of the letters in a random sample of english text wil be in the set EFGOR
David,
I suspect that the distribution of letters in crosswords might be different from the distribution of letters in ordinary English text. For example, the letters T, H, and E are helped in ordinary English text by the word "the", which makes up a substantial fraction of ordinary text but essentially never appears in crosswords.
This doesn't make anything you said invalid, though.
What would be more impressive, of course, would be if the letters of FROGGER formed a path from one end of the grid to the other and did not appear anywhere else; this would be very rare if one was just placing letters down at random. I've seen puzzles like this -- for example, there's been at least one where all the occurrences of the letter A in the puzzle could be connected to form a much larger A.
This reminds me of a NY Times puzzle (maybe 7 or 8 years ago) that did not use the letter e. I was always amazed at that one.
frank, have you read La Disparition, or its English translation A Void?
Post a Comment