Maths Olympiad Prep

Library / /1355 of 1394

Combinatorics Difficulty 6.2 National Olympiad Prove it United States

Problem:

Compute the number of ways to arrange 3 copies of each of the 26 lowercase letters of the English alphabet such that for any two distinct letters x1x_{1} and x2x_{2}, the number of x2x_{2}'s between the first and second occurrences of x1x_{1} equals the number of x2x_{2}'s between the second and third occurrences of x1x_{1}.

Solution

Solution:

First, we prove such a string can be divided into blocks where each block consists of the same substring written three times. We prove the following lemma.

Lemma 1. For any letter x1x_{1}, the strings between the first and second occurrences of x1x_{1} and between the second and third occurrences of x1x_{1} are the same.

Proof. Call these two strings s1s_{1} and s2s_{2}. We know they must be permutations of each other, and if a letter appears twice in s1s_{1}, it would also have to appear twice in s2s_{2}, for four appearances in all, which is impossible. Thus, no letter appears twice in s1s_{1} (and likewise in s2s_{2}).

Assume for sake of contradiction that for some letters x2x_{2} and x3x_{3} in these strings, x2x_{2} appears before x3x_{3} in s1s_{1}, but after x3x_{3} in s2s_{2}. Then, between these two appearances of x2x_{2} (which are consecutive, because no other x2x_{2}'s appear in either s1s_{1} or s2s_{2}), there must be two x3x_{3}'s. This implies there must also be two x3x_{3}'s between the other pair of consecutive x2x_{2}'s, contradiction.

We conclude any two letters in s1s_{1} and s2s_{2} appear in the same order in both strings, so s1=s2s_{1} = s_{2}. \square

Let the first letter of our 78-character string be x1x_{1}, and suppose the next appearance of x1x_{1} is the (k+1)(k + 1)-th letter. Let x2x_{2}, x3x_{3}, ..., xkx_{k} be the letters in between. Then, x2x3xkx_{2}x_{3}\ldots x_{k} is the string between the first and second x1x_{1}'s, so it must also be the string between the second and third x1x_{1}'s. Thus, after the second x1x_{1}, we must have x2x3xkx1x_{2}x_{3}\ldots x_{k}x_{1}.

Now, between the first and second xkx_{k}'s is the string x1x2x3xk1x_{1}x_{2}x_{3}\ldots x_{k-1}, so this must also be between the second and third xkx_{k}'s. Thus, after the second xkx_{k}, we must have x1x2x3xkx_{1}x_{2}x_{3}\ldots x_{k}.

Thus, the first 3k3k letters are simply x1x2x3xkx_{1}x_{2}x_{3}\ldots x_{k} repeated three times. We can remove this block of 3k3k letters and repeat to show that the whole string can be divided into such blocks.

To count the number of such strings, we first note that there are 2252^{25} ways to divide the strings into such blocks. This is because there are 25 possible places which can divide two blocks (after the 3rd, 6th, 9th, etc. letters), and we can choose any subset of these to divide blocks.

The string is then uniquely determined by the first one-third of each block, which must consist of every letter exactly once (as the whole string is just three copies of these thirds spliced together). These thirds can consist of any ordering of the 26 letters, so there are 26! strings with any given partition of blocks.

We conclude the total number of strings is 22526!\boxed{2^{25}\cdot 26!}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.