# How to compute the different number and ways to read a given phrase forming a pile or a stack?

I'm totally lost in this riddle, does it exist a way to calculate the different ways to read a word using a systematically approach?. In my initial attempt what I tried to do is drawing a circle over each time I could identify the word being asked but in the end I got very confused and I felt that I counted twice the word, hence I couldn't even understand if my attempt was right.

The problem is as follows:

At a kindergarten's playroom in Taichung a teacher assembled the following configuration using alphabet cubes forming a stack (see the figure as a reference) where it can be read the word DOS BANDOS. (Spanish word for two sides). Compute the number of different ways and joining neighboring letters can be read the phrase DOS BANDOS. The given alternatives in my book are:

$$\begin{array}{ll} 1.&1536\\ 2.&1280\\ 3.&256\\ 4.&768\\ 5.&1024\\ \end{array}$$

So as mentioned, from what I could identify immediately was seen from the top to bottom there are four cubes which form vertically the word being asked. From left to right, and then from right to left another two. This accounts for six. My findings are pictured in the diagram from below, colored with orange. But that's how far I went. As the more I looked at the stack I started to get confused on which can be allowed ways and which do already counted. Needless to say that the number I found is way off from the existing alternatives.

Hence can somebody help me with this riddle? An answer which would assist me the most is a way to methodically to solve this rather than just drawing circles over words as if it were a word search puzzle on a newspaper.

Overall does it exist a way?. Can somebody help me to be on the right path on this one?. If a diagram or drawing is necessary for an explanation or a justification of the method please include in your answer because I believe an answer for this question would be greatly improved with a visual aid, as I am not good at understanding just plain words or straightforward formulas.

• There's a lot of zig-zaggy ways to spell out the word, too. – kimchi lover Feb 21 '19 at 14:15
• @kimchilover That's the reason for the question in the first place. – Chris Steinbeck Bell Feb 21 '19 at 15:02

The simplest way to do this to notice that:

• The only way to get the correct sequence of letters is to start at the top and take a letter from each row in turn.

• In making your way down row by row from the top, you always have a choice between taking the left or right letter immediately below.

You make this choice $$8$$ times, and have $$4$$ possible starting points, so the total number of routes down is

$$4\cdot 2^8=1024.$$

• I'm still confused on understanding what you said with making the choice 8 times. If this is the case why the answer is not just $8 \times 2$?. What's the justification of the use of a power of $2$?. This is the part where I'm stuck at. I get the idea of multiplying by $4$ as there is that number of starting routes. But I don't understand why to get the total is a power?. How can I prove that?. – Chris Steinbeck Bell Feb 22 '19 at 21:11
• I have a second question as well, supposing that I encounter a similar problem but with $5$ letters on top and the same number of steps in that truncated pyramid. Would it be okay to conclude that the number of routes or ways to read that would to be $5 \times 2^8$?. What am I allowed or not allowed to do?. I hope you can help me to clear out these doubts. – Chris Steinbeck Bell Feb 22 '19 at 21:14
• Here's your second version, step by step. Choose from the $5$ possible starting points. Then, for each of the 5 possibilities, decide whether to turn left or right, so that's are $5\cdot 2$ routes to the second row. For each of those, choose whether to turn left or right, so $5\cdot 2\cdot 2$ routes to the third row. Each left/right choice doubles the number of routes, and by the time we get to the bottom we're up to $5\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2 = 5\cdot 2^8$ routes to the bottom. – timtfj Feb 23 '19 at 18:27
• Suppose we use coin tosses to choose between left and right. Then choosing a route means choosing from $5$ starting points then tossing a coin $8$ times—we're working out how many possibilities there are for a $1$-out-of-$5$ choice followed by $8$ coin tosses. – timtfj Feb 23 '19 at 18:46
• Yet another way to look at it (still the $5$-version): before you start, there are numerous routes to choose from. Choosing the starting point narrows it down to a fifth of them. Then each time you choose left or right, you cut half of them out. Eventually you're left with the one route that you actually chose. Since that was the result of dividing the total number of possibilities by $5$ once then by $2$ eight times, there must have been $5×2^8$ of them before narrowing them down. – timtfj Feb 23 '19 at 23:43

You need to account for the paths with turns: left-left-right-..., etc.

To do so methodically, you can make a diagram like so, starting with ones at the top, and where every other number is the sum of its top two neighbours.

   1 1 1 1
1 2 2 2 1
1 3 4 4 3 1
1 4 7 8 7 4 1
...


This means that there is only one path involving the B on the far left, while there are $$8$$ with the central B. Once you calculate the rows down to the bottom, add up the last row to get the total number of paths.

This is closely related to Pascal's Triangle. More specifically, notice that it is nothing other than the sum of four overlapping copies of Pascal's Triangle. And if you know that the $$n$$th row of Pascal's Triangle sums to $$2^{n-1}$$, ...

• I'm still unable to execute the final calculation on my own to get to the answer. I do understand a little of what you mentioned. I'm familiar with the Pascal triangle but not with the paths you said. Can you help me to do the calculation?. – Chris Steinbeck Bell Feb 21 '19 at 15:09
• I don't understand what you meant with $8$ on the central $B$ and which one is should I sum?. Can you make this part clear please?. – Chris Steinbeck Bell Feb 21 '19 at 15:10
• I'm checking with the wikipedia entry but I don't know how you got to those numbers in the Pascal triangle. Summing the upper two?. I got that. But to fill in the whole triangle seems time consuming. Does it exist a way to speed up?, because there are $9$ rows in the problem and I cannot find a way to relate those numbers with a binomial coefficient, specially in the last row. – Chris Steinbeck Bell Feb 21 '19 at 15:12
• Pascal's triangle is given in the form of a equilateral triangle but in this case it is a trapezoid. How could I modify it so I could obtain the binomial coefficients?. Did you meant this by summing the upper two?. Because I cannot find a way since in this case $4$ appears in the third row clearly a transgression from $\binom{3}{1}$ therefore can it be modified?. I'm still lost. I hope you can help me how to find the final summation which you alluded in your answer. – Chris Steinbeck Bell Feb 21 '19 at 15:21
• The number in each position in the diagram is the number of ways to reach that position from the top—which is the number of ways to get to the left one just above, plus the number of ways to get to the right one just above. Summing the last row adds together all the ways to get to the bottom. – timtfj Feb 21 '19 at 15:25