# Unlisted Entries in Your Word Finds

Over dinner tonight, my daughter told us a story about how they were working on a Word Find in school today and she found the word “ELF”.  She was fascinated by the fact that the theme of the Word Find was supposed to be Thanksgiving and that the word was not listed among the words to find.

The story started me thinking.

### What do you suppose is the probability that in an m x m Word Find (meaning m rows and m columns) you would find a given three letter word, like “ELF”?

To answer the question, you must first lay out some ground rules, or assumptions as we call them in mathematical modeling.  First, let’s assume that the letters are distributed randomly and uniformly.  Second, we’ll assume that there are three orientations to finding the word: vertical, horizontal and diagonal.  As with most of these puzzles I’ve every done and especially the ones my daughter is now doing as a 10 year old, we’ll also expect to find the word forward or backward.

For a single 3 letter random string, the probability that it matches our given word would clearly be

[tex]p=frac{2}{26^3}[/tex]

because the likelihood of each letter matching is 1/26 and because we assumed random letters, a forward match has a probability of 1/26 * 1/26 * 1/26, as does a backward match.

The next question to answer would be, how many 3-letter sequences are there for an m x m matrix of letters?

In each row, there would (m-2) 3-letter sequences which means m*(m-2) horizontal sequences.  The same goes for the columns.  Now consider the diagonals.  On the main diagonal there are m letters so there would be (m-2) 3-letter sequences.  On the first super-diagonal there are (m-1) letters so there would be (m-3) 3-letter sequences.  The same is true for the first sub-diagonal.  If you keep marching up the diagonals, you’ll see (m-4), then (m-5), all the way down to 1.

So we’ll have a total of

[tex](m-2) + 2(m-3)+2(m-4)+cdots+2(1)[/tex]

for the number of forward diagonal 3-letter sequences.  Since our word-find is assumed to be square, we’ll have the same number going on the back diagonal.  So here is a total count on 3-letter sequences: horizontal + vertical + diagonal.

[tex]mathrm{Total} = 2m(m-2)+2(m-2)+4(m-3)+cdots + 4(1)[/tex]

To simplify this, recall that if you have the sum of the first k integers,

[tex]1+2+cdots+k=frac{k(k+1)}{2}[/tex]

So we can simplify the Total as first combining the first two terms,

[tex]mathrm{Total}=(2m+2)(m-2)+4(m-3)+cdots+4(1)[/tex]

Then we combine the last terms using the sum formula above,

[tex]mathrm{Total}=2(m+1)(m-2)+4frac{(m-3)(m-2)}{2}[/tex]

Some minimal algebra finally gives us the formula for the number of 3-letter sequences as a function of m:

[tex]mathrm{Total}=4(m-1)(m-2)[/tex]

That’s surprisingly simple!

Back the main question now: we want the probability that at least one of these 3-letter sequences matches our given word.  Turns out, under our assumptions, this is just a binomial distribution.  Woohoo!

Recall that a binomial distribution with n trials and  the probability, p, for a success in a single trial has the probability density function

[tex]P(X=x)=left( begin{array}{cc}n\ xend{array} right) p^x (1-p)^{n-x}[/tex]

Thus, we are looking for “at least one success” which means we calculate [tex]1-P(X=0)[/tex].  We know that [tex]n=4(m-1)(m-2)[/tex] and [tex]p=frac{2}{26^3}[/tex]

Now, you can plug and chug in your calculator or run out and stick a formula in Excel, Wolfram Alpha, Maple, etc.  Either way, we now have an easy answer to a couple of interesting questions:

### 1. If we have 20×20 grid of randomly distributed letters, what is the probability that the word “ELF” appears?

IN EXCEL:  =1-binomdist(0,4*(m-2)*(m-1),2/26^3,FALSE)