17
$\begingroup$

In how many different ways may the word DIAMOND be read in the arrangement shown? You may start wherever you like at a D and go up or down, backwards or forwards, in and out, in any direction you like , so long as you always pass from one letter to another that adjoins it.

How many ways are there?

Generalize for a word of any length that can be found in such an arrangement.

arrangement

$\endgroup$
23
$\begingroup$

Here is a slightly easier proof than Rand al'Thor's.

Let's look at a simpler problem consisting of

one quarter of the square. Starting at the central D, only do moves upwards or to the right. The resulting path will lie in the triangle that forms the top-right quarter of the square.

The number of solutions to this simpler problem is

$2^6=64$ because at every step you have exactly two choices - up or right.

The original problem consists of

four such triangles. This leads to $4$ times as many solutions, except for the fact that four solutions are double-counted. These are the four straight solutions, belonging as they do to two triangles simultaneously.
The total number of solutions is therefore $4\times 2^6 - 4 = 252$

This easily generalizes to

$4\times 2^n-4$ assuming the word does not have a palindromic tail that would allow the final moves to be towards the centre.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Nicely done. I was trying to figure out if there's any way to map this diamond onto a normal square grid, to find a bijection between centre-to-edge paths here and some classical corner-to-corner paths, but I couldn't find one. $\endgroup$ – Rand al'Thor May 26 at 13:35
  • $\begingroup$ great job! @jaap scherphuis $\endgroup$ – Shiv Prateek May 26 at 14:17
  • $\begingroup$ If a word has a double letter (like "letter") then there would also be diagonal moves $\endgroup$ – Kai May 26 at 21:25
  • $\begingroup$ diagonal moves are forbidden i forgot to mention that $\endgroup$ – Shiv Prateek May 27 at 3:34
  • $\begingroup$ Diagonal moves may be forbidden, but what if the word in question is RACECAR? You didn't say that you must start at the central letter and end at one of the outermost letters... $\endgroup$ – Quuxplusone May 27 at 6:25
19
$\begingroup$

Here's an approach that uses a Pascal-type recursion. Introduce a Cartesian coordinate system with the initial D at the origin. Let $a_{i,j}$ be the number of good paths to the terminal Ds at the border, starting from point $(i,j)$. We want to compute $a_{0,0}$. Now $a_{i,j}=1$ for the four terminal Ds and otherwise $$a_{i,j} = \sum_{\substack{k=\pm1,\ \ell=\pm1:\\|i|+|j|<|i+k|+|j+\ell|}} a_{i+k,j+\ell}.$$ The resulting values are as follows:

\begin{matrix} & & & & && 1 \\ & & & & & 1 &3 &1 \\ & & & & 1 &2 &7 &2 &1 \\ & & & 1 &2 &4 &15 &4 &2 &1 \\ & & 1 &2 &4 &8 &31 &8 &4 &2 &1 \\ & 1 &2 &4 &8 &16 &63 &16 &8 &4 &2 &1 \\ 1 &3 &7 &15 &31 &63 &\color{blue}{252} &63 &31 &15 &7 &3 &1 \\ & 1 &2 &4 &8 &16 &63 &16 &8 &4 &2 &1 \\ && 1 &2 &4 &8 &31 &8 &4 &2 &1 \\ & && 1 &2 &4 &15 &4 &2 &1 \\ & & && 1 &2 &7 &2 &1 \\ & & & && 1 &3 &1 \\ & & & & && 1 \end{matrix}

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ wow! the pattern is quite beautiful $\endgroup$ – Shiv Prateek May 26 at 14:24
  • 7
    $\begingroup$ and looks like a exquisite guess the next number... 1, 3, 7, 15, 31, 63, and the next number is not 127 $\endgroup$ – SeanC May 26 at 17:10
11
$\begingroup$

The answer is

$252$ possible paths,

the proof being as follows. (Thanks to @El-Guest for finding the error in my previous reasoning!)

You must start at the central $D$, go to $I$ in one of 4 possible ways, then from each letter you have either (A) 3 possible choices for the next one, if you're still on one of the orthogonal lines from the centre, or (B) 2 possible choices for the next one, if you've left those orthogonal lines. Also if you've left those orthogonal lines, you can't get back to them.

So, let $k$ ($1\leq k\leq6$) be the number of steps taken on those orthogonal lines. There are then just 4 possibilities for the first $k$ steps, and each of the remaining $6-k$ steps can be taken in 2 possible ways. So the total number of possibilities, for each given value of $k$, is $2^{6-k}\times4$.

Then the total is $$\sum_{k=1}^62^{6-k}\times4=4(32+16+8+4+2+1)=4\times63=252$$

This assumes that rotations and reflections of the same path count as different from each other.


For a general word of $n$ letters, laid out in a diamond configuration like this, the answer will be at least

$$\sum_{k=1}^{n-1}2^{n-1-k}\times4=4(2^n-1)=2^{n+2}-4,$$

but it may be more if doubling back on the word is possible, e.g. for palindromic words or words like BANANA. In this case, the word DIAMOND can only be spelled out starting from the centre and going to the edge, which makes counting the possibilities easier.

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ Wait, what if you go left then up to get to DIA? Aren’t there only two available Ms in that path? $\endgroup$ – El-Guest May 26 at 12:42
  • $\begingroup$ @El-Guest Oops, you're right. Edited. $\endgroup$ – Rand al'Thor May 26 at 12:55
  • $\begingroup$ This looks better — very nice. $\endgroup$ – El-Guest May 26 at 13:14
  • 1
    $\begingroup$ @Rand al'Thor looks nice, great work! $\endgroup$ – Shiv Prateek May 26 at 14:15

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.