Reading a Palindrome in Several Different Ways
Consider the pseudo-palindrome:
W A S I T A C A T I S A W .
In how many ways can W A S I T A C A T I S A W be read if you may start at any W and move only right, left, up, or down to adjacent letters? Keep in mind that each case can be counted twice since it is a palindrome and that the same letter can be used more than once in each sequence.
The answer is 63504.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
I got the question wrong because of ambiguity in the problem statement. I see that you have edited it now...
I apologize for being a little unclear in my solution. When I say "numbers", I mean number of ways to get to a certain letter. For example, C would be 1 . Both of the A 's would also be 1 . And thus Pascal's triangle is formed! :D
Log in to reply
You need to explain the 2 6 and 4 × 2 6 − 4 better. Currently, it's not too clear what you are thinking about.
Log in to reply
Well, there's 4 of those little Pascal's triangle sector thingies in the whole diamond, and (as I explained) we overcount by 4 so we need to subtract 4 . What are you having trouble understanding?
Log in to reply
@Finn Hulse – Because I know how to approach the problem, I can read between the lines of your solution. However, it will not be easily understood by others who have not solved the problem.
1) You should explain why 'contained in one of the four triangles formed by the diamond's diagonals"
2) You're overcomplicating things, by appealing to dynamic programming. There is a very simple explanation of where 2 6 comes from.
3) You need to explain where the overcounting comes from, and where there are only 4 of them.
Log in to reply
@Calvin Lin – Explanation for someone who wants to know:
w
w a w
w a s a w
w a s i s a w
w a s i t i s a w
w a s i t a t i s a w
w a s i t a c a t i s a w
Look at the left side of the triangle.
W <- start
w A
w a S
w a s I
w a s i T
w a s i t A
w a s i t a C <- first half
The path will be this capital letter.
And then the right side.
W <- finish
A w
S a w
I s a w
T i s a w
A t i s a w
C a t i s a w
This way we get from top W to middle C, then top W.
If we look at the right side (start) and then left side (finish), we still get the same method that from top W to middle C, then top W again.
This means that there will be 4 double counting for these methods. (4 directions at the up, down, left, right)
That's why you have to subtract by 4.
Why is there only 4? The borders (up, down, left, right) are the only things that we can move to different area (NW, NE, SE, SW). As we can see from my example (NW->NE & NE->NW).
@Calvin Lin – 1) Okay I'll explain tomorrow.
2) I was just showing off. :D
3) That is a very good point. Tomorrow. :D
Log in to reply
@Finn Hulse – The very simple explanation is thus: Look at the first quadrant. Each time, we can either move up or right; and since there are 6 moves we must do, there are 2 6 different ways.
Log in to reply
@Daniel Liu – I know. But I was just showing how Pascal's triangle can be applied (for once! :D).
We can start by counting the number of ways to spell C A T I S A W . Any such string starts with C in the center and is contained in one of the four triangles formed by the diamond's diagonals. The number of strings spelling C A T I S A W in a given triangle can be found by the standard application of dynamic programming. These numbers can be computed by diagonals parallel to the triangles hypotenuse by adding up the adjacent numbers to the left and below the letter in question. These "numbers" are the number of ways to reach a given letter, and they happen to form Pascal's triangle! The sum of these numbers on the triangle's hypotenuse, the diamond's border, is thus 2 6 !
The number of strings spelling C A T I S A W for the entire diamond is then obtained by the formula 4 × 2 6 − 4 . (We need to subtract 4 to compensate the overcount of the strings along the diamond's diagonals.) This implies that the total number of ways to spell W A S I T A C A T I S A W is given by the formula ( 4 × 2 6 − 4 ) 2 = 6 3 5 0 4 .