International Mathematics Competition
for University Students
2020

IMC2020: Day 1, Problem 1

Problem 1. Let \(\displaystyle n\) be a positive integer. Compute the number of words \(\displaystyle w\) (finite sequences of letters) that satisfy all the following three properties:

   (1) \(\displaystyle w\) consists of \(\displaystyle n\) letters, all of them are from the alphabet \(\displaystyle \{\texttt{a},\texttt{b},\texttt{c},\texttt{d}\}\);

   (2) \(\displaystyle w\) contains an even number of letters \(\displaystyle \texttt{a}\);

   (3) \(\displaystyle w\) contains an even number of letters \(\displaystyle \texttt{b}\).

(For example, for \(\displaystyle n=2\) there are \(\displaystyle 6\) such words: \(\displaystyle \texttt{aa}\), \(\displaystyle \texttt{bb}\), \(\displaystyle \texttt{cc}\), \(\displaystyle \texttt{dd}\), \(\displaystyle \texttt{cd}\) and \(\displaystyle \texttt{dc}\).)

Armend Sh. Shabani, University of Prishtina

Solution 1. Let \(\displaystyle N=\{1,2,\ldots,n\}\). Consider a word \(\displaystyle w\) that satisfies the conditions and let \(\displaystyle A,B,C,D\subset N\) be the sets of positions of letters \(\displaystyle \texttt{a}\), \(\displaystyle \texttt{b}\), \(\displaystyle \texttt{c}\) and \(\displaystyle \texttt{d}\) in \(\displaystyle w\), respectively. By the definition of the words we have \(\displaystyle A\sqcup B\sqcup C\sqcup D=N\). The sets \(\displaystyle A\) and \(\displaystyle B\) are constrained to have even sizes.

In order to construct all suitable words \(\displaystyle w\), choose the set \(\displaystyle S=A\cup B\) first; by the conditions, \(\displaystyle |S|=|A|+|B|\) must be even. It is well-known that an \(\displaystyle n\)-element set (with \(\displaystyle n\ge1\)) has \(\displaystyle 2^{n-1}\) even subsets, so there are \(\displaystyle 2^{n-1}\) possibilities for \(\displaystyle S\).

If \(\displaystyle S=\emptyset\) then we can choose \(\displaystyle C\subset N\) arbitrarily, and then the set \(\displaystyle D=S\setminus C\) is determined \(\displaystyle D\) uniquely. Since \(\displaystyle N\) has \(\displaystyle 2^n\) subsets, we have \(\displaystyle 2^n\) options for set \(\displaystyle C\) and therefore \(\displaystyle 2^n\) suitable words \(\displaystyle w\) with \(\displaystyle S=\emptyset\).

Otherwise, if \(\displaystyle k=|S|>0\), we have to choose an arbitrary subset \(\displaystyle C\) of \(\displaystyle N\setminus S\) and an even subset \(\displaystyle A\) of \(\displaystyle S\); then \(\displaystyle D=(N\setminus S)\setminus C\) and \(\displaystyle B=S\setminus A\) are determined and \(\displaystyle |B|=|S|-|A|\) will automatically be even. We have \(\displaystyle 2^{n-k}\) choices for \(\displaystyle C\) and \(\displaystyle 2^{k-1}\) independent choices for \(\displaystyle A\); so for each nonempty even \(\displaystyle S\) we have \(\displaystyle 2^{n-k}\cdot 2^{k-1}=2^{n-1}\) suitable words.

The number of nonempty even sets \(\displaystyle S\) is \(\displaystyle 2^{n-1}-1\), so in total, the number of words satisfying the conditions is

\(\displaystyle 1\cdot 2^n + (2^{n-1}-1)\cdot2^{n-1} = 4^{n-1}+2^{n-1}. \)

Solution 2. Let \(\displaystyle a_n\) denote the number of words of length \(\displaystyle n\) over \(\displaystyle \mathcal{A}=\{\texttt{a},\texttt{b},\texttt{c},\texttt{d}\}\) such that \(\displaystyle \texttt{a}\) and \(\displaystyle \texttt{b}\) appear even number of times. Further, we define the following sequences for the number of words of length \(\displaystyle n\), all over \(\displaystyle \mathcal{A}\).

   \(\displaystyle \bullet\) \(\displaystyle b_n\) - the number of words with an odd number of \(\displaystyle \texttt{a}\)'s and even number of \(\displaystyle \texttt{b}\)'s

   \(\displaystyle \bullet\) \(\displaystyle c_n\) - the number of words with even number of \(\displaystyle \texttt{a}\)'s and an odd number of \(\displaystyle \texttt{b}\)'s

   \(\displaystyle \bullet\) \(\displaystyle d_n\) - the number of words with an odd number of \(\displaystyle \texttt{a}\)'s and an odd number of \(\displaystyle \texttt{b}\)'s

We will call them A-words, B-words, C-words and D-words, respectively.

It is clear that \(\displaystyle a_1=2\) and that

\(\displaystyle a_n+b_n+c_n+d_n=4^n. \)

