HMMT 二月 2019 · COMB 赛 · 第 1 题
HMMT February 2019 — COMB Round — Problem 1
题目详情
英文原题
- How many distinct permutations of the letters of the word REDDER are there that do not contain apalindromic substring of length at least two? (A substring is a contiguous block of letters that is partof the string. A string is palindromic if it is the same when read backwards.)
解析
英文解析
- How many distinct permutations of the letters of the word REDDER are there that do not contain apalindromic substring of length at least two? (A substring is a contiguous block of letters that is partof the string. A string is palindromic if it is the same when read backwards.)
Proposed by: Yuan Yao
Answer: 6
If two identical letters are adjacent or have a single letter in between, there is clearly a palindromicsubstring 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 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, soit has to be X. Continuing analogously, the fifth letter has to be Y, and the sixth letter has to be Z.
So any word satisfying the problem statement has to be of the form XYZXYZ. It is easy to check thatsuch a word indeed does not have any palindromic substrings. X, Y, Z can be any permutation of R,
E, D, giving a total of 6 possibilities.