1. How many distinct permutations of the letters of the word REDDER are there that do not contain a palindromic substring of length at least two? (A substring is a contiguous block of letters that is part of the string. A string is palindromic if it is the same when read backwards.)
Answer:
6
If two identical letters are adjacent or have a single letter in between, there is clearly a palindromic substring of length (respectively) two or three. So there cannot be any such substrings.
Say we have a permutation of the word REDDER without any palindromic substrings. Let us call the first letter $\mathrm{X}$. The second letter has to be different, let us call it Y. The third letter cannot be X or Y, let it be Z. Again, the fourth letter cannot be Y or Z, and we only have 3 letters to choose from, so it has to be X. Continuing analogously, the fifth letter has to be $\mathrm{Y}$, and the sixth letter has to be $\mathrm{Z}$. So any word satisfying the problem statement has to be of the form XYZXYZ. It is easy to check that such a word indeed does not have any palindromic substrings. X, Y, Z can be any permutation of R, $\mathrm{E}, \mathrm{D}$, giving a total of 6 possibilities.