First, we find a recurrence relation for \(\displaystyle a_n\). If an A-word of length \(\displaystyle n\) begins with \(\displaystyle \texttt{c}\) or \(\displaystyle \texttt{d}\), it can be followed by any A-word of length \(\displaystyle n-1\), contributing with \(\displaystyle 2a_{n-1}\). If an A-word of length \(\displaystyle n\) begins with \(\displaystyle \texttt{a}\), it can be followed by any word of length \(\displaystyle n-1\) that contains an odd number of \(\displaystyle \texttt{a}\)'s and even number of \(\displaystyle \texttt{b}\)'s, thus contributing with \(\displaystyle b_{n-1}\). If an A-word of length \(\displaystyle n\) begins with \(\displaystyle \texttt{b}\), it can be followed by any word of length \(\displaystyle n-1\) that contains even number of \(\displaystyle \texttt{a}\)'s and an odd number of \(\displaystyle \texttt{b}\)'s, thus contributing with \(\displaystyle c_{n-1}\). Therefore we have the following recurrence relation:

\(\displaystyle a_n=2a_{n-1}+b_{n-1}+c_{n-1}. \)

\(\displaystyle (1) \)

Next, we find a recurrence relation for \(\displaystyle b_n\).

If a B-word of length \(\displaystyle n\) begins with \(\displaystyle \texttt{c}\) or \(\displaystyle \texttt{d}\), it can be followed by any B-word of length \(\displaystyle n-1\), contributing with \(\displaystyle 2b_{n-1}\). If a B-word of length \(\displaystyle n\) begins with \(\displaystyle \texttt{a}\), it can be followed by any word of length \(\displaystyle n-1\) that contains even number of \(\displaystyle \texttt{a}\)'s and even number of \(\displaystyle \texttt{b}\)'s, contributing with \(\displaystyle a_{n-1}\). If a B-word of length \(\displaystyle n\) begins with \(\displaystyle \texttt{b}\), it can be followed by any word of length \(\displaystyle n-1\) that contains an odd number of \(\displaystyle \texttt{a}\)'s and an odd number of \(\displaystyle \texttt{b}\)'s, contributing with \(\displaystyle \displaystyle d_{n-1}=4^{n-1}-a_{n-1}-b_{n-1}-c_{n-1}\). Therefore we have the following recurrence relation:

\(\displaystyle b_n=b_{n-1}+4^{n-1}-c_{n-1}. \)

\(\displaystyle (2) \)

Now observe that \(\displaystyle b_k=c_k\) for all \(\displaystyle k\), since simultaneously replacing \(\displaystyle \texttt{a}\)'s to \(\displaystyle \texttt{b}\)'s and vice versa we get a \(\displaystyle C\)-word from a \(\displaystyle B\)-word. Therefore (2) yields \(\displaystyle b_n=4^{n-1}\). Now (1) yields

\(\displaystyle a_n=2\cdot a_{n-1}+2\cdot 4^{n-2}. \)

Solving the last recurrence relation (for example, diving by \(\displaystyle 2^n\) we get \(\displaystyle x_n:=a_n2^{-n}\) satisfies \(\displaystyle x_n-x_{n-1}=2^{n-3}\), and it remains to sum up consecutive powers of 2) we get

\(\displaystyle a_n=2^{n-1}+4^{n-1}. \)

Solution 3. Consider the sum

\(\displaystyle \frac{(a+b+c+d)^n+(-a-b+c+d)^n +(-a+b+c+d)^n+(a-b+c+d)^n}4. \)

\(\displaystyle {(3)} \)

Expanding the parentheses as

\(\displaystyle (a+b+c+d)^n=(a+b+c+d)(a+b+c+d)\ldots (a+b+c+d),\)

we get a sum of products \(\displaystyle x_{1}\ldots x_{n}\), \(\displaystyle x_i\in \{a,b,c,d\}\), naturally corresponding to the words of length \(\displaystyle n\) over the alphabet \(\displaystyle \{\texttt{a},\texttt{b},\texttt{c},\texttt{d}\}\). Consider the other terms in the numerator similarly.

If a word \(\displaystyle x_{1}\ldots x_{n}\) contains \(\displaystyle A,B,C,D\) letters \(\displaystyle \texttt{a}\),\(\displaystyle \texttt{b}\),\(\displaystyle \texttt{c}\) and \(\displaystyle \texttt{d}\) respectively, we get \(\displaystyle a^Ab^Bc^Cd^D\) with the coefficient

\(\displaystyle \frac{1+(-1)^{A+B}+(-1)^A+(-1)^B}4=\frac{(1+(-1)^A)(1+(-1)^B)}4 =\begin{cases}1,& \text{if}\,\, A\, \text{and}\, B\, \text{are even}\\ 0,& \text{otherwise}.\end{cases} \)

Hence, by substituting \(\displaystyle a=b=c=d=1\) in \(\displaystyle (3)\) we get the answer \(\displaystyle (4^n+2^{n+1})/4=4^{n-1}+2^{n-1}\